<p dir="auto">I'm trying to use <code class="notranslate">sizehint!</code> + <code class="notranslate">push!</code> to fill an array, but it is much slower than the equivalent operation using <code class="notranslate">resize!</code> and indexing. Benchmarks below.</p>
<p dir="auto">I'm not surprised there's <em>some</em> overhead, and I'd be willing to accept some just to avoid potential bugs resulting from uninitialized data, but the overhead is 10x:</p>
<div class="highlight highlight-source-julia notranslate position-relative overflow-auto" dir="auto" data-snippet-clipboard-copy-content="julia&gt; VERSION
v&quot;1.3.0-DEV.377&quot;

julia&gt; f!(arr, N) = ( sizehint!(arr, N); for i in 1:N; push!(arr, i); end; arr )
f! (generic function with 1 method)

julia&gt; g!(arr, N) = ( resize!(arr, N); for i in 1:N; arr[i] = i; end; arr )
g! (generic function with 1 method)

julia&gt; f!(Int[], 1_000_000) == g!(Int[], 1_000_000)
true

julia&gt; @benchmark f!(arr, 1_000_000) setup=(arr=Int[])
BenchmarkTools.Trial: 
  memory estimate:  7.63 MiB
  allocs estimate:  1
  --------------
  minimum time:     3.717 ms (0.00% GC)
  median time:      3.811 ms (0.00% GC)
  mean time:        3.870 ms (0.00% GC)
  maximum time:     6.022 ms (0.00% GC)
  --------------
  samples:          1271
  evals/sample:     1

julia&gt; @benchmark g!(arr, 1_000_000) setup=(arr=Int[])
BenchmarkTools.Trial: 
  memory estimate:  7.63 MiB
  allocs estimate:  1
  --------------
  minimum time:     392.328 μs (0.00% GC)
  median time:      419.459 μs (0.00% GC)
  mean time:        433.387 μs (0.00% GC)
  maximum time:     2.653 ms (0.00% GC)
  --------------
  samples:          10000
  evals/sample:     1"><pre class="notranslate">julia<span class="pl-k">&gt;</span> <span class="pl-c1">VERSION</span>
<span class="pl-s"><span class="pl-pds"><span class="pl-c1">v</span>"</span>1.3.0-DEV.377<span class="pl-pds">"</span></span>

julia<span class="pl-k">&gt;</span> <span class="pl-en">f!</span>(arr, N) <span class="pl-k">=</span> ( <span class="pl-c1">sizehint!</span>(arr, N); <span class="pl-k">for</span> i <span class="pl-k">in</span> <span class="pl-c1">1</span><span class="pl-k">:</span>N; <span class="pl-c1">push!</span>(arr, i); <span class="pl-k">end</span>; arr )
f! (generic <span class="pl-k">function</span> with <span class="pl-c1">1</span> method)

julia<span class="pl-k">&gt;</span> <span class="pl-en">g!</span>(arr, N) <span class="pl-k">=</span> ( <span class="pl-c1">resize!</span>(arr, N); <span class="pl-k">for</span> i <span class="pl-k">in</span> <span class="pl-c1">1</span><span class="pl-k">:</span>N; arr[i] <span class="pl-k">=</span> i; <span class="pl-k">end</span>; arr )
g! (generic <span class="pl-k">function</span> with <span class="pl-c1">1</span> method)

julia<span class="pl-k">&gt;</span> <span class="pl-c1">f!</span>(Int[], <span class="pl-c1">1_000_000</span>) <span class="pl-k">==</span> <span class="pl-c1">g!</span>(Int[], <span class="pl-c1">1_000_000</span>)
<span class="pl-c1">true</span>

