How efficient is
popfirst!() on an Array compared to
pop!()? If I use
popfirst!() do all of the elements in the array need to be shifted over?
If they do need shifting, it would need to read through the entire array. Am I correct in assuming that
pop!() does not iterate through the entire array?
Here is a small benchmark:
julia> popper(N, f) = (b = rand(N); while !isempty(b) f(b) end)
popper (generic function with 2 methods)
julia> using BenchmarkTools
julia> @btime popper(10^6, popfirst!)
4.328 ms (2 allocations: 7.63 MiB)
julia> @btime popper(10^6, pop!)
2.943 ms (2 allocations: 7.63 MiB)
so it isn’t such a big difference.
Array will do the same sort of trickery that
push! do — that is, they over allocate and simply change where the array “starts” to amortize the cost of the operations.
If I keep doing
popfirst! followed by
push! enough times, so that I’m always pushing the element I just popped and not increasing the length of the array, would my
Array eventually need to expand allocated space, or would it cycle through the space it already has reserved?
Edit: @mbauman because I think I did a general reply, rather than a reply to you
Thank you for doing this! I will start using BenchmarkTools now, too.