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

[giordano]

@rfourquet

When would you recommend FixedSizeVector over Memory ?

Memory doesn’t have multi-dimensional array semantic, it’s only a flat data container. FixedSizeArray is a light wrapper around Memory (or any other Memory-like backend actually) to provide that semantic.

[rfourquet]

Sure, but I was referring specifically to FixedSizeVector. Memory seems to have the same 1-d array semantic as FixedSizeVector. IOW, I’m interested in contexts where only 1-d will ever be needed.

[foobar_lv2]

@Mason

Could you expand on why you’d want to use the const-mutable pattern here? The only reason I can think of wanting to do this would be ~1ns faster hashing, and being able to attach finalizers to a specific FixedSizeArray rather than it’s .mem field.

Sure. If you store one of the thingies in a heap object that permits inline storage (e.g. another array-like thing, or as a field in a struct), then this copies one pointer for AlternativeFixedSizeArray, and stores the entire struct (including the size tuple) for FixedSizedArray.

If you store one of the thingies in a heap object that does not permit inline storage, e.g. because it is Any-typed, or you pass to a non-inferred / nospecialize context, then the FixedSizedArray must be boxed, i.e. an entire new object allocated. This entire new object will then be unboxed again when passing to inferred contexts, and will be boxed anew when passing to uninferred contexts. This boxing/unboxing is slow!

If you pass one of the thingies to a non-inlined function, then AlternativeFixedSizedArrays only passes a pointer in a register, whereas FixedSizedArrays needs to deal with more complex calling conventions. I’m not 100% up to date with current julia calling conventions, but afaiu this should typically go via stack, which is slower than register. In C calling convention, passing the immutable struct version by-value would kinda suck.

==========

I’m not saying that mutable struct with const fields is necessarily better than struct here – it’s just that there are tradeoffs involved, and this specific setting looks to me like one of the unusual situations where it’s close (most cases are a no-brainer for immutable struct over mutable-with-const-fields).

==========

The ideal memory layout would of course be if the size-tuple was inlined into the Memory (that must be heap-allocated with identity, for GC purposes, anyways), i.e. something like

mutable struct MemoryArray{N}
const ptr::Ptr{Nothing} #cannot implement that in julia, must be built-in like GenericMemory
const len::Int
parentForGC::Any #sometimes needed for GC purposes
const size::NTuple{Int}
end

But I think we can’t really get this.

[nsajko]

@foobar_lv2

Can you elaborate on the reasons for your decision to do

struct FixedSizeArray{T,N,Mem<:DenseVector{T}} <: DenseArray{T,N}
    mem::Mem
    size::NTuple{N,Int}
end

as opposed to

mutable struct AlternativeFixedSizeArray{T,N,Mem<:DenseVector{T}} <: DenseArray{T,N}
    const mem::Mem
    const size::NTuple{N,Int}
end

I suppose FixedSizeArrays.jl could, hypothetically, provide an additional type like you propose, perhaps named FixedSizeArrayObjectIdentity. However I’m sure we wouldn’t merge a PR like that before seeing some motivating benchmarks comparing the new type with the old one.

[giordano]

@rfourquet

IOW, I’m interested in contexts where only 1-d will ever be needed.

In that case probably not much of a difference.

The problems you showed with map are probably related to the fact Base.Array is a “privileged” container type, when there isn’t another obvious alternative.

[matthias314]

I get an error when trying to convert a Vector to a FixedSizeVector. Is this a bug, or is there a reason for this?

julia> FixedSizeVectorDefault{Int}([1, 2, 3])
3-element FixedSizeArray{Int64, 1, Memory{Int64}}:
 1
 2
 3

julia> convert(FixedSizeVectorDefault{Int}, [1, 2, 3])
ERROR: MethodError: Cannot `convert` an object of type Vector{Int64} to an object of type FixedSizeArray{Int64, 1, Memory{Int64}}
The function `convert` exists, but no method is defined for this combination of argument types.

By the way, when is it allowed to use FixedSizeVector? With a Vector as argument, it seems to be as good as FixedSizeVectorDefault:

julia> FixedSizeVector([1, 2, 3])
3-element FixedSizeArray{Int64, 1, Memory{Int64}}:
 1
 2
 3

[giordano]

@matthias314

I get an error when trying to convert a Vector to a FixedSizeVector. Is this a bug, or is there a reason for this?

There’s a reason: Before release: Remove `convert(::T, x) where {T <: FixedSizeArray}` methods · Issue #120 · JuliaArrays/FixedSizeArrays.jl · GitHub

[Benny]

@Mason

Yes, the FixedSizeArray itself can be allocated inline, but that just means you put a pointer and an NTuple inline. The actual contents of the array themselves are not stored inline, so no continuous memory stuff like with StaticArrays.

@foobar_lv2

Stack/register allocation is of course nice if you have many short-lived FixedSizeArrays that are backed by longer-living Memory instances. But I don’t see this happening in real life.

I think it’s an advantage that FixedSizeArray is an immutable struct because as far as I can tell, there’s nothing that demands its backend be heap allocated or have mutable identity. It’s possible for Mem<:DenseVector{T} to be an immutable, inline-allocated vector with the necessary static length parameter, which in turn makes FixedSizeArray an immutable, inline-allocated, multidimensional array with static length information via Mem. An SVector or NTuple wouldn’t work because:

1. Neither SArray<:StaticArray nor NTuple can subtype DenseVector
2. An NTuple (or anything built on it) with an abstract element type is strictly an abstract supertype of concrete, compact, heterogeneous Tuples, unlike a concrete Array with possible isbits-Union inline optimization. That abstract type does hurt when we need SVectors with Union{T, Nothing} elements.

