arraytraits.md

Status quo

Currently the AbstractArray type hierarchy has three major subtype trees:

• DenseArray
• AbstractSparseArray
• AbstractRange

In addition, we have the StridedArray typealias, which effectively “adds” strided SubArrays and ReshapedArrays as pseudo-subtypes of DenseArrays.

We also have the IndexStyle trait.

The current behavior of similar itself could be refactored into a trait-like function (return the type of an unallocated, mutable array, but that would then also require a consistent constructor interface).

Prior discussions

• #10064: Toward defining the interface of AbstractArray
  • Really good examination of complexity guarantees of Strided, Ragged & CSC arrays
  • Also references the excellent gist: JeffBezanson/what_is_an_array.md
  • Very helpful in defining bounds on what is not an array
• #18161: Similar and traits
• #10889: iscontiguous function or trait
• Many more...

Dimensions of variance

We needn’t support all of these options, but we should be aware of them. In fact we should punt as much as possible, provided that we allow for later specializations where it’s crucial.

Shape

I think we should simply demand that all AbstractArrays must be rectangular, with ordered and sequential (AbstractUnitRange) integer indices. Anything else is more like a generic associate collection.

Storage

• Stored: all elements exist within a single chunk of homogenous memory
  • Strided: all elements exist in memory at regular, computable offsets with stride
    • Contiguous
    • Storage order: strides are strictly increasing or strictly decreasing.
  • Distributed: the array is spread across heterogeneous memory regions; some are faster to access than others. Maybe some are not available at all?
  • “Sparse”: some elements exist in memory, others are a constant value. We may want a different word for this since Sparse Array is a more specific term of art.
    • Structured: only specific locations in the array can be stored (e.g., Diagonal). Issues like #17670. This isn’t entirely orthogonal to mutability.
    • Sparse/Compressed: any locations in the array can be stored (e.g., CSC, COO)
• Computed: no elements exist in memory. Is there a valuable distinction to be made between a purely computed array and a MappedArray?

MappedArrays are tricky — they’re computed but you’d want a MappedMatrix{conj, Array{T,N}} to be a strided matrix for BLAS consideration.

Mutability

Could have the full product of all/some/none + readable/writable.