# Why does a vector with 10 times more elements takes 2x-5x less time to pre-allocate?

**URL:** <https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828>\
**Category:** Performance\
**Tags:** question\
**Created:** [October 27, 2024, 4:33pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828 "2024-10-27T16:33:54Z")\
**Posts on this page:** 15\
**Page:** 1

<div class="post-metadata">

**Author:** ![Olegg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/olegg/32/51316_2.png) [@Olegg](https://discourse.julialang.org/u/Olegg)\
**Post date:** [October 27, 2024, 4:33pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/1 "2024-10-27T16:33:54Z")

</div>

I’m benchmarking pre-allocation of vectors:

```julia
display(@benchmark Vector{Int}(undef, 1000) )
display(@benchmark Vector{Int}(undef, 10000) )
display(@benchmark Vector{Int}(undef, 1000) )
display(@benchmark Vector{Int}(undef, 10000) )

```

I get these results on my MacBook Pro 2021, Ventura 13.6.2 and Julia 1.11.1

 ![Screenshot 2024-10-27 at 16.23.22](https://global.discourse-cdn.com/julialang/original/3X/c/f/cf6f368f9fee45f53ec0f19e484ec0b165df9023.png)  
This is counterintuitive: pre-allocating the longer vector takes about 2 and 5 less the average and median time, respectively.

Why would this happen? And how can this be used for faster code?

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [October 27, 2024, 5:44pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/2 "2024-10-27T17:44:28Z")

</div>

I cannot replicate this (on Windows 10), so it’s certainly not a universal phenomenon.

> **Versioninfo (1.10.4)**
>
> Julia Version 1.10.4  
> Commit 48d4fd4843 (2024-06-04 10:41 UTC)  
> Build Info:  
> Official [https://julialang.org/](https://julialang.org/) release  
> Platform Info:  
> OS: Windows (x86\_64-w64-mingw32)  
> CPU: 8 × Intel(R) Core™ i7-7700K CPU @ 4.20GHz  
> WORD\_SIZE: 64  
> LIBM: libopenlibm  
> LLVM: libLLVM-15.0.7 (ORCJIT, skylake)  
> Threads: 8 default, 0 interactive, 4 GC (on 8 virtual cores)  
> Environment:  
> JULIA\_NUM\_THREADS = auto

> **1.10.4**
>
> ```julia-repl
> julia> @benchmark Vector{Int}(undef, 1000)
> BenchmarkTools.Trial: 10000 samples with 972 evaluations.
> Range (min … max): 122.634 ns … 38.501 μs ┊ GC (min … max): 0.00% … 97.11%
> Time (median): 175.823 ns ┊ GC (median): 0.00%
> Time (mean ± σ): 469.906 ns ± 736.463 ns ┊ GC (mean ± σ): 36.84% ± 27.70%
> 
> █▅▃ ▁▃▃▃▃▂▃▃▂▁▁ ▁
> ████▆▆▃▃▃▁▅████████████▇▆▆▆▆▆▄▄▅▄▃▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▃▅▄▄▄▄▅▅▄▄▄▇ █
> 123 ns Histogram: log(frequency) by time 3.93 μs <
> 
> Memory estimate: 7.94 KiB, allocs estimate: 1.
> 
> julia> @benchmark Vector{Int}(undef, 10000)
> BenchmarkTools.Trial: 10000 samples with 196 evaluations.
> Range (min … max): 611.735 ns … 13.318 μs ┊ GC (min … max): 0.00% … 88.09%
> Time (median): 878.571 ns ┊ GC (median): 0.00%
> Time (mean ± σ): 1.689 μs ± 1.234 μs ┊ GC (mean ± σ): 40.63% ± 29.03%
> 
> ▅▆▇█▆▂▅▂▂▁ ▁ ▂▃▂▂▂▂▃▅▆▆▅▄▃▂▁ ▂
> ███████████▆▆▅▃▁▃▁▁▅▅██▇▅▆▆▅▆███████████████████▇▇▆▇▇▆▆▆▅▇▅▅ █
> 612 ns Histogram: log(frequency) by time 4.57 μs <
> 
> Memory estimate: 78.17 KiB, allocs estimate: 2.
> 
> ```

> **1.11.1**
>
> ```julia-repl
> julia> @benchmark Vector{Int}(undef, 1000)
> BenchmarkTools.Trial: 10000 samples with 964 evaluations.
> Range (min … max): 136.826 ns … 6.270 μs ┊ GC (min … max): 0.00% … 83.47%
> Time (median): 164.627 ns ┊ GC (median): 0.00%
> Time (mean ± σ): 438.752 ns ± 484.669 ns ┊ GC (mean ± σ): 43.07% ± 33.43%
> 
> █▃▂▁ ▃▅▄▂▁▁▁ ▁▁▁ ▁
> █████▆▅▅▆▇█████████▇▇▇▇▆▆▇▇▇█████▇▇▆▅▆▆▅▆▆▅▄▅▅▅▅▄▄▆▅▆▆▆▅▅▅▅▅▄ █
> 137 ns Histogram: log(frequency) by time 2.45 μs <
> 
> Memory estimate: 7.88 KiB, allocs estimate: 3.
> 
> julia> @benchmark Vector{Int}(undef, 10000)
> BenchmarkTools.Trial: 10000 samples with 178 evaluations.
> Range (min … max): 783.146 ns … 13.634 μs ┊ GC (min … max): 0.00% … 74.92%
> Time (median): 1.163 μs ┊ GC (median): 0.00%
> Time (mean ± σ): 2.383 μs ± 1.610 μs ┊ GC (mean ± σ): 54.82% ± 36.67%
> 
> ▅▇▇█▆▂▁ ▂▆▆▆▆▅▄▃▂▁▁▁ ▁ ▂
> █████████▇▄▁▅▅▄▄██▆▆▅▄▄▁▁▁▄▁▄▆█████████████████▇▇▆▇█▇▆▆▆▆▆▅▅ █
> 783 ns Histogram: log(frequency) by time 6.38 μs <
> 
> Memory estimate: 78.19 KiB, allocs estimate: 3.
> 
> ```

> [@Olegg](#):
>
> And how can this be used for faster code?

I suppose you could just allocate too much and then take a view.

```julia
x = Vector{Int}(undef, alloc_length) # e.g. 10_000
x = view(x, 1:desired_length) # e.g. 1_000

```

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 27, 2024, 5:47pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/3 "2024-10-27T17:47:00Z")

</div>

this has to do with the speed of malloc vs your system allocator. note that this benchmark may be misleading since you might be ending up in a place where you are allocating, running a trivial GC and then freeing, where a more realistic workload wouldn’t show this behavior

---

<div class="post-metadata">

**Author:** ![Olegg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/olegg/32/51316_2.png) [@Olegg](https://discourse.julialang.org/u/Olegg)\
**Post date:** [October 27, 2024, 6:58pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/4 "2024-10-27T18:58:32Z")

</div>

It’s useful to know about OS dependence, thanks for checking. Interestingly, allocs estimate = 3 in either of my cases, whereas for you it’s 1 and 2 for the smaller and larger case.

The `view` solution is indeed faster than direct allocation for 1000, and almost as fast as for 10,000. Also, it’s about 7 times faster than `resize!`, so I’ll try it elsewhere in my code.

EDIT: Actually, the resize! speed could be a regression in Julia 1.9.4 → 1.11.1.

```julia
x = Vector{Int}(undef, 10000)
y = Vector{Int}(undef, 10000)
display(@benchmark view($x, 1:1000))
display(@benchmark resize!($y, 1000))

```

On 1.11.1 this outputs

```julia
view:
Range (min … max): 2.416 ns … 15.834 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 2.542 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 2.544 ns ± 0.168 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
resize!
 Range (min … max): 3.958 ns … 17.916 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 4.042 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 4.085 ns ± 0.304 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

```

And on 1.9.4:

```julia
view: 
Range (min … max): 1.791 ns … 26.500 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 1.875 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 1.910 ns ± 0.360 ns ┊ GC (mean ± σ): 0.00% ± 0.00%
resize!:
 Range (min … max): 1.791 ns … 24.166 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 1.875 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 1.915 ns ± 0.405 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

```

---

<div class="post-metadata">

**Author:** ![Olegg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/olegg/32/51316_2.png) [@Olegg](https://discourse.julialang.org/u/Olegg)\
**Post date:** [October 27, 2024, 7:05pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/5 "2024-10-27T19:05:54Z")

</div>

Thanks, I’ll benchmark this with my actual (realistic) code. Do you have some pointers which OS/hardware/GC parameters could be relevant here? Perhaps I could adjust vector sizes programmatically, based on those.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 27, 2024, 7:57pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/6 "2024-10-27T19:57:11Z")

</div>

> [@Olegg](#):
>
> The `view` solution is indeed faster than direct allocation for 1000, and almost as fast as for 10,000. Also, it’s about 7 times faster than `resize!`

This benchmark result is very weird and probably misleading. `resize!` should also be basically a zero-cost operation. How can it be slower than, well, _anything_?

---

<div class="post-metadata">

**Author:** ![eldee](https://avatars.discourse-cdn.com/v4/letter/e/b5a626/32.png) [@eldee](https://discourse.julialang.org/u/eldee)\
**Post date:** [October 27, 2024, 8:10pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/7 "2024-10-27T20:10:20Z")

</div>

> [@Olegg](#):
>
> Interestingly, allocs estimate = 3 in either of my cases, whereas for you it’s 1 and 2 for the smaller and larger case.

Note that this is only the case on 1.10.4, in 1.11.1 I also got 3 allocations for both sizes.

> [@DNF](#):
>
> `resize!` should also be basically a zero-cost operation.

This doesn’t seem to be true in 1.11: `resize!` essentially just calls `_deleteend!`, which is implemented as

```julia
function _deleteend!(a::Vector, delta::Integer)
    delta = Int(delta)
    len = length(a)
    0 <= delta <= len || throw(ArgumentError("_deleteend! requires delta in 0:length(a)"))
    newlen = len - delta
    for i in newlen+1:len
        @inbounds _unsetindex!(a, i)
    end
    setfield!(a, :size, (newlen,))
    return
end

```

(while in earlier versions it’s a `ccall`). So apart from changing the `size` attribute, it is also explicitly looping over all ‘deleted’ elements.

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 27, 2024, 8:47pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/8 "2024-10-27T20:47:51Z")

</div>

That’s shocking. The whole point of `resize!` is that it should be zero cost (or O(1)). What is the point of deleting the elements?

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 27, 2024, 10:14pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/9 "2024-10-27T22:14:11Z")

</div>

the intent, at least is that the entire loop should disappear for common eltypes. it needs to be there (and was there in C) because you don’t want deleted memory in the array keeping alive data since otherwise that would be a horrible way to have nasty memory leaks. for bitstypes it (hopefully) codegens into nothing

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [October 27, 2024, 10:29pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/10 "2024-10-27T22:29:25Z")

</div>

But benchmarks (I tried some myself) showed O(n) behavior for `Float64`. Is that unexpected?

---

<div class="post-metadata">

**Author:** ![Benny](https://avatars.discourse-cdn.com/v4/letter/b/49beb7/32.png) [@Benny](https://discourse.julialang.org/u/Benny)\
**Post date:** [October 27, 2024, 10:36pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/11 "2024-10-27T22:36:03Z")

</div>

> [@eldee](#):
>
> I cannot replicate this (on Windows 10)

Windows 11, Julia v1.11.1, and I also see the consistently shorter minimum, median, and average times for allocating the smaller vector.

---

<div class="post-metadata">

**Author:** ![Olegg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/olegg/32/51316_2.png) [@Olegg](https://discourse.julialang.org/u/Olegg)\
**Post date:** [October 27, 2024, 11:08pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/12 "2024-10-27T23:08:20Z")

</div>

I got a little more reasonable result for Julia 1.9.4. Running this code

```julia
function allocation(a::Int=1000, b::Int=10_000)
    println("Allocation")
    println(a)
    display(@benchmark Vector{Int}(undef, $a))
    println(b)
    display(@benchmark Vector{Int}(undef, $b))
    println(a)
    display(@benchmark Vector{Int}(undef, $a))
    println(b)
    display(@benchmark Vector{Int}(undef, $b))
    println("---------------------------")
end
allocation()

```

after a few times outputs

 ![Screenshot 2024-10-27 at 23.05.10](https://global.discourse-cdn.com/julialang/original/3X/0/3/03977a1921daee5f081e182085ddbf54f31cffe5.png)  
The median time is smaller for the smaller vector, whereas the average is still larger. However, for Julia 1.11.1, the outputs are the same as in my OP, even after several runs.

---

<div class="post-metadata">

**Author:** ![Oscar\_Smith](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/oscar_smith/32/25343_2.png) [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)\
**Post date:** [October 27, 2024, 11:58pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/13 "2024-10-27T23:58:07Z")

</div>

it definitely shouldn’t be. time to dig in to some profiling.

---

<div class="post-metadata">

**Author:** ![Palli](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/palli/32/3380_2.png) [@Palli](https://discourse.julialang.org/u/Palli)\
**Post date:** [October 28, 2024, 11:20am UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/14 "2024-10-28T11:20:11Z")

</div>

`Vector{Int}(undef, 1000)` is basically only allocating on 1.10 (calling jl\_alloc\_array\_1d and thus malloc), and since not initializing the speed _should be independent of size_(?):

```julia
julia> @code_lowered Vector{Int}(undef, 1000)
CodeInfo(
1 ─ %1 = Core.cconvert(Core.Int, m)
│ %2 = Core.apply_type(Core.Array, $(Expr(:static_parameter, 1)), 1)
│ %3 = Core.unsafe_convert(Core.Int, %1)
│ %4 = $(Expr(:foreigncall, :(:jl_alloc_array_1d), Array{T, 1}, svec(Any, Int64), 0, :(:ccall), :(%2), :(%3), :(%1)))
└── return %4
)

```

I believe the benchmarking inaccurate, allocating isn’t directly responsible for the GC activity (i.e. if you’re not runniing out of memory you shouldn’t have GC triggered, but it happens because of benchmarking in a loop), it is actually shown to be zero for min., but sometimes you get it for mean (and sometimes for median, but sometimes no GC activity), so I think it means cost of releasing the memory, and thus GC activity.

The min stays almost the same when allocating 10x (276.351 ns for me), while some other numbers go up, and then do go up with another 10x for 100x allocated.

However on 1.11 I see larger assembly with @code\_native and different/larger code with:

```julia
@code_lowered Vector{Int}(undef, 1000)
CodeInfo(
1 ─ %1 = Core.fieldtype
│ %2 = Core.fieldtype(self, :ref)
│ %3 = (%1)(%2, :mem)
│ %4 = Core.undef
│ mem = (%3)(%4, m)
│ %6 = mem
│ %7 = Core.memoryref(%6)
│ %8 = Core.tuple(m)
│ %9 = %new(self, %7, %8)
└── return %9

```

I think/thought malloc in general does not initialize:

> [@Oscar\_Smith](#):
>
> this has to do with the speed of malloc vs your system allocator. note that this benchmark may be misleading since

> [@Olegg](#):
>
> It’s useful to know about OS dependence, thanks for checking.

I still think on Windows it woulldn’t initialize, but one caveat, is that first allocations need to come from the kernel (basically old memory from other processes), and on any OS, then it must initialize for security reasons.

I would thus trust min. numbers. when only allocating, i.e. when using `undef` (this does not apply to e.g. zeros, that does fill and is then of course linear in speed).

---

<div class="post-metadata">

**Author:** ![Olegg](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/olegg/32/51316_2.png) [@Olegg](https://discourse.julialang.org/u/Olegg)\
**Post date:** [October 30, 2024, 1:13pm UTC](https://discourse.julialang.org/t/why-does-a-vector-with-10-times-more-elements-takes-2x-5x-less-time-to-pre-allocate/121828/15 "2024-10-30T13:13:11Z")

</div>

That’s very insightful, thanks. And CodeInfo is a great tool, which I’ll use.

For accurate benchmarking in my case, would you suggest (A) to benchmark different code (to my original)? Or (B) to use the same code, but only look at the minimum time?

If (B) is the way, does it mean that Julia’s standard benchmarking can be inaccurate due to GC activity? Then there could be implications for lots of benchmarking code.