Question on allocations for push pop of arrays

Need do confirm that if we do push! to array of a single element it reallocates with just one extra space for new element (in opposite to, say, preallocate 2 times more elements for better average performance).

Thanks!

Here’s how you can check:

using Plots
list = Int[]
plot([@allocated(push!(list, i)) for i in 1:1000], xaxis=:log10)
1 Like

To answer your question, you are probably looking for sizehint!, which lets you control how much extra space is preallocated.

1 Like

No, the allocation grows geometrically, by factors of 2, so that pushing n times does O(n) work.

So, I ran the following:

lst = Int64[]
size = 100000
plot([@allocated(push!(lst, i)) for i in 1:size])
plot([@allocated(pop!(lst)) for i in 1:size])

This outputs the following 2 plots. First appear to be confirming that capacity of array doubles, which is nice.

This is plot for when we do pop. I expected to also see relocation, but three are none. Can anyone help to explain?

1 Like

There aren’t allocations, just frees. Since you are shrinking, you only have to free the part of memory you aren’t using any more. You never need to reallocate anything new.

1 Like