What's the deal with StaticArrays?

[stevengj]

@sadish-d

They are appropriate when there are lots of small arrays involved because StaticArrays use Tuples underneath, which live in the stack rather than heap. This is more efficient because there are no “allocations” when writing to the stack and reading from the stack is faster

It is not necessarily stored in the stack. The compiler may put a tuple (hence a static array) entirely in registers, so that it never goes into RAM at all.

There are (at least) three reasons why static arrays are fast for small fixed-size arrays:

1. Completely unrolling to loop-free code. e.g. v3 = v1 + v2 is just implemented as 3 scalar additions, with no loop overhead at all, if these are all SVector{3, Float64}. The unrolled loops can also sometimes trigger SIMD optimizations.
2. Avoiding heap (or even stack) allocations of temporary arrays. This is related to point (1) — working with static arrays as local variables is as if you had just written out all of the scalar operations by hand on all the components.
3. Static arrays can be stored “inline” in other data structures. e.g. a length-N array Vector{SVector{3, Float64}}, such as [v1, v2, v3] from my example above, is stored as 3N consecutive Float64 values. This is much more efficient to access than a Vector{Vector{Float64}}, which is essentially an array of pointers to Vector{Float64} arrays, and is often faster and more convenient than a 3 \times N Matrix{Float64} (e.g. because the length 3 is stored in the type you get the benefits of (1) and (2) when accessing vectors in the array, and no “slicing” or “views” are needed). (There is also HybridArrays.jl to get the best of both worlds for matrices with a static number of rows.)

@sadish-d

how does the information about size get passed from the type signature to the compiler?

The compiler has special support for tuples (whose length is in their type signature), so anything else built on top of tuples inherits this support. (One of the major steps in this special support was julia#4042: “Tuples made me sad (so I fixed them)”.)

More generally, any integer value stored in the type gets treated as a compile-time constant for type-inferred code, which may trigger all sorts of LLVM optimizations. But the storage of tuples required specialized compiler work to implement.

@sadish-d

So why do we not have StaticArrays that are appropriate for arrays of all sizes?

It would be a totally different data structure, because the performance tradeoffs are different for long arrays. You (1) don’t want to unroll vector operations of long lengths because the code size explodes, (2) you can’t store them in registers and may even exceed the stack-size limit, and (3) you can already get many of the benefits of “inline” storage in arrays by storing them as the columns of a Matrix, whereas you wouldn’t want to store a large array inline in an arbitrary struct.

@sadish-d

it means the compiler doesn’t have to brace for the arrays changing size when there is no need

This is generally not a significant concern for large arrays.

@sadish-d

it means, in certain situations, the compiler can be confident about indices being within bound just by looking at the type.

In operations on large arrays where bounds checks are expensive, you can already eliminate this overhead by checking the bounds once outside of your loop(s) and then using @inbounds within your inner loop bodies. This is not (currently) automated by the compiler AFAIK, though.

@sadish-d

beyond performance, there are cases where it is nice to have a guarantee that the size of the container is not mutable.

This could be implemented quite easily by wrapping a Vector in another data structure, ala ReadOnlyArrays.jl. (I don’t recall a huge demand for this as a stand-alone Array-like data structure in which only the length is immutable, though?)

Actually, an easy way to fix the length of an array right now is just to use an N \times 1 Matrix, since a multidimensional Array in Julia cannot be resized — you can still access such a matrix efficiently as A[i], as if it were a 1d array with indices i ∈ 1:length(A) (what Julia calls “linear indexing”).