Popfirst!() on an array

New to Julia
1

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?

2

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.

1 Like
3

In short, popfirst! and pushfirst! on Array will do the same sort of trickery that pop! and push! do — that is, they over allocate and simply change where the array “starts” to amortize the cost of the operations.

2 Likes
4

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

5

Thank you for doing this! I will start using BenchmarkTools now, too. :smiley:

1 Like