Create an Array interop crate

[vitiral]

This is based on the conversations referenced in #13

I want to try and have a conversation with the relevant crate authors/maintainers that create their own Array data types in rust. I would like to see if we can get an agreed upon basic data structure and API (Trait) for converting to/from the different types with zero* cost. This issue is intended to be the forum for those discussions. I'm hoping such an effort will be relatively easy and not limit the API's of each individual crate.

Once we get such a crate, we should document it on this site. I think telling the story of why there are different crates is really important because a lot of people expect rust numerical types have a standard in the same way as python does. If you can explain that the conversions are simple and basically free, then explain that they allow for useful features (like array multiplication with *) I think there will be a lot more support and the ecosystem can thrive with less friction.

This thread is for discussion on this topic and is open to anyone. Particularily welcome are the numerical library crate maintainers.

The proposed name of the crate from me is array-interop

* zero meaning no copying or moving (in memory) of the arrays, dimensions etc might be lost/gained.

[vitiral]

These requirements are subject to change per the discussion. I've chosen to create what I think are the most reasonable to get us started.

We will call the conversion trait TryFromArray, the base type Array and the conversion crate array-interop

The basic requirements are:

• converting shall not copy or move the array of data
  • having to create/delete dimension or lengths is acceptible -- although a standard shall be created so that crates with the same information can do a direct memory map (avoid creating a new dimension array)
• converting shall utilize the TryFrom trait in std
• each library shall only need to implement TryFromArray to convert to/from any other data types which implements that trait.
• the library shall use a struct which is interoperable with C for conversion with libraries outside of rust
• array_interop::Array shall be interoperable with numpy (not identical to their data type but zero-cost convertable into it with a bridge library), to allow interop with the the current state of the art in research languages.

Definition of Done:

• we shall set up a repository which implements the array-interop crate and agree to use it

[bluss]

• Need to think about version coupling and which way to organize this so that it works smoothly.
  • Does a numeric library for example depend on array-interop, or the other way around?
• A public dependency requires for a crate that it needs to bump the major version when the public dependency is version bumped
  • Public dependency: Types or traits of the dependency are used in the API of the crate
• TryFrom is neat but not stable which is a major drawback to it
• We want to have conversion of views or view-taking of a foreign data structure as well. For example rulinalg's MatrixSlice and ndarray's ArrayView are view types. (This could be covered by the same trait.)

[Andlon]

Thanks for bringing up the topic.

Let's make one thing clear first. Are we talking about interop for arrays (potentially multi-dimensional of many dimensions) or matrices (and possibly vectors)? Or stated differently, do we intend this to be an interop solution specifically for linear algebra or for storing data in multi-dimensional arrays?

[vitiral]

@bluss

• I would say the dependency would be similar to how serde works (albeit MUCH simpler). Numeric crates would depend on array-interop and implement the TryFromArray trait. I would argue it NEEDS to be this way, since many of the crates are going to want to hide the details of how their data is stored (they will be private) making it impossible for an external crate to access that information (part of the point of array-interop is to be able to expose this info in a standard defined API).
• agreed: any changes to array-interop will require a bump of the major version. Therefore it should be 1.0 before any of the array libraries use it in their master branches.
• I didn't realize TryFrom is not stable... we'll have to figure out something to do then.
• I didn't think about Views, that is extremely important. I've given a possible solution below.
• The other thing that needs to be covered (at least eventually, maybe not in 1.0) is sparse matrixes.

@Andlon: my understanding is that both 2D-Arrays and Matrixes typically store their data in the same way: a single long row-major contiguous vector. I think we should probably try to support BOTH row-major and column-major types as separate structs, possibly RowMajorArray and ColumnMajorArray. The crate author would then only implement FromRowMajorArray or FromColumnMajorArray (as the other would have a high cost of conversion).

In that way it doesn't matter whether the library treats the data as a Matrix or an Array -- the data is the same, only the operations are different. Looking at it another way, the functions/methods of each library might be different, but they are operating on data that is guaranteed to be in the same structure (and is therefore interoperable with very little conversion cost).

I think it is worthwhile to give a very, very basic overview of what the structs might look like (as I imagine them -- you are all more expert here than me):

struct RowMajorArray<T>{
    /// The data, stored in row-major order
    data: *mut T,
    /// The dimensions of the data
    dim: Vec<usize>,
}

ColumnMajorArray would have an idetical layout with a different name

the *View types would be the same but have a PhantomData<&'a T> attached to them to track their lifetime.

Notice that the data itself is just a mutable pointer whos length can be determined by self.dim.fold(|f, v| f * v) (multiplying the dimensions together), which saves us a usize. Probably we wouldn't want to use Vec for the dim field (and add a dim_len: usize) so that we can interface with nostd crates.

Also notice that this is the "simplest possible implementation." There are no type defined dimensions. The idea here is that creating/reading type dimensions introduces only a small cost and is worth it in order to have a common interop interface.

Again, this is a proof of concept to get the ball rolling. Please provide feedback as I am NOT the expert here.

[bluss]

I'm thinking of this as a conversion interface, so in terms of function parameters rather than a struct. Of course it could be seen as equivalent.

We will want to be able to convert data structures without allocating a vec for the dimensions. Fixed dimensionality types want to be able to implement the trait in a way that identifies a source of data of a particular dimensionality. The common case is one and two dimensional data.

my understanding is that both 2D-Arrays and Matrixes typically store their data in the same way: a single long row-major contiguous vector.

This is indeed the default memory layout of ndarray, but it is flexible. An owned array can be row- or column- major and (only applies if number of axes > 2) have other orderings of the axes as well. An array view can use custom strides for any axis.

Rulinalg has MatrixSlice which supports a custom row stride. As of this writing to my knowledge, ndarray can always represent rulinalg's data layouts but not the other way around. rulinalg can perfectly represent the default layout of ndarray's 1D and 2D arrays.

An illustration (picture) of how the strides work for the 2D case are in slide 7 and 8 of this old talk https://bluss.github.io/rust-ndarray/talk1/ I know there is no good accompanying description. This representation is used in linear algebra and other places to efficiently represent a cut-out from a larger matrix. (in ndarray, this is generalized to more dimensions than just two).