Allocations in the loop

New to Julia
1

Hello,

I am starting to learn Julia, and am puzzled by the allocations inside the loop. It seems that I only access values inside the loop and didn’t allocate anything. However, test1 allocated 1M and test2 allocated 22G.

Could anyone kindly help explain to me why?

Thank you!

function make_dictionary!(dict, vec)
    for i in 0:9
        dict[i] = Vector{Int}()
    end
    for m in eachindex(vec)
        push!(dict[m % 10], m)
    end
end

function test1(n)
    vec = Vector(1:n)
    dict = Dict()
    make_dictionary!(dict, vec)
    r = 0.0
end

function test2(n)
    vec = Vector(1:n)
    dict = Dict()
    make_dictionary!(dict, vec)
    r = 0.0

    for r1 = 0:9
        for r2 = 0:9
            for m1 in dict[r1]
                for m2 in dict[r2]
                    r += 1
                end
            end
        end
    end
    r
end

@time test1(20000)
@time test2(20000)
2

dict = Dict{Int, Vector{Int}}() ? Because a Dict() can contain anything whatsoever, the == test it has to perform when using it is type-unstable (the compiler doesn’t know which method to call, so has to introduce a dynamic call), and that involves allocations.

1 Like
3

Thank you for your reply! Would you please expand it a little more where “==” test was done?

Also why test3 (single loop other than double loop) has no such problems.

test1: 1M; test2: 22G; test3: 2M

function test3(n)
    vec = Vector(1:n)
    dict = Dict()
    make_dictionary!(dict, vec)
    r = 0.0

    for r1 = 0:9
        for m1 in dict[r1]
            r += 1
        end
    end
    r
end
4

A Dict is a hash table. To find the key, it first hashes the value you input, r1, which it knowns to be an Int. So far so good. It then looks up in that hash value’s bucket and finds a single key, of unknown type at compile-time (because your dict is a Dict{Any, Any}). To know that this key is indeed r1, it calls ==(r1::Int, that_key::Any). That’s a dynamic call. At runtime, it’ll figure out that that_key is also an Int, and call ==(::Int,::Int).

Your test3 also allocates in the loop AFAICT. It’s just that because the loop isn’t nested, it doesn’t allocate as much.

5

Thank you!

1 Like