performance - 型宣言を追加すると、Julia アルゴリズムが大幅に遅くなる

Question

私は非常に基本的なアルゴリズムを Julia Studio (Julia 0.2.0、OSX 10.8.2) で作成しました。このアルゴリズムは、Hearthstone の特定のマナ カーブの各ターンに残っている平均マナを計算します。アルゴリズムが完成したら、すべての変数に型宣言を追加し、これが全体の速度を向上させるのに役立つと考えました。びっくり！追加された型宣言により、コードの実行が 4 倍以上遅くなりました (~7 秒から~28 秒まで)。この奇妙な動作の原因は何ですか?どうすれば修正できますか? 型を追加すると、コンパイラがより高速なコードを生成するのに役立つか、少なくとも違いはないように感じます。

型宣言のないコードは次のとおりです (実行時間 6.76 秒)。

function all_combinations(n)
    result = Array{Int64}[]
    for x in [1:n]
        append!(result, collect(combinations(1:n,x)))
    end
    return result
end

curve = [2, 3, 4, 5, 5, 4, 3, 2, 1, 1]

games = Array{Int64}[]

function execute()
    for game_n in [1:5000]

        deck = mapreduce(
            (x) -> fill(x[1], x[2]),
            append!,
            enumerate(curve))

        function drawcard()
            card = splice!(deck, rand(1:length(deck)))
        end

        hand = [drawcard() for n in [1:3]]

        turn_leftovers = Int64[]

        for mana in [1:10]

            push!(hand, drawcard())

            possible_plays = all_combinations(length(hand))
            map!(
                play -> map(i -> hand[i], play),
                possible_plays)
            filter!(x -> sum(x) <= mana, possible_plays)

            if  !isempty(possible_plays)

                play = reduce(
                    (a, b) -> sum(a) > sum(b) ? a : b,
                    possible_plays)
                for card in play
                    splice!(hand, findfirst(hand, card))
                end
                push!(turn_leftovers, mana - sum(play))
            else
                push!(turn_leftovers, mana)
            end

        end

        push!(games, turn_leftovers)

    end
end

println(@elapsed execute())

println("Averaging over $(length(games)) games")
for turn in [1:length(games[1])]
    avrg = mean(map(game -> game[turn], games))
    println("Left on turn $turn: $avrg")
end
println("Average mana leftover: $(mean(reduce(vcat, games)))")
println("Done")

型宣言を含むコードは次のとおりです (実行時間 28.48 秒)。

function all_combinations(n)
    result = Array{Int64}[]
    for x in [1:n]
        append!(result, collect(combinations(1:n,x)))
    end
    return result
end

curve::Array{Int64} = [2, 3, 4, 5, 5, 4, 3, 2, 1, 1]

games = Array{Int64}[]

function execute()
    for game_n::Int64 in [1:5000]

        deck::Array{Int64}
        deck = mapreduce(
            (x) -> fill(x[1], x[2]),
            append!,
            enumerate(curve))

        function drawcard()
            card::Int64 = splice!(deck, rand(1:length(deck)))
        end

        hand::Array{Int64}
        hand = [drawcard() for n in [1:3]]

        turn_leftovers::Array{Int64}
        turn_leftovers = Int64[]

        for mana::Int64 in [1:10]

            push!(hand, drawcard())

            possible_plays::Array{Array{Int64}} = all_combinations(length(hand))
            map!(
                play -> map(i::Int64 -> hand[i], play),
                possible_plays)
            filter!(x::Array{Int64} -> sum(x) <= mana, possible_plays)

            if  !isempty(possible_plays)

                play::Array{Int64} = reduce(
                    (a::Array{Int64}, b::Array{Int64}) -> sum(a) > sum(b) ? a : b,
                    possible_plays)
                for card::Int64 in play
                    splice!(hand, findfirst(hand, card))
                end
                push!(turn_leftovers, mana - sum(play))
            else
                push!(turn_leftovers, mana)
            end

        end

        push!(games, turn_leftovers)

    end
end

println(@elapsed execute())

println("Averaging over $(length(games)) games")
for turn in [1:length(games[1])]
    avrg = mean(map(game -> game[turn], games))
    println("Left on turn $turn: $avrg")
end
println("Average mana leftover: $(mean(reduce(vcat, games)))")
println("Done")

最速のバージョンでも、JavaScript で記述された同等のコードよりも少し遅いことに注意してください。ただし、これはおそらくお粗末な実装のためだけです。より優れたアルゴリズムが、どの曜日でも JS を凌駕することは間違いありません。