Relation to FixedSizeArrays.jl

[schmrlng]

Hi Andy,

Could you help me understand the differences in approach (pros/cons) between the implementations of SVector and SMatrix in this package and Vec and Mat in FixedSizeArrays.jl? The type definitions are identical (e.g., SVector and Vec both wrap NTuple) and the benchmarks are close, although it looks like StaticArrays might scale a bit better (do you have an idea of why)? At a very cursory level I understand that both implementations pack tightly in memory and are amenable to specialized/unrolled linear algebra code, and I'm a fan of how StaticArray is a subtype of AbstractArray, but are there any hidden design subtleties that potential users should be aware of?

Thanks,
Ed

[andyferris]

Thanks for your question, Ed.

One subtle difference is in how dimensions greater than one are treated: in FixedSizeArrays an m x n matrix is stored as m tuples of n elements each and in StaticArrays it is a flat tuple of size m x n . In Julia 0.4 the nesting was necessary to get decent performance when you have more than 8 elements, while on 0.5 we seem to get better codegen out of the flat storage scheme. It seems it's more effort for the compiler to unload the nested tuples, but for small matrices it does eventually give exactly the same codegen (e.g. 3x3 matrix multiplication).

(of course, in StaticArrays, you could implement a matrix type that uses nested tuples. You only need to implement getindex appropriately.)

Another difference which affects codegen is that StaticArrays inlines almost everything. This can make code faster slightly faster and I think it means that it gets around some issues where Julia's inference engine will start "approximating" return types that are "too complex" (see the wizardry in Base's inference.jl for that). Extensive use of generated functions (in both packages) also gets around some of those issues.

StaticArrays also has built-in mutable types (MVector, etc) which I'd like to make faster, but I'm not sure if that is even possible. At the moment, it seems that even allocating them is slower than a similarly sized Array, so that is confusing me to no end! The fact that StaticArray <: AbstractArray gets you a lot of powerful functions from Base (but you often loose any speed advantage there) and StaticArrays will let you get a pointer to your data to pass to LAPACK, etc (this is automatically managed by eig, etc).

Let me know if you have any more questions :)

Regards,
Andy

EDIT - Sorry I think I hit "post" prematurely!

[andyferris]

Also, do note that some functionality available in FixedSizeArrays is missing in StaticArrays, and vice-versa. Hopefully the list of "missing" features in StaticArrays will decrease over time.

[c42f]

From the user's point of view, I think there's two big differences:

• Whether the types are subtypes of AbstractArray. Not much to say here, it's obviously a great advantage that SArray <: AbstractArray, whereas the same isn't true for FixedArray.
• Whether you can dispatch on the particular fixed size parameters. FixedSizeArrays is a bit more flexible here, since you can easily write a function which matches any 2x2 matrix (ie, FixedMatrix{2,2}), whereas StaticArrays doesn't have an equivalent abstract statically sized matrix type. I don't think this will be a problem in practice, only time will tell.

[andyferris]

Oh yes, dispatch on size is a difference. Hopefully (in time) we can make that easier by changing the type tree or else implementing (and exporting) a trait.

[c42f]

By the way, you can of course match against SMatrix{2,2}, and I expect people will be using this standard concrete type most of the time rather than defining their own fixed size matrix type which is a subtype of SArray.

[schmrlng]

Thanks for the detailed responses! I have a much better picture of the statically-sized array landscape now. I'll leave this open in case anyone else who comes across this package has similar questions, but you can close it if you'd like.

[c42f]

The right place for this is probably the README - leaving it open until then makes sense.

[c42f]

By the way, we just had a long discussion about this over at FixedSizeArrays.jl, which led to more-or-less a decision to move forward with StaticArrays as the fixed size implementation for julia-0.5, and to move to the new home at JuliaArrays/StaticArrays.jl

See SimonDanisch/FixedSizeArrays.jl#159

[andyferris]

Right... when the dust settles we'll update the README. Something along the lines of "we recommend new packages to use StaticArrays and for packages depending on FixedSizeArrays to switch over sometime during the Julia 0.5 cycle (as we won't guarantee that FixedSizeArrays will be Julia 0.6 compatible)."?

[andyferris]

Where are we on this? @SimonDanisch do you agree with the above comment?

[SimonDanisch]

Yes, seems reasonable!
The last thing I run into was missing constructors. It seems like a type inheriting from StaticVector doesn't inherit all constructors. Having a consistent set of constructors for different fixed arrays was an important goal for usability and because its not that trivial to implement them all correctly. Are there any plans to offer this? I must admit I got myself into quite a mess with that (the constructor code in FixedSizeArrays is probably the ugliest code I've written so far)... But maybe we could offer a macro that one could execute for a custom type?
For reference:

using StaticArrays
immutable Point{N, T} <: StaticVector{T}
     data::NTuple{N, T}
