pub const DEVELOPMENT_NOTES: ();Expand description
A discussion of the approach, alternatives, trade-offs and context.
§Alternative design: multi-dimensional slices
We limit ourselves to 2-dimensional slices here. This avoids two major
complications. Potential allocations within the ‘tag’ portion of the
reference would make this metadata incompatible with Copy semantics, required
for the unstable custom-unsized type design that we want to be compatible with
in the future, as well many forms of const manipulation, which forbid
dropping generally. Additionally, higher-dimensional slices would require us to
be more cautious with manipulations that are trivial for 2-element vectors but
may be non-(log)-linear in higher dimensions. All that would introduce
additional decision points and jump that likely affect codegen. We rather solve
one problem well at a time.
§Alternative design: strided slices
A more general solution to the problem of multi-dimensional slices is to use two separate explicit strides for both dimensions of the matrix. The position of an element is then computed by the inner product of the index vector and the stride vector (or a homogeneous version with an offset). This representation makes transposition trivial.
However, the flexible stride in both direction implies that we can not rely on either direction having contiguous elements. (That is, to a degree, the point). We could now longer offer an conversion to row iterator of element slices, which also implies quite some performance penalties for all operations that would be dependent on it. This more general design may be worth exploring in addition to the denser matrix design.
§Alternative design: byte strides
Instead of storing the offset of a block in number of elements we could also
store all strides as a number of bytes. The pointer offset operation would work
practically the same, just moving the scaling operation. We would have an extra
invariant to maintain as all references must be well-aligned which is not
guaranteed by arbitrary byte offsets. As a consequence, the type used for the
pointer tag is not by itself a sufficient description. Its validity would also
depend on the element type T for which it is used.
We’d either want to provide a different generic-over-T tag type or need to
annotate several operations with the type. This would complicate the design and
split up the responsibility of maintaining the unsafe invariants across more
locations. Hence we stay with element-based offsets which mirrors the standard
library choice of representing slice lengths as usize in terms of element
count; not in terms of memory size.
Still this design may be worth exploring. Several real-world matrix types pad
their rows in a way that they are not guaranteed to be multiples of their
element size, but highly aligned. For instance, a row of [f32; 3] elements
may always be padded to a multiple of 4 f32 elements. This pseudo-3d matrix
appears in several image processing contexts and byte strides are the more
pragmatic way of approach it, rather than making the matrix generic over both
element and underlying type.
§Additional design: sparse matrices
Sparse matrices are very often expressed as a set of three arrays (CSC format):
a slice of raw elements, a slice of row indices, and a set of column offsets.
Accessing an element uses two indirection lookups, first we compute the number
and index of elements in a column from the column offsets at i and i+1,
then retrieve the sorted row indices and corresponding raw elements by indexing
the two other matrices with the offset range.
Slicing such a matrix into blocks is possible as long as the set of present elements can not change. Computing the range of allowed elements for a column is a binary-search within the row indices to determine the lower and upper bound indices. We must not slice into the element array with any larger indices to avoid undefined mutable aliasing with other blocks. As an iterator design this might make sense, very similar to the design of a dense slice. Having no modification for data indices is a bummer, though insertion and removal being separate steps comes with the representation so this may be fine.
An additional trickiness here would be the types allowed for the index slices.
While we might natively want to default to usize, smaller and
platform-independent types such as u32 or even u16 will be desirable in
practice. Unlike the sized length tuple we can not expect a conversion to
always be possible though. Hence the type would need to be generic and that
combination of generic types with critical safety requirements to their value
interpretation would warrant extra care in the implementation. We can’t trust
user-chosen types to maintain the sortedness property critical to row
non-aliasing without an unsafe or sealed trait—neither of which appear to be
super ergonomic choices in the interface. If you need to have unsafe lines
anyways, the motivation to this library goes down quite a bit.
§Footnotes
¹Technically, the sharing predicate / invariant depends on the pointee type but
access is closely guarded to most code. To crates, stable Rust provides one
escape hatch in the form of UnsafeCell<T>, which allows shared mutation, and
your own types can only make use of this through composition (fields in
struct, enum, and on nightly within union). Additionally, any operation
that such a custom type implements must still conform to the requirements of
the underlying type’s operational semantics and thus sharing predicates if
references to it are involved.
²In contrast to C++ where T* and T const * are both ‘pointers’ but have
pointee types that differ in their qualifiers. So while they are distinct
on a type-level (including type mismatch shenanigans with decltype(auto)) on
an operation semantics level this is more permissive than the Rust model, and
we can const_cast the difference away as well as undo its recursiveness for
fields by setting them mutable (only class fields though, not arbitrary
places such as parts of an array). Hence, the compiler can distinguish and
optimize only in a very limited number of cases. Also programmers can
accidentally introduce paradoxical T const&& types in their programs, which
contributes significantly to a quirky and lighthearted work environment.
The mantra seems to be: the clearest way of letting people know you are taking
control of a resource is to explicitly say you’re copying it (/s, summarized
from this gem). Also you know need to
explain what it means to return a const T as a separate type from returning a T even though
returning is maybe the most common way of initializing a totally non-const value. I suppose
the analogy of buying a house that you’re not allowed to modify
is more hilarious in Germany (see UrhG §1 (1) No. 4).