We probably would need another core backend StaticMemory{L, T} to make that possibility a reality.

[giordano]

@matthias314

By the way, when is it allowed to use FixedSizeVector?

To be clear, FixedSizeVector{T} is not a concrete type because the memory backend is left free. In places where you need to specify a concrete type (e.g. for introspection) you want to use FixedSizeVectorDefault or anyway set the memory type, but constructors should use the default memory backend (Memory in Julia v1.11+) if not otherwise specified.

[digital_carver]

Since this is a common thing people might try, it might be worth either adding convert methods that just error, or adding error hints to this particular MethodError, linking to this issue and asking people to explicitly use the constructor.

[matthias314]

EDIT: added length 500 and also MutableSmallVector

I’ve run some benchmarks (with Julia 1.11.5). Here are examples for lengths 32 and 500 with Int16 elements. The timings are for 1000 operations of the given kind, numbers in brackets indicate allocations.

It appears that FixedSizeVector is noticeably faster than Vector for addition and much faster for in-place addition and comparisons. (For both kinds of additions the differences are much smaller or disappear for length 500.) However, FixedSizeVector is somewhat slower for sum and count and much slower when comparing two equal vectors. Creating a FixedSizeVector from a iterator is also slow (if I’ve done that correctly).

Length <= 32 (or == 32 if not possible otherwise)

type	create vec	create itr	sum	v + w	v .+= w	count(>(c), v)	v == w	v == w max
Vector{Int16}	31.259 μs (2)	23.356 μs (2)	7.509 μs	43.406 μs (2)	21.584 μs	11.049 μs	6.174 μs	7.009 μs
FixedSizeVectorDefault{Int16}	24.222 μs (1)	72.832 μs (1)	14.467 μs	29.580 μs (1)	8.780 μs	12.652 μs	3.224 μs	23.179 μs
MVector{32, Int16}	10.568 μs (1)	9.750 μs (1)	2.347 μs	5.875 μs	21.765 μs	2.758 μs	3.329 μs	15.119 μs
MutableFixedVector{32, Int16}	9.698 μs (1)	8.549 μs (1)	3.085 μs	2.821 μs	4.490 μs	1.594 μs	2.487 μs	2.719 μs
MutableSmallVector{32, Int16}	19.352 μs (1)	10.478 μs (1)	3.057 μs	3.157 μs	4.512 μs	2.020 μs	2.679 μs	3.229 μs

Length <= 500 (or == 500 if not possible otherwise)

type	create vec	create itr	sum	v + w	v .+= w	count(>(c), v)	v == w	v == w max
Vector{Int16}	61.644 μs (2)	69.742 μs (2)	39.312 μs	102.721 μs (2)	123.097 μs	46.504 μs	6.287 μs	30.817 μs
FixedSizeVectorDefault{Int16}	82.601 μs (1)	655.020 μs (1)	47.316 μs	100.777 μs (1)	93.896 μs	59.326 μs	3.907 μs	342.495 μs
MVector{500, Int16}	81.885 μs (1)	65.354 μs (1)	19.550 μs	104.291 μs	367.615 μs	21.174 μs	4.126 μs	198.523 μs
MutableFixedVector{500, Int16}	89.185 μs (1)	90.337 μs (1)	57.662 μs	95.209 μs	117.661 μs	22.247 μs	40.584 μs	53.424 μs
MutableSmallVector{500, Int16}	188.431 μs (1)	80.513 μs (1)	123.028 μs	114.714 μs	138.296 μs	29.382 μs	69.503 μs	69.516 μs

create vec = create from Vector
create itr = create from iterator (using collect_as for FixedSizeVector)
v == w max = comparing two equal vectors

Note: sum for MVector does not widen the element type to Int. The sum of two MVectors is an MVector by default; I’ve converted it to SVector.

The benchmark code is benchmark/benchmark_vec.jl in the SmallCollections.jl repository.

[nsajko]

@rfourquet

one issue I spotted with Memory is that a .+ a yields a Vector when a::Memory

To be perfectly clear, FixedSizeArrays.jl does not have that issue.

[Benny]

Are we even supposed to do math on Memory? I thought it was just a backend mutable buffer with an runtime-fixed size, not a full data structure with a semantic size.

[giordano]

Are you sure you reported the units correctly? 2-8 microseconds to sum 32 int16s sounds like a lot of time. What’s the CPU, and the Julia version?

[Oscar_Smith]

Are we even supposed to do math on Memory?

Sure! It’s a very simple data-structure (conceptually at least, it has a few layout tricks like small union optimization), but it fully fleshes out the interface of a 1D fixed size mutable Vector.

[matthias314]

@giordano

Are you sure you reported the units correctly?

As I wrote, the timings are for 1000 operations of the given kind.
So for a single operation you have to replace µs by ns.

[araujoms]

I rewrote some of my code using FixedSizeArrays, and got a 5% speedup in a real-world problem. Nice!

[giordano]

Thanks for the report! How about memory allocations? I’m curious to see if they also went down, and that may explain the marginally better performance.

[araujoms]

The number of allocations went down, but curiously the amount of allocated memory went up.

[mikmoore]

At some point I thought I learned that Array{T, D} for D != 1 was special-cased in the compiler to be (effectively?) immutable. But if this package has utility for D other than 1, then it must be that said special-casing only covers part of the surface area.

Does any such hack actually exist or have I been making this up? If it exists, what are the extent and limitations of its implementation?

---

Thanks for the package. It appears to be a minor tragedy that Array wasn’t this all along and we didn’t instead make a distinct type for a resizable AbstractVector. Now on to my next soapbox!

(LinearAlgebra.jl should have had its own dedicated vector/matrix types instead of pirating Array.)