Allocations when pushing to SVector in a loop

General Usage
1

I’m trying to use SVectors from StaticArrays.jl to minimise allocations in a piece of code, but seeing some weird behaviour (and extra allocations) in a specific use case. If I call the following function

function foo()
    v = SVector{0,Int64}()
    v = push(v, 0)
end

@btime returns 1.815 ns (0 allocations: 0 bytes). As expected, everything is done on the stack. But if I push to the SVector in a loop, like so

function bar()
    v = SVector{0,Int64}()
    for i in 1:10
        v = push(v, i)
    end
end

then I end up with 233.220 ns (10 allocations: 560 bytes). Can anyone tell me what’s going on here?

2

See Performance Tips Β· The Julia Language

v changes type in every iteration.

4 Likes
3

To elaborate a bit on @kristoffer.carlsson’s answer, consider:

julia> v = SVector{0, Int64}()
0-element SArray{Tuple{0},Int64,1,0}

julia> push(v, 0)
1-element SArray{Tuple{1},Int64,1,1}:
 0

One way around this is to use mutable MArrays:

function bar()
    v = zeros(MVector{10})
    for i ∈ 1:10
        v[i] = i
    end
end

julia> @btime bar()
  1.640 ns (0 allocations: 0 bytes)
2 Likes
4

Thanks @kristoffer.carlsson and @nilshg, that makes sense. Why the allocations though? I understand that using an immutable SVector would be inefficient, but how does the type instability result in the assignment allocating to the heap when, e.g., both SVector{0,Int64} and SVector{1,Int64} exist on the stack?

5

both SVector{0,Int64} and SVector{1,Int64} exist on the stack

There’s nothing special about SVector which guarantees that it’s allocated on the stack. The elements commonly exist only in registers (for type stable code with short SVectors), or in a heap allocated β€œbox”, for type unstable code. The detail of what storage is used is entirely up to the compiler.

You can see what’s happening with @code_warntype: note the several occurrences of Any. This means the compiler can’t figure out the type of this value at compile time, and will resort to putting the value on the heap next to its runtime type information.

julia> function bar()
           v = SVector{0,Int64}()
           for i in 1:10
               v = push(v, i)
           end
           v
       end
bar (generic function with 1 method)

julia> @code_warntype bar()
Body::Any
1 ─       goto #7 if not true
2 β”„ %2  = Ο† (#1 => $(QuoteNode(Int64[])), #6 => %5)::Any
β”‚   %3  = Ο† (#1 => 1, #6 => %11)::Int64
β”‚   %4  = Ο† (#1 => 1, #6 => %12)::Int64
β”‚   %5  = (Main.push)(%2, %3)::Any
β”‚   %6  = (%4 === 10)::Bool
└──       goto #4 if not %6
3 ─       goto #5
4 ─ %9  = (Base.add_int)(%4, 1)::Int64
└──       goto #5
5 β”„ %11 = Ο† (#4 => %9)::Int64
β”‚   %12 = Ο† (#4 => %9)::Int64
β”‚   %13 = Ο† (#3 => true, #4 => false)::Bool
β”‚   %14 = (Base.not_int)(%13)::Bool
└──       goto #7 if not %14
6 ─       goto #2
7 β”„ %17 = Ο† (#5 => %5, #1 => $(QuoteNode(Int64[])))::Any
└──       return %17
2 Likes