[ANN] FixedSizeArrays.jl: What Array probably should have been

[giordano]

This has been one year in the making, but the first release of FixedSizeArrays.jl is finally out and you can install it in your environment with

import Pkg
Pkg.add("FixedSizeArrays")

This package can be installed in Julia v1.10 and following releases, but the improvements mentioned in the sections below are generally available only in v1.11+ thanks to the use of the new Memory type.

@nsajko and @oscar_smith greatly contributed to FixedSizeArrays.jl.

Motivation

The Base.Array type is very convenient and flexible, but in many applications it’s too flexible: it’s a dynamic array type, which allows you to add or remove elements from both ends. However there are many situations (most notably linear algebra applications) where this flexibily is unnecessary and actually comes with a performance cost: it prevents some compiler optimisations, since the size of the array could change, even if it never does in practice. The package FixedSizeArrays.jl provides a mutable array implementation, FixedSizeArray, with the same backend as Base.Array (this is an implementation detail!), but whose size is fixed after construction. This allows the compiler to better reason about optimisations, since the size of an array is known with certainty after construction.

As a taster of the performance of FixedSizeArrays, allocating and filling a FixedSizeVector is (slightly) faster and uses less memory (32 bytes) than an equally sized Base.Vector:

julia> using BenchmarkTools, FixedSizeArrays

julia> for n in (0, 2^0, 2^5, 2^10, 2^15, 2^20, 2^25, 2^30)
           @info "n = $(n)"
           @btime fill!(Vector{Float32}(undef, $(n)), 0.0)
           @btime fill!(FixedSizeVectorDefault{Float32}(undef, $(n)), 0.0)
       end
[ Info: n = 0
  5.028 ns (1 allocation: 32 bytes)
  2.884 ns (0 allocations: 0 bytes)
[ Info: n = 1
  8.280 ns (2 allocations: 64 bytes)
  6.991 ns (1 allocation: 32 bytes)
[ Info: n = 32
  9.534 ns (2 allocations: 192 bytes)
  7.569 ns (1 allocation: 160 bytes)
[ Info: n = 1024
  91.336 ns (3 allocations: 4.07 KiB)
  88.852 ns (2 allocations: 4.04 KiB)
[ Info: n = 32768
  1.578 μs (3 allocations: 128.07 KiB)
  1.641 μs (2 allocations: 128.04 KiB)
[ Info: n = 1048576
  55.965 μs (3 allocations: 4.00 MiB)
  35.493 μs (2 allocations: 4.00 MiB)
[ Info: n = 33554432
  42.459 ms (3 allocations: 128.00 MiB)
  42.026 ms (2 allocations: 128.00 MiB)
[ Info: n = 1073741824
  1.352 s (3 allocations: 4.00 GiB)
  1.340 s (2 allocations: 4.00 GiB)

Furthermore, to facilitate escape analysis, when possible we throw a custom error exception when accessing out-of-bounds indices: this exception does not capture the entire array, thus enabling further optimisations, such as entirely removing memory allocations for small arrays because the error path could be elided (note: this happens only in Julia v1.12+):

julia> using BenchmarkTools, FixedSizeArrays, Random

julia> function g(T)
           v = T(undef, 250)
           rand!(v)
           return v[begin] + v[end]
       end
g (generic function with 1 method)

julia> @btime g(Vector{Float64})
  98.515 ns (2 allocations: 2.02 KiB)
1.4551362750846786

julia> @btime g(FixedSizeVectorDefault{Float64})
  90.504 ns (0 allocations: 0 bytes)
0.827647261037804

Comparison with other packages

See the documentation for comparison with other fixed-size arrays in the ecosystem, but in a gist this does not replace StaticArray if what you want is an immutable stack-allocated array with the size in the type domain which you can dispatch on. FixedSizeArray really looks a lot more like Base.Array, but with fixed size.

JuliaCon talk

If you’re going to attend JuliaCon 2025, either in-person or remotely, make sure to come to our talk FixedSizeArrays.jl: What Array probably should have been.

[drandran12]

Congrats! Will need to benchmark this with StaticArrays.MVector and Smallcollections.MutableSmallVector soon.

[giordano]

I’m not familiar with Smallcollections.MutableSmallVector, but a comparison with StaticArrays.MArray is mentioned in the docs: I don’t know about performance, but the use case of FixedSizeArray vs StaticArrays.MArray is slightly different. FixedSizeArray really wants to be a “better” Base.Array for numerical applications, rather than trying to optimise small arrays (FixedSizeArray is based on Memory rather than Tuple, so it should perform equally well at all sizes) or dispatch on array’s size (FixedSizeArray doesn’t allow that), which is what StaticArrays.jl does best.

[Benny]

@giordano

The Base.Array type is very convenient and flexible, but in many applications it’s too flexible: it’s a dynamic array type, which allows you to add or remove elements from both ends. However there are many situations (most notably linear algebra applications) where this flexibily is unnecessary and actually comes with a performance cost: it prevents some compiler optimisations, since the size of the array could change, even if it never does in practice.

Possibly clarified in your upcoming talk or somewhere in the devdocs, but do you mean Vector specifically? I had assumed that the “fixed-size” Memory would’ve at least allowed those fixed size optimizations for N>=2 Arrays. If not, how does FixedSizeArray’s inform the compiler that you really won’t reallocate the Memory? It lacks size information in the type parameters that StaticArrays have, so that can’t be it.

Also one more favorable point of comparison between FixedSizeArray and MArray: Memory can leverage the isbits-Union optimization, NTuple and anything based on it can’t. To elaborate, a concrete Memory with an element type of a small Union of (up to 256, I think) isbits types can store each element in contiguous blocks of the largest type’s size like a C union, followed directly by contiguous bytes specifying the type of each element (on the same single Memory, unlike a struct of arrays). Concrete tuples are strictly structures of concrete types, so NTuple{n, Union{T, Nothing}} is strictly an abstract type and thus cannot use the isbits-Union optimization, both significantly hurting the performance and data locality of StaticArrays despite decent type inference of indexing. FixedSizeArray doesn’t stand in for SArray because mutable Memory can’t be reliably stored inlined, but that’s a different conversation for an immutable version of Memory or a tuple that acts like an anonymous version of structs.

[giordano]

@Benny

If not, how does FixedSizeArray’s inform the compiler that you really won’t reallocate the Memory?

The size is a field of an immutable struct:

src/FixedSizeArray.jl

This is the same layout as Base.Array, but that’s a mutable struct:

base/boot.jl

If a function depends only on the size/length of a FixedSizeArray, that can be entirely constant-propagated, see for example FixedSizeArrays.jl Showcase · JuliaArrays/FixedSizeArrays.jl · Discussion #62 · GitHub.

[nsajko]

@Benny

I had assumed that the “fixed-size” Memory would’ve at least allowed those fixed size optimizations for N>=2 Arrays.

I’m not sure how that could be implemented, though, given that Vector === Array{T, 1} where {T}. That is, Vector and Matrix differ just by that one type parameter, so one can’t simplify Matrix without affecting Vector, I think.

See also this PR:

• Allow taking Matrix slices without an extra allocation by vtjnash · Pull Request #56236 · JuliaLang/julia · GitHub

  Since changing Array to use Memory as the backing, we had the option of making non-Vector arrays more flexible, but had instead preserved the restriction that they must be zero offset and equal in length to the Memory. This results in extra complexity, restrictions, and allocations however, but doesn’t gain any known benefits. Indeed, it makes it harder to allow resizing or reshaping Matrices completely flexibly.