Hybrid static and regular multidimensional array

[antoine-levitt]

It seems like a common pattern to have big arrays of small arrays (e.g. 3 x N x N) and to accelerate this by converting to an array of static arrays (N x N array of SVectors of size 3). This works very well, but requires an API change: arr[:,i,j] -> arr[i,j]. Would it be possible with indexing overloading to have a type of array of SArrays such that arr[:,i,j] is an SArray?

[andyferris]

Yes! We mostly need static unit ranges and corresponding overloads of similar and we might get MVevtors out of this (and other places).

Getting SVector seems possible but not necessarily consistent with the AbstractArray interface (since the indexee is mutable).

A third possibility is a statically sized view type for view.

[cdsousa]

That is something that the Eigen library does in C++. It has the sizes as integer template parameters, and a special value means dynamic size. But it has the restriction of having only 1 or 2 dimensions, and the immutability vs mutability and stack vs heap dichotomies are pretty different in C++.

[andyferris]

Yes the idea would be to make something along the idea of Eigen.

Julia v0.7 has escape analysis enabling stack allocation of mutable structs whose lifetimes are within a function (after inlining). If that’s robust we might have fast MVectors :)

[c42f]

This makes sense to me. Presumably you'd just want a view of an AbstractArray with the first N dimensions statically known in the view type? Then implement getindex (returning an SArray) and setindex (taking a StaticArray) for that view?

In Eigen it's also possible to make the second dimension statically sized but the first dynamic. My feeling is that you generally want the small dimensions first so maybe we don't need to support this to begin with?

[c42f]

returning an SArray

Or at least, it would return one provided that the sliced dimensions are all static dimensions.

[tkoolen]

Another thing that Eigen allows you to do is have fixed maximum dimensions. For example, if you know that a matrix has 6 rows and up to 6 columns, it would still be stack-allocated. Maybe something to think about in a possible future redesign.

[c42f]

There was some great discussion of this over at #553

[mateuszbaran]

I'm working on this, primarily to make a fast array type for power manifolds (in the Manifolds.jl package). I'm pushing my code here for now: https://github.com/JuliaNLSolvers/Manifolds.jl/blob/mbaran/power-manifold/src/utils.jl (the SizedAbstractArray type). It's still WIP right now. There are so many special cases to consider though, it will take me a while to finish it. Are you interested in this work?

Ref #341 (an earlier version of SizedAbstractArray does exactly that).

[c42f]

I'm very interested in it at a general level: how do we evolve the ecosystem (including Base) in such a way that arrays with statically known dimensions are easy to work with? The abstract StaticArray being one case where all the dimensions are statically known. Ideally a lot of this could be driven based on whether Base.axes(a,i) returns a static or dynamically sized axis.

Whether the mixed static and dynamic types should live in StaticArrays itself I don't know. It kind of depends on how much of the implementation machinery we could share. In StaticArrays itself we would like to move away from unrolling so much code. If we could reach a state where we have a shared set of heuristics for codegen involving static vs dynamic dimensions then we could consider merging things together.

Ultimately we'd like to improve the abstractions in the ecosystem so that we could eventually delete a reasonable bulk of the StaticArrays codebase :-) I feel that a good medium term situation would be to move a minimal amount of core StaticArrays machinery into Base — maybe just some of the traits — and adjust Base a little so that it's easier to intercept a few key function calls. For example, to generate appropriate output container types.

[mateuszbaran]

That sounds very ambitious. My use case is a bit special because I need very few operations on such mixed arrays. Usually I'll either splice a mixed array to get a fully statically sized one or just operate on the underlying fully dynamic array.

[c42f]

Sure, it's not a short term plan ;-) But having fully general arrays which mix static and dynamic dimensions seems strictly harder than maintaining StaticArrays itself. So any plan to bring them together in a sensible way is going to be a bit ambitious.

[mateuszbaran]

I worked on my hybrid arrays and they seem to work quite well. Generated code in typical cases matches what we have in Arrays of SArrays (most importantly getindex, setindex! and broadcasting). I think I'll put it in a separate package (HybridArrays?), it might be quite useful.

By the way, I need to have sized abstract arrays somewhere. It's a small change to your SizedArray (although a bit larger than #341 ) with no drawbacks as far as I can see, so maybe it could go into StaticArrays instead of duplicating a lot of code?