# Push! vs pushfirst! performance

**URL:** <https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402>\
**Category:** Performance\
**Tags:** vector\
**Created:** [March 2, 2020, 1:15pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402 "2020-03-02T13:15:51Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [March 2, 2020, 1:15pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/1 "2020-03-02T13:15:51Z")

</div>

I was surprised at this performance:

```julia
julia> function p(x, n)
           for i = 1:n
               push!(x, i)
           end
           x
       end
p (generic function with 1 method)
julia> function pf(x, n)
           for i = 1: n
               pushfirst!(x, i)
           end
           x  
       end
pf (generic function with 1 method)

```

```julia
julia> @benchmark pf(x, 100_000_000) setup=(x=Vector{Int}())
BenchmarkTools.Trial: 
  memory estimate: 834.17 MiB
  allocs estimate: 27
  --------------
  minimum time: 3.786 s (0.43% GC)
  median time: 3.820 s (0.22% GC)
  mean time: 3.820 s (0.22% GC)
  maximum time: 3.854 s (0.01% GC)
  --------------
  samples: 2
  evals/sample: 1

```

```julia
julia> @benchmark p(x, 100_000_000) setup=(x=Vector{Int}())
BenchmarkTools.Trial: 
  memory estimate: 834.17 MiB
  allocs estimate: 26
  --------------
  minimum time: 895.597 ms (0.04% GC)
  median time: 905.239 ms (0.90% GC)
  mean time: 904.526 ms (0.90% GC)
  maximum time: 917.439 ms (1.73% GC)
  --------------
  samples: 6
  evals/sample: 1

```

Am I benchmarking this correctly? `pushfirst!` is even slower than `push!` + `reverse!`:

```julia

julia> function pr(x, n)
           for i = 1:n
               push!(x, i)
           end
           reverse(x)
       end
pr (generic function with 1 method)
julia> @benchmark pr(x, 100_000_000) setup=(x=Vector{Int}())
BenchmarkTools.Trial: 
  memory estimate: 1.56 GiB
  allocs estimate: 28
  --------------
  minimum time: 1.163 s (0.08% GC)
  median time: 1.193 s (3.46% GC)
  mean time: 1.212 s (4.24% GC)
  maximum time: 1.294 s (10.00% GC)
  --------------
  samples: 5
  evals/sample: 1 

julia> x = Vector{Int}(); y = Vector{Int}()
0-element Array{Int64,1}
julia> pf(x, 1000) == pr(y, 1000)
true

```

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [March 2, 2020, 2:37pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/2 "2020-03-02T14:37:22Z")

</div>

I think that’s traditionally the case in many languages: we optimize for appending, not inserting in front.

A naive implementation of `push!` (resp. `pushfirst!`) would re-allocate the array, copy all elements to the bigger buffer, and then add the element to the end (resp. the beginning). That’s insufferably slow because of all the copy operations, and that’s why it’s typically optimized by over-allocating; e.g. by the next power of two, the next Fibonacci number, or something close to either (see e.g. [the Python implementation](https://github.com/python/cpython/blob/7b3ab5921fa25ed8b97b6296f97c5c78aacf5447/Objects/listobject.c#L52) or [the Julia implementation](https://github.com/JuliaLang/julia/blob/2d5741174ce3e6a394010d2e470e4269ca54607f/src/array.c#L850)). Then the copy happens only every now and then, and on [average you get good complexity](https://en.wikipedia.org/wiki/Amortized_analysis#Dynamic_array).

I guess that technically, we could over-allocate the buffer and store the elements in the middle instead of in the end. That would give the same benefit both to loops of `push!` and loops of `pushfirst!`. I’m not aware of any language that does that by default – but given your surprise, maybe you are?

---

<div class="post-metadata">

**Author:** ![yuyichao](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/yuyichao/32/20_2.png) [@yuyichao](https://discourse.julialang.org/u/yuyichao)\
**Post date:** [March 2, 2020, 2:58pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/3 "2020-03-02T14:58:47Z")

</div>

> [@tkluck](#):
>
> I guess that technically, we could over-allocate the buffer and store the elements in the middle instead of in the end. That would give the same benefit both to loops of `push!` and loops of `pushfirst!` . I’m not aware of any language that does that by default – but given your surprise, maybe you are?

That’s exactly what julia does. And that’s why I don’t expect any asymptotic slowdown. The two should just be off by a constant factor with the pushing to the back easier to optimize and more optimized.

> [@anon94023334](#):
>
> `pushfirst!` is even slower than `push!` + `reverse!` :

And this comparison is unfair. It is very common for some operation to be faster if you can first prepare the problem and transfrom it into a different problem beforee transforming it back. You pay the initial and final cost once and save time elsewhere. Note that you aren’t even reversing twice. The fair comparison is to call `reverse!` in every iteration and I’ll be surprised if that is faster.

---

<div class="post-metadata">

**Author:** ![tkluck](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tkluck/32/15769_2.png) [@tkluck](https://discourse.julialang.org/u/tkluck)\
**Post date:** [March 2, 2020, 3:07pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/4 "2020-03-02T15:07:32Z")

</div>

> [@yuyichao](#):
>
> That’s exactly what julia does.

Thank you for correcting me! I didn’t know Julia did that – quite cool.

---

<div class="post-metadata">

**Author:** ![Elrod](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/elrod/32/22461_2.png) [@Elrod](https://discourse.julialang.org/u/Elrod)\
**Post date:** [March 2, 2020, 5:51pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/5 "2020-03-02T17:51:25Z")

</div>

> [@anon94023334](#):
>
> ```julia
> function pr(x, n)
> for i = 1
> push!(x, i)
> end
> reverse(x)
> end
> 
> ```

I think you meant `for i = 1:n`. But your benchmark timings make it look like that is what you did.

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [March 2, 2020, 8:07pm UTC](https://discourse.julialang.org/t/push-vs-pushfirst-performance/35402/6 "2020-03-02T20:07:21Z")

</div>

> [@Elrod](#):
>
> I think you meant `for i = 1:n` . But your benchmark timings make it look like that is what you did.

Yes - that was deleted somehow from the code snippet. The function did indeed use `1:n`. Edited.