Slow insert at end of large array (Solved)

General Usage Performance
1

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

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?

2

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.

3

Why not push!?

1 Like
4

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> @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.

5

Take a look at your code again:

And the arguments of insert!:

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 :slight_smile:

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

2 Likes
6

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

7

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

8

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

1 Like