9e. Tuples and Static Vectors for Small Collections

Introduction

Vector creation can be a performance bottleneck, given the memory-allocation overhead associated with it. The issue arises not only when defining new vectors, but also when we reference a slice like x[1:2], or computing intermediate results on the fly like x .* y in sum(x .* y).

This section introduces one way to address this limitation of the built-in vectors. It's based on the so-called static vectors, which are made available by the StaticArrays package. Unlike the built-in vectors, which are allocated on the heap, static vectors are allocated on the stack and are essentially tuples under the hood. This feature determines that they're only suitable for collections comprising a few elements. As a rule of thumb, consider using static vectors for up to 75 elements. Beyond this threshold, the overhead associated with their creation and access will outweigh any potential performance gain, or directly result in a fatal error. [note] My recommended number of elements is actually lower than the documentation's suggested (100 elements). The reason for this discrepancy is that as you approach the upper limit, the performance benefits of static vectors compared to regular vectors decreases significantly. As a result, you may find yourself spending more time benchmarking performance than reaping any speed advantages.

Despite being built on top of tuples, static vectors offer various additional advantages. Firstly, they maintain their performance benefits even with larger collections. Secondly, static vectors are more convenient to work with, as they can be manipulated as regular vectors. In fact, they support other array types like matrices, explaining the package's name. Finally, StaticArrays provides mutable variants, making them less rigid than tuples, which only exist as immutable objects. In this respect, it's worth indicating that, while the mutable version provides performance benefits relative to regular vectors, the immutable option still offers the best performance.

Warning!

To avoid repetition, the entire section assumes all collections contain a few elements. Considering this, any benefit of static vectors that is highlighted is contingent upon this assumption. We'll also suppose that the StaticArrays package is already available in the workspace, which demands including the line using StaticArrays at the beginning of each session.

SVectors Don't Allocate and Are Faster

The objects defined in StaticArrays are built on top of tuples when possible. This entails that SVectors typically don't allocate memory.

x = rand(10)

function foo(x)
    a = x[1:2]              # 1 allocation (copy of slice)
    b = [3,4]               # 1 allocation (vector creation)

    sum(a) * sum(b)         # 0 allocation (scalars don't allocate)
end

  29.819 ns (2 allocations: 160 bytes)

x = rand(10)

@views function foo(x)
    a = x[1:2]              # 0 allocation (view of slice)
    b = [3,4]               # 1 allocation (vector creation) 

    sum(a) * sum(b)         # 0 allocation (scalars don't allocate)
end

  15.015 ns (1 allocation: 80 bytes)

x = rand(10);   tup = Tuple(x)

function foo(x)
    a = x[1:2]              # 0 allocation (slice of tuple)
    b = (3,4)               # 0 allocation (tuple creation)

    sum(a) * sum(b)         # 0 allocation (scalars don't allocate)
end

  1.400 ns (0 allocations: 0 bytes)

x = rand(10);   sx = SA[x...]

function foo(x)
    a = x[SA[1,2]]          # 0 allocation (slice of static array)
    b = SA[3,4]             # 0 allocation (static array creation)

    sum(a) * sum(b)         # 0 allocation (scalars don't allocate)
end

  1.600 ns (0 allocations: 0 bytes)

The impact of SVectors on memory allocations is especially relevant for operations creating temporary vectors, such as broadcasting.

x = rand(10)

foo(x) = sum(2 .* x)

  17.936 ns (1 allocation: 144 bytes)

x = rand(10);   sx = SVector(x...)

foo(x) = sum(2 .* x)

  1.800 ns (0 allocations: 0 bytes)

Interestingly, even if an operation doesn't allocate memory under regular vectors, SVectors still provide performance benefits. To illustrate this, consider the function sum(f, <vector>), which sums the elements of <vector> after they're transformed via f. The implementation below shows that the operation is faster with SVectors, despite not allocating memory with regular vectors.

x  = rand(10)

foo(x) = sum(a -> 10 + 2a +  3a^2, x)

  4.400 ns (0 allocations: 0 bytes)

x  = rand(10);  sx = SVector(x...);

foo(x) = sum(a -> 10 + 2a +  3a^2, x)

  2.900 ns (0 allocations: 0 bytes)

Using Static Vectors

Next, we consider operations that pre-allocate intermediate outputs in relation to static vectors. The conclusions are twofold. Firstly, if the operation exclusively uses SVectors, there's no need to pre-allocate intermediate results. Secondly, storing the final output as an MVector can entail performance gains relative to a regular vector.

The example we use involves counting the elements in x that are greater than x[i], with the operation computed for each possible index i. Formally, this is captured by sum(x .> x[i]). [note] For simplicity, we use sum to avoid introducing new functions, although it'd be more natural to use count instead. . To make the comparison starker, the operation x .> x[i] and sum are written separately.

x = rand(50)

function foo(x; output = similar(x))
    for i in eachindex(x)
        temp      = x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  3.188 μs (101 allocations: 5.17 KiB)

x = rand(50)

function foo(x; output = similar(x), temp = similar(x))
    for i in eachindex(x)
        @. temp      = x > x[i]
           output[i] = sum(temp)
    end

    return output
end

  695.745 ns (2 allocations: 992 bytes)

x = rand(50);   sx = SVector(x...)

function foo(x; output = Vector{Float64}(undef, length(x)))
    for i in eachindex(x)
        temp      = x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  183.661 ns (1 allocation: 496 bytes)

x = rand(50);   sx = SVector(x...)

function foo(x; output = similar(x))
    for i in eachindex(x)
        temp      = x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  148.817 ns (1 allocation: 448 bytes)

x = rand(50);   sx = SVector(x...)

function foo(x; output = MVector{length(x),eltype(x)}(undef))
    for i in eachindex(x)
        temp      = x .> x[i]
        output[i] = sum(temp)
    end

    return output
end

  148.975 ns (1 allocation: 448 bytes)

Note that every implementation requires pre-allocating the vector output, which leaves us with only one decision to make: whether to pre-allocate the temporary vector temp. This also explains why every implementation involves at least one memory allocation.

The "No-Preallocation" tab serves as a baseline for comparison. In contrast, the "Pre-allocating" tab reuses a regular vector to compute temp, while the "SVector" tab converts x to an SVector sx without pre-allocating temp. The benchmarks reveal that the SVector approach outperforms pre-allocation, thanks to the memory allocation avoidance and additional optimization opportunities provided by SVectors.

As for the last two tabs, they continue defining x as an SVector, but additionally treat output as an MVector. The last tab in particular does this by using similar(sx) to initialize output, whereas the other tab explicitly specifies an MVector. As the benchmarks demonstrate, integrating MVectors into the operation yields further performance gains.