end
# all these work with SVector:
Point{3}([1,2,3]) --> ERROR: The size of type `Point{3,Float32}` is not known
rand(Point{3, Float32}) --> ERROR: The size of type `Point{3,Float32}` is not known
zeros(Point{3, Float32}) --> ERROR: The size of type `Point{3,Float32}` is not known

[andyferris]

Hi Simon,

Your point about missing constructors is interesting. In this case the problem is that you haven't defined size() on Point. At the moment size() is an interface (or trait) and not an inherited type parameter. It cannot guess that the size of Point is equal to (N,).

One unfortunate thing is that you need to define both:

@pure Base.size{N}(::Type{Point{N}}) = (N,)
@pure Base.size{N,T}(::Type{Point{N,T}}) = (N,)

However I see there are further constructor issues! Sigh.

@SimonDanisch this is something we should definitely improve! Please note that, in my experience, FieldVector is a bit easier to use at the moment, but this should be extended across all types.

We need to figure out if we want the size to become a type parameter, like FixedSizeArrays does. Having size as a trait is sometimes really powerful, however.

[c42f]

We need to figure out if we want the size to become a type parameter, like FixedSizeArrays does.

This is a hard one; personally I'd be all for it if the compiler was a bit more flexible with type constructors. Without that, there's three options I know about:

• The FixedSizeArrays Tuple type hack (possibly unsanctioned black magic which will break in the future?)
• The boilerplateful approach in the abandoned PR Core type rewrite SimonDanisch/FixedSizeArrays.jl#144
• Make the StaticArrays size traits more powerful by introducing a proper type

I think some of the things we were able to achieve with the FixedSizeArrays approach were quite powerful (eg, https://github.com/SimonDanisch/FixedSizeArrays.jl/blob/0f54fa25d033c492ff7e1028b6c4b97340e5e30b/src/core.jl#L102), but I was a bit worried that it was overly complex and asking a lot from the compiler.

[SimonDanisch]

@andyferris I was using StaticArrays.FixedSizeArrays, where you defined these methods (since they behaved the same, I shortened the example):

julia> using StaticArrays # newest master
INFO: Recompiling stale cache file /home/s/.julia/lib/v0.5/StaticArrays.ji for module StaticArrays.
u
julia> using StaticArrays.FixedSizeArrays

julia> a = Point(1,2,3)
ERROR: No precise constructor found. Length of input was 3 while length of StaticArrays.FixedSizeArrays.Point{3,Int64} is 3.
 in StaticArrays.FixedSizeArrays.Point{S,T}(::Int64, ::Int64, ::Int64) at /home/s/.julia/v0.5/StaticArrays/src/core.jl:51

julia> rand(Point{3, Float32})
ERROR: No precise constructor found. Length of input was 3 while length of StaticArrays.FixedSizeArrays.Point{3,Float32} is 3.
 in macro expansion at /home/s/.julia/v0.5/StaticArrays/src/arraymath.jl:78 [inlined]
 in rand(::MersenneTwister, ::Type{StaticArrays.FixedSizeArrays.Point{3,Float32}}) at /home/s/.julia/v0.5/StaticArrays/src/arraymath.jl:70
 in rand(::Type{T}) at ./random.jl:228

[andyferris]

@SimonDanisch this is due to some changes I made to make it more obvious to the user when a type is constructed but the size isn't inferrable.

I just pushed a change which reduces that fallback error precedence to convert. Prior to this it was overriding the default constructors!!

This package clearly needs more tests... sorry about that.

[andyferris]

To add to @c42f's (very good) list, I have also considered a few more approaches:

• Add Size to StaticArray{Size, T, D} and keep Size in all subtypes, like SVector{N, T, (N,)}. For 95% of the time, the third parameter to SVector could be ignored by a user. (we could also do the horrible thing and make everyone use SVector{(3,)})
• This one is a bit weird. Have size(::StaticVector) return something like Val{Size}. We would have to introduce something like SInt{x} (static Int) such that we can perform integer arithmatic using x.
• Double down on traits. We should have more traits like whether setindex! works., the size, and so-on.

I really can't think of the best approach. I feel traits will play a bigger role in Julia in the future and am happy to move in that direction. However dispatch on traits is a little nasty currently in Julia when there are multiple traits and multiple method definitions.

Maybe we should just get some feedback on the Tuple type hack and see whether that is a "maintainable" approach.

[SimonDanisch]

Sure! I actually started porting the FSA tests to StaticArrays.... That seems like a good start and in the end, we can just migrate the tests :)

[andyferris]

Wasn't sure where to put this, but I advertised on julia-users

https://groups.google.com/forum/#!topic/julia-users/wxtAnqk3FWk

[c42f]

I think this is well resolved by now.