StaticArray types with cartesian index style

[TheBB]

I was trying to create a new static array type (an unsafe strided statically-sized view - or USS View for short). Because of the strided this type must have a cartesian index style. Most of the generated functions in StaticArrays generate code with linear indexing. Unfortunately, splitting a linear index to a cartesian one is fairly slow.

Ideally one could generate code using linear indexing for linear-indexable types and cartesian indexing for cartesian-indexable types. I tried to write a patch like this, but it turns out that generated (that is, generator) functions run in an older world and can't see new methods to Base.IndexStyle. Ouch.

So if there's interest in supporting external subtypes of StaticArray with different index styles, I believe this has to be encoded on the type level as a new parameter, i.e.

abstract type StaticArray{S, T, N, I<:IndexStyle} <: AbstractArray{T, N} end
Base.IndexStyle(::Type{StaticArray{S,T,N,I}}) where {S,T,N,I} = I()
struct SArray{S, T, N, L} <: StaticArray{S, T, N, IndexLinear} # .... etc

Is there interest in doing this?

[andyferris]

We should probably support this as a trait and change the dispatch pattern throughout the library...

[c42f]

Are you sure IndexCartesian is necessary for statically sized arrays? I think the big performance hit with turning linear into Cartesian indexing is the integer division & remainder by the array size, but for static arrays this size is known at compile time. In that case compilers usually remove the integer division using a similar algorithm to Base.MultiplicativeInverses.multiplicativeinverse (though done by LLVM).

So it's worth benchmarking before deciding on a wholesale rewrite of StaticArrays. Especially because StaticArrays assumes linear indexing in many places.