# Push! and insert! very slow? (julia 1.11) (EDIT: No; just one-time allocations.)

**URL:** <https://discourse.julialang.org/t/push-and-insert-very-slow-julia-1-11-edit-no-just-one-time-allocations/122502>\
**Category:** Performance\
**Created:** [November 11, 2024, 3:33pm UTC](https://discourse.julialang.org/t/push-and-insert-very-slow-julia-1-11-edit-no-just-one-time-allocations/122502 "2024-11-11T15:33:06Z")\
**Posts on this page:** 2\
**Page:** 2

<div class="post-metadata">

**Author:** ![mlanghinrichs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mlanghinrichs/32/50371_2.png) [@mlanghinrichs](https://discourse.julialang.org/u/mlanghinrichs)\
**Post date:** [November 12, 2024, 12:23pm UTC](https://discourse.julialang.org/t/push-and-insert-very-slow-julia-1-11-edit-no-just-one-time-allocations/122502/22 "2024-11-12T12:23:18Z")

</div>

yes, my sentence was also not clear at all. Thanks a lot for your help!

> [@GunnarFarneback](#):
>
> Since moving the data around is a bottleneck you should look for ways to reduce that. How important is it to keep the ordering of your elements? Are there other ways to handle that? What are the actual requirements on the vector?

Yes, thanks! The ordering is important in my case, but, as you say, maybe there are better ways to achieve that. I will think about this!

---

<div class="post-metadata">

**Author:** ![mlanghinrichs](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mlanghinrichs/32/50371_2.png) [@mlanghinrichs](https://discourse.julialang.org/u/mlanghinrichs)\
**Post date:** [November 12, 2024, 5:01pm UTC](https://discourse.julialang.org/t/push-and-insert-very-slow-julia-1-11-edit-no-just-one-time-allocations/122502/23 "2024-11-12T17:01:46Z")

</div>

To extend my last post and for people who run into similar issues with `insert!` and `deleteat!`. With a relatively simple trick I was able to drastically improve the run time of the simulation algorithm, eliminating the cost associated with these two methods entirely.

I introduced a temporary `positions` array that allowed to switch to `push!` and `pop!` methods instead, and sorting the array only in the end into the correct order. Run time improvement scales with the length of the input array; in my use cases it was ~100 fold.

Reduced versions of the simulation algorithm are posted below; together with some benchmarks. Thanks for all the help and hints along the way; for my needs I can consider this solved! 🙂

```julia
# original version with insert! and deleteat!
function sim_0!(array, nstep)
    for __ in 1:nstep
        isempty(array) && break

        arrind = rand(1:length(array))

        if rand() < 0.5
            insert!(array, arrind, array[arrind])
        else
            deleteat!(array, arrind)            
        end
    end

    array
end

# improved version with push! and pop! and position array
function sim_1!(array, nstep)
    positions = collect(1:length(array))

    for __ in 1:nstep
        isempty(array) && break

        arrind = rand(1:length(array))

        if rand() < 0.5
            push!(array, array[arrind])
            push!(positions, positions[arrind])
        else
            array[arrind], array[end] = array[end], array[arrind]
            positions[arrind], positions[end] = positions[end], positions[arrind]
            pop!(array)
            pop!(positions)
        end
    end

    # sort array according to positions
    array = array[sortperm(positions)]

    array
end

using BenchmarkTools

@btime sim_0!(a, 1_000_000) setup=(a = collect(1:100)) evals=1
@btime sim_1!(a, 1_000_000) setup=(a = collect(1:100)) evals=1
# 28.981 μs (0 allocations: 0 bytes)
# 5.332 μs (4 allocations: 992 bytes)
# => same order of magnitude

@btime sim_0!(a, 1_000_000) setup=(a = collect(1:10_000)) evals=1
@btime sim_1!(a, 1_000_000) setup=(a = collect(1:10_000)) evals=1
# 199.213 ms (3 allocations: 216.00 KiB)
# 10.512 ms (16 allocations: 676.62 KiB)
# => 10 times difference

@btime sim_0!(a, 1_000_000) setup=(a = collect(1:100_000)) evals=1
@btime sim_1!(a, 1_000_000) setup=(a = collect(1:100_000)) evals=1
# 3.686 s (3 allocations: 1.36 MiB)
# 15.469 ms (16 allocations: 5.70 MiB)
# => >200 times difference

a0 = sim_0!(collect(1:100_000), 1_000_000)
a1 = sim_1!(collect(1:100_000), 1_000_000)

# check statistical properties (are identical)
using StatsBase
mean(values(countmap(a0))), mean(values(countmap(a1)))
std(values(countmap(a0))), std(values(countmap(a1)))

```

[Previous page](https://discourse.julialang.org/t/push-and-insert-very-slow-julia-1-11-edit-no-just-one-time-allocations/122502.md?page=1)