julia<span class="pl-k">&gt;</span> <span class="pl-c1">@benchmark</span> <span class="pl-c1">f!</span>(arr, <span class="pl-c1">1_000_000</span>) setup<span class="pl-k">=</span>(arr<span class="pl-k">=</span>Int[])
BenchmarkTools<span class="pl-k">.</span>Trial<span class="pl-k">:</span> 
  memory estimate<span class="pl-k">:</span>  <span class="pl-c1">7.63</span> MiB
  allocs estimate<span class="pl-k">:</span>  <span class="pl-c1">1</span>
  <span class="pl-k">--------------</span>
  minimum time<span class="pl-k">:</span>     <span class="pl-c1">3.717</span> ms (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  median time<span class="pl-k">:</span>      <span class="pl-c1">3.811</span> ms (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  mean time<span class="pl-k">:</span>        <span class="pl-c1">3.870</span> ms (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  maximum time<span class="pl-k">:</span>     <span class="pl-c1">6.022</span> ms (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  <span class="pl-k">--------------</span>
  samples<span class="pl-k">:</span>          <span class="pl-c1">1271</span>
  evals<span class="pl-k">/</span>sample<span class="pl-k">:</span>     <span class="pl-c1">1</span>

julia<span class="pl-k">&gt;</span> <span class="pl-c1">@benchmark</span> <span class="pl-c1">g!</span>(arr, <span class="pl-c1">1_000_000</span>) setup<span class="pl-k">=</span>(arr<span class="pl-k">=</span>Int[])
BenchmarkTools<span class="pl-k">.</span>Trial<span class="pl-k">:</span> 
  memory estimate<span class="pl-k">:</span>  <span class="pl-c1">7.63</span> MiB
  allocs estimate<span class="pl-k">:</span>  <span class="pl-c1">1</span>
  <span class="pl-k">--------------</span>
  minimum time<span class="pl-k">:</span>     <span class="pl-c1">392.328</span> μs (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  median time<span class="pl-k">:</span>      <span class="pl-c1">419.459</span> μs (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  mean time<span class="pl-k">:</span>        <span class="pl-c1">433.387</span> μs (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  maximum time<span class="pl-k">:</span>     <span class="pl-c1">2.653</span> ms (<span class="pl-c1">0.00</span><span class="pl-k">%</span> GC)
  <span class="pl-k">--------------</span>
  samples<span class="pl-k">:</span>          <span class="pl-c1">10000</span>
  evals<span class="pl-k">/</span>sample<span class="pl-k">:</span>     <span class="pl-c1">1</span></pre></div>
<p dir="auto">Almost all time is spent in the function <code class="notranslate">_growend!</code>, which in turn is backed by a C function so I can't easily pin-point on what line the slowness is. I have reproduced this in v1.0.3 as well as latest master.</p>
<p dir="auto">When looking over my code_native, I recently saw that every push! costs me a call into the runtime library. This appears...excessive, at least for the standard case where the push can be accommodated without copying.</p>
<p dir="auto">So, lets compare the push! and the fastpush!</p>
<p dir="auto">First, lets look at what a vector actually is:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="struct array_T
    data :: Ptr{Void}
    length:: UInt64
    flags::UInt16
    elsize::UInt16
    offset::UInt32
    nrows::UInt64
    ncols_maxsz::UInt64
    stuff1::UInt64
    stuff2::UInt64
    stuff3::UInt64
end"><pre class="notranslate"><code class="notranslate">struct array_T
    data :: Ptr{Void}
    length:: UInt64
    flags::UInt16
    elsize::UInt16
    offset::UInt32
    nrows::UInt64
    ncols_maxsz::UInt64
    stuff1::UInt64
    stuff2::UInt64
    stuff3::UInt64
end
</code></pre></div>
<p dir="auto">This gives us the fastpush:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="@inline function fastpush!(A::Vector{T},val::T) where T
    if isbits(T)
        arr = unsafe_load(convert(Ptr{array_T}, pointer_from_objref(A)))
        if arr.length + arr.offset  &lt; arr.ncols_maxsz       
            unsafe_store!(convert(Ptr{UInt64}, pointer_from_objref(A)), arr.length+1, 2)
            unsafe_store!(convert(Ptr{UInt64}, pointer_from_objref(A)), arr.length+1, 4)
            @inbounds A[arr.length+1] = val
        else
            push!(A,val)
        end
    else
        push!(A,val)
    end
    A
end"><pre class="notranslate"><code class="notranslate">@inline function fastpush!(A::Vector{T},val::T) where T
    if isbits(T)
        arr = unsafe_load(convert(Ptr{array_T}, pointer_from_objref(A)))
        if arr.length + arr.offset  &lt; arr.ncols_maxsz       
            unsafe_store!(convert(Ptr{UInt64}, pointer_from_objref(A)), arr.length+1, 2)
            unsafe_store!(convert(Ptr{UInt64}, pointer_from_objref(A)), arr.length+1, 4)
            @inbounds A[arr.length+1] = val
        else
            push!(A,val)
        end
    else
        push!(A,val)
    end
    A
end
</code></pre></div>
<p dir="auto">And lets run a race:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="function pushtest(A,n)
    resize!(A, 0);
    for i = 1:n push!(A,i) end
    nothing
end

function fastpushtest(A,n)
    resize!(A, 0)
    for i = 1:n fastpush!(A,i) end
    nothing
end

function settest(A,n)
    resize!(A, n)
    for i = 1:n  A[i]=i end
    nothing
end"><pre class="notranslate"><code class="notranslate">function pushtest(A,n)
    resize!(A, 0);
    for i = 1:n push!(A,i) end
    nothing
end

function fastpushtest(A,n)
    resize!(A, 0)
    for i = 1:n fastpush!(A,i) end
    nothing
end

function settest(A,n)
    resize!(A, n)
    for i = 1:n  A[i]=i end
    nothing
end
</code></pre></div>
<p dir="auto">yielding:</p>
<div class="snippet-clipboard-content notranslate position-relative overflow-auto" data-snippet-clipboard-copy-content="Nm = 100_000_000; A = Vector{Int}(Nm); resize!(A, 0);
#after warmup:

@time settest(A,Nm); @time settest(A,Nm);
  0.356040 seconds (4 allocations: 160 bytes)
  0.326640 seconds (4 allocations: 160 bytes)

@time pushtest(A,Nm); @time pushtest(A,Nm);
  0.899436 seconds (4 allocations: 160 bytes)
  0.895555 seconds (4 allocations: 160 bytes)

@time fastpushtest(A,Nm); @time fastpushtest(A,Nm);
  0.577715 seconds (4 allocations: 160 bytes)
  0.606671 seconds (4 allocations: 160 bytes)"><pre class="notranslate"><code class="notranslate">Nm = 100_000_000; A = Vector{Int}(Nm); resize!(A, 0);
#after warmup:

@time settest(A,Nm); @time settest(A,Nm);
  0.356040 seconds (4 allocations: 160 bytes)
  0.326640 seconds (4 allocations: 160 bytes)

@time pushtest(A,Nm); @time pushtest(A,Nm);
  0.899436 seconds (4 allocations: 160 bytes)
  0.895555 seconds (4 allocations: 160 bytes)

@time fastpushtest(A,Nm); @time fastpushtest(A,Nm);
  0.577715 seconds (4 allocations: 160 bytes)
  0.606671 seconds (4 allocations: 160 bytes)
</code></pre></div>
<p dir="auto">Hence, a 30% speedup is possible if we manage to get the fastpath inlined.</p>
<p dir="auto">It would mayhaps be nice if it was somehow possible to make llvm aware of julia's runtime lib. For example, compile to llvm_IR (using clang or dragonegg?), and call into a nice library of llvm code including optimization-relevant metadata, and possibly inline current ccall-functions.</p>
<p dir="auto">Not sure whether this performance problem is worth trying to fix (and how much more expensive it is if we lose important registers on the call). It is easy to avoid, though, by implementing the checks by hand (for tight loops that need to push a lot). In a perfect world, the optimizer would reduce to only a single check for unrolled pushing loops. In my applications, I do enough other things between push!/pop! that this ends up being benign.</p>
<p dir="auto">PS. This is related to <a class="issue-link js-issue-link" data-error-text="Failed to load title" data-id="278803288" data-permission-text="Title is private" data-url="https://github.com/JuliaLang/julia/issues/24901" data-hovercard-type="pull_request" data-hovercard-url="/JuliaLang/julia/pull/24901/hovercard" href="https://github.com/JuliaLang/julia/pull/24901">#24901</a>, which removes the boundcheck from push!/pop!.</p>
<p dir="auto">I also posted this in discourse.julialang.org before. The fastpush is deliberately not a pull request, because it is dirty and architecture dependent.</p>