🎓 A1Learner
🔍
0 of 47 lessons completed

Julia Allocation Patterns

Allocation patterns are the ways a program creates new storage while it runs. Good patterns create storage once and reuse it instead of growing it again and again.

Growing a list costs new storage step by step

A list grown in a loop reaches 100 entries. Its count shows the cost of growing step by step.

function grow_list(n)
    xs = Int[]
    for i in 1:n
        push!(xs, i)
    end
    return xs
end
grow_list(3)
println(length(grow_list(100)))
println(sum(grow_list(100)))
println(@allocated grow_list(100))

A sized list costs less new storage

A list given room for 100 entries in advance reaches the same size and sum. Its count is smaller.

function sized_list(n)
    xs = Int[]
    sizehint!(xs, n)
    for i in 1:n
        push!(xs, i)
    end
    return xs
end
sized_list(3)
println(length(sized_list(100)))
println(sum(sized_list(100)))
println(@allocated sized_list(100))

A buffer filled again needs no new storage

A buffer can be filled a second time. The second fill needs no new storage.

function refill_list!(buf)
    for i in eachindex(buf)
        buf[i] = 2 * i
    end
    return sum(buf)
end
buf = Vector{Int}(undef, 5)
refill_list!(buf)
println(@allocated refill_list!(buf))
println(buf)
println(sum(buf))

Example

function sized_build_list(n)
    xs = Int[]
    sizehint!(xs, n)
    for i in 1:n
        push!(xs, i)
    end
    return xs
end
function refill_three!(buf)
    for i in eachindex(buf)
        buf[i] = 3 * i
    end
    return sum(buf)
end
sized_build_list(3)
buf = sized_build_list(5)
println(sum(buf))
refill_three!(buf)
println(@allocated refill_three!(buf))
println(buf)
println(sum(buf))

Key points

  • Growth: growing a list inside a loop creates new storage again and again as the list grows.
  • Preallocation: sizehint! sets aside room in a list in advance, so later pushes need less new storage.
  • Buffer: a buffer is a list kept around so later work can fill it instead of building a new list each time.
  • Sized list: a list sized in advance shows a smaller @allocated count than the same list grown step by step.
  • Reuse: a buffer filled again by a second call needs no new storage when the buffer already exists.

In this example, a sized list of 5 entries is built and summed. The list is then filled with tripled entries. The refill count is 0. The new sum is 45.

Note

measure @allocated after warm-up, so the count shows the pattern and not compilation.

Try it Yourself

Edit the code, then press Run.

Running is simulated · JuliaHub

Exercise

Why does a sized list show a smaller @allocated count than a grown list?