How fast is `unshift!` for a `Vector`?

General Usage
1

unshift! adds an element at the front of a Vector, which requires shifting the whole contents of the Vector to the right. This feels like is should be slow (or, rather, slooow).

However, some naive benchmarking indicates otherwise:

using BenchmarkTools

julia 0.6> @btime push!(v, 1) samples=1000 evals=1000;
  25.801 ns (0 allocations: 0 bytes)

julia 0.6> @btime unshift!(v, 1) samples=1000 evals=1000;
  26.104 ns (0 allocations: 0 bytes)

Is unshift! actually as fast as this would indicate?

2

No, the Array implementation in Base is designed to efficiently insert/delete items at both ends of the array. See the code to grow the beginning of the array, for example. When items are inserted, it doubles the allocated length of the array as needed and leaves some unused space at the beginning for inserting subsequent items. This means that repeatedly inserting items at either end has O(1) amortized cost.

7 Likes
3

Though a demonstration of @stevengj’s answer is redundant:

julia> pointer(v)
Ptr{Float64} @0x00007f24867610b0

julia> unshift!(v,1);

julia> pointer(v)
Ptr{Float64} @0x00007f24867610a8
1 Like
4

Great, thanks!