# Slow insert at end of large array (Solved)

**URL:** <https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264>\
**Category:** Performance\
**Tags:** first-steps\
**Created:** [January 30, 2019, 7:08am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264 "2019-01-30T07:08:19Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![robsmith11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robsmith11/32/29641_2.png) [@robsmith11](https://discourse.julialang.org/u/robsmith11)\
**Post date:** [January 30, 2019, 7:08am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/1 "2019-01-30T07:08:19Z")

</div>

Why is inserting an element at the end of an array (with enough room – as evidenced by the lack of allocations) so slow?

```julia
julia> a0 = repeat([1], 10^9);

julia> @btime insert!(a,1,10^9 + 1) evals=1 setup=(a=sizehint!(deepcopy($a0), 10^9 + 1));
887.683 ms (0 allocations: 0 bytes)

```

There should be no need to move any memory around, right?

---

<div class="post-metadata">

**Author:** ![jbrea](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jbrea/32/3879_2.png) [@jbrea](https://discourse.julialang.org/u/jbrea)\
**Post date:** [January 30, 2019, 7:26am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/2 "2019-01-30T07:26:44Z")

</div>

Why `insert!` and not `a[10^9+1] = 1`?

It may be interesting to inspect `@code_native insert!(a0,1,10^9)` to see what is happing.

Btw. `a0 = fill(1, 10^9)` would be an alternative for the first line.

---

<div class="post-metadata">

**Author:** ![ChrisRackauckas](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/chrisrackauckas/32/77_2.png) [@ChrisRackauckas](https://discourse.julialang.org/u/ChrisRackauckas)\
**Post date:** [January 30, 2019, 7:50am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/3 "2019-01-30T07:50:50Z")

</div>

Why not `push!`?

---

<div class="post-metadata">

**Author:** ![robsmith11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robsmith11/32/29641_2.png) [@robsmith11](https://discourse.julialang.org/u/robsmith11)\
**Post date:** [January 30, 2019, 7:56am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/4 "2019-01-30T07:56:34Z")

</div>

> [@jbrea](#):
>
> Why `insert!` and not `a[10^9+1] = 1` ?

> [@ChrisRackauckas](#):
>
> Why not `push!` ?

Because it’s just a simplified example. In my actual code, I’ll be inserting mostly _near_ the end, but not always exactly at the end.

```julia
julia> @code_native insert!(a0,1,10^9 + 1);
        .text
; ┌ @ array.jl:1151 within `insert!'
        pushq %r15
        pushq %r14
        pushq %rbx
        movq %rdx, %r14
        movq %rsi, %r15
        movq %rdi, %rbx
; │ @ array.jl:1152 within `insert!'
; │┌ @ array.jl:814 within `_growat!'
; ││┌ @ int.jl:52 within `-'
        leaq -1(%r15), %rsi
; ││└
        movabsq $jl_array_grow_at, %rax
        movl $1, %edx
        callq *%rax
; │└
; │ @ array.jl:1154 within `insert!'
; │┌ @ array.jl:767 within `setindex!'
        movq (%rbx), %rax
        movq %r14, -8(%rax,%r15,8)
; │└
; │ @ array.jl:1155 within `insert!'
        movq %rbx, %rax
        popq %rbx
        popq %r14
        popq %r15
        retq
        nopw %cs:(%rax,%rax)
; └

```

I’m not good at reading assembly, but that seems pretty reasonable. I think the `$jl_array_grow_at` should only be called if there’s not enough room.

---

<div class="post-metadata">

**Author:** ![bennedich](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/bennedich/32/4894_2.png) [@bennedich](https://discourse.julialang.org/u/bennedich)\
**Post date:** [January 30, 2019, 8:10am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/5 "2019-01-30T08:10:12Z")

</div>

Take a look at your code again:

> [@robsmith11](#):
>
> insert!(a, 1, 10^9 + 1)

And the arguments of `insert!`:

```julia
help?> insert!
search: insert! InsertionSort

  insert!(a::Vector, index::Integer, item)

  Insert an item into a at the given index. index is the index of item in the resulting a.

```

Hope this explains it 🙂

Spoiler: (you’re inserting the value 10^9 + 1 at index 1, not inserting 1 at the end!)

---

<div class="post-metadata">

**Author:** ![robsmith11](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/robsmith11/32/29641_2.png) [@robsmith11](https://discourse.julialang.org/u/robsmith11)\
**Post date:** [January 30, 2019, 8:12am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/6 "2019-01-30T08:12:19Z")

</div>

Doh! Thanks for pointing out my stupid mistake that I just spent that last hour on. 😄

---

<div class="post-metadata">

**Author:** ![carstenbauer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/carstenbauer/32/4981_2.png) [@carstenbauer](https://discourse.julialang.org/u/carstenbauer)\
**Post date:** [January 30, 2019, 8:49am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/7 "2019-01-30T08:49:14Z")

</div>

OT: Nice spoiler 🙂 How did you create it? Markdown?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [January 30, 2019, 9:14am UTC](https://discourse.julialang.org/t/slow-insert-at-end-of-large-array-solved/20264/8 "2019-01-30T09:14:07Z")

</div>

Discourse has a spoiler feature, click on the cogwheel icon in the toolbar.