# Allocations in the loop

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)
``````

`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

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
``````

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.

Thank you!

1 Like