Should (array) view be an internal type?

The motivation for this post is to get some feedback on a potential solution to a problem discussed several times before. I have not seen this exact solution being discussed, but perhaps it is trivially bad without me realizing it. What I want answered is if it is worth pursuing the problem further or if by some detail of how the language or the compiler works it is inherently a bad idea.

The problem is concerned referencing a view in some larger array. I have attempted to structured the text to make it possible to skip the part of the problem formulation the reader is already familiar with.

Introduction

Today, the only viable way to create a view into an array is by defining a type that can act as a view reference. Let's use the struct below as a basis of discussion. An analog struct corresponding to a mutable reference must also be created, but the definition is omitted.

pub struct View<'a, T: 'a, const DIM: usize> {
    data: std::ptr::NonNull<T>,
    len: [usize; DIM],
    stride: [usize; DIM],
    phantom: std::marker::PhantomData<&'a T>,
}

This type will work fine to a large extent. Particularly it is possible to implement methods on the array type and View to index/slice/view parts of the array in several exotic ways. For an example of how this works in practice ndarray is great, although the corresponding view type in ndarray is a bit more complex it is conceptually the same.

Problem

The problem is not related to what is possible to do with these kinds of array views in Rust. It is purely related to ergonomics. But it is nonetheless severe enough that working with ndarray or any other dynamic array library in Rust feels out of place compared to other parts of the language. A lot of my initial expectations about how dynamic arrays in Rust should work is wrong. And I believe users familiar with the nice dynamic arrays from numpy or Matlab will be hesitant to use Rust for purposes where arrays are needed.

I have attempted to list up some of the ergonomics issue this

1. The Index trait

Since Rust's Index trait require returning a reference it is currently impossible to use indexing in Rust to create a view into an array. This require different methods to be created to compensate for the missing Index implementations. The solutions can be decent. but since "native" indexing is supported with much flexibility in specification in ranges for 1D arrays and slices, it is unfortunate that multi dimensional arrays cannot provide the same ergonomics.

Below is an example demonstrating indexing in ndarray compared to how it can be expected to work.

let array = ndarray::array![[1, 2, 3], [4, 5, 6], [7, 8, 9]];

// This kind of indexing is unfortunately impossible
assert_eq!(
    array[(0..2, 0..2)],
    ndarray::array![[1, 2], [4, 5]]);

// This is how view indexing looks like
use ndarray::s;
assert_eq!(
    array.slice(s![0..2, 0..2]),
    ndarray::array![[1, 2], [4, 5]]);

2. AsRef, AsMut, Borrow, etc

The same issue with Indexing also exists with these AsRef kind of traits. For arrays to work as a reference when using the Rusts stdlib types as Cow it is important these traits are implemented. One workaround is to define the layout of the array type as an extended version of the View, like shown below.

#[repr(C)]
pub struct Array<T, const DIM: usize> {
    data: std::ptr::NonNull<T>,
    len: [usize; DIM],
    stride: [usize; DIM],
    // The rest of the fields are omitted 
}

Now AsRef<View> can be implemented for Array by transmuting the reference. The big drawback is that the View layout need to be guaranteed stable, if not it is UB to use these methods. This means View and Array probably must be defined in the same crate, which is incompatible with problem #4.

3. AddAssign and friends

As discussed in [1] it is quite akward to use AddAssign and similar traits with Views such as defined above. Simply stated the intuitive way of adding a value to a column doesn't work.

// This does not compile
values.column_mut(0) += 1.;

The solution is quite unintuitively:

// This works but is not intuitive
*&mut values.column_mut(0) += 1.;

Even though we know that a View represents a reference to some Array there is no way to let the compiler know. If the compiler was aware that View was a reference it would be sufficient to write

// This works but is not intuitive
*values.column_mut(0) += 1.;

4. Implementing functions using views

In Rust, functions working on continuous arrays of memory can be general over a lot of different types. The important thing is that all these types can be referenced as slices. It would be possible to do the same for Views if everyone would agree on a single definition to use. Unfortunately this is not trivial as a requirement for implementing AsRef and friends (see #3) is that the layout of the slice definition never can change.

The motivation here is quite strong. Things like finite differences or image filters can be implemented once and for all in a function over a View instead for a specific Array implementation.

Previously suggested solutions

Generalize Index(Mut) to return proxy for references

This have been discussed in [2] [3]. The conclusion is that changing the Index(Mut) traits might be desirable when GAT support is landed. But even if it is desirable it is not trivial. The old traits can never be removed, due to backward compatibility. However, it is possible to get some future edition to point to new traits.

Even though this would fix #1 it doesn't automatically help with AsRef, AsMut, Borrow, etc or any of the other issues. This must therefore be considered a band-aid rather than a full solution.

Custom DST

Custom DSTs would be a great solution. This is previously discussed in [4] and [5]. Here, View would be the DST and a &View would be a (very) fat pointer incorporating stride and length information. This removes the need for a ViewMut as the mutability would be decided as in an ordinary reference.

This is a good solution to all of the issues. Unfortunately the full custom DST feature is not something that can be prioritized at the moment and the RFC is such postponed[5]. This is understandable as this array indexing problem is the main motivation of this feature.

The suggestion up for discussion

Instead of creating a full feature custom DST almost uniquely for solving this problem, we could create view as a native Rust type. We could either call it view<T, n> or something more in lines with the slice and array types like [n[T]]. Like for the custom DST solution View would be the DST and a &View would be a (very) fat pointer incorporating stride and length information.

I believe the main problem here is that a reference to a view would not simply be 2 x ptr_size but instead 1 + 2xn ptr_size. I have no idea how heavily rustc expects or optimizes on fat pointers being exactly twice the length of normal pointers, but this type would need to break this assumption.

Another drawback is that references are generally expected to be somewhat slim. A 4D view would be 9 x ptr_size. This might be acceptable due to there hardly being more efficient ways to represent these views and the overhead being quite expected when using Views.

What parts of the language have the same level of complexity and are handled more nicely? Most of Rust's large, comprehensive crates fair no better than ndarray (not to say they shouldn't) but this seems incongruous with my experience; it's not as though Rust's syntax and conventions makes things like implementing serde deserializers or tokio's async combinators trivial. Generic and efficient mathematical constructs almost always suffer representation issues which bubble up through the language's syntax. (Since mathematicians don't often design their constructs to be suitable for efficient computer representation.)

3 Likes

If you can stuff your pointer metadata into a single usize (which is actually practical on 64 bit targets, since you can use 2×u32 or 4×u16), you can get 90% of the way there and use &[mut] MyView, a la bitvec.

Any solution that actually feels good is inherently going to want to be a custom DST type, so that you can use &View, &mut View, *const View, *mut View, ptr::NonNull<View>, Box<View>, etc. Instead having to deal with ViewRef, ViewMut, ViewRaw, ViewOwned, etc. is a significant hit to usability.

Ultimately, I think the provision of a language-blessed View type is basically isomorphic to custom DSTs, but worse, because you're using View instead of the existing DST support and the composition of types that affords. Making View work the way you want will require solving all the same hard problems as proper custom DSTs, so I'd much rather go for proper custom DSTs once we've solved those problems.


In theory, the fact you can't .column_mut() += 1 is "just" a missing trait impl in ndarray. Consider also nalgebra.

For the "noncontiguous array" vocabulary type, consider the bytes crate.

6 Likes

Just to be precise, as I see it's ambiguously written. When writing "working with", I'm talking about using the library and not working on the library. I'm also not directly talking about how difficult things are to do, what strikes me with ndarray is the amount of weirdness in how the built in ops/traits work in even the most basic user facing use cases. I hope my answer is informative based on this.

Serde might actually be a good example to use. Implementing a deserializer is definitely not trivial, but I don't immediately see what kind of stdlib/language features you would expect to use without being able? Anyhow, the primary user facing use case for serde is to implement (De)Serialize on new types. This is lovely in serde as most types this can be derived in the same way you derive stdlib types. Even if you implement these traits yourself, the interface feels familiar based on std::fmt::Formatter. I would argue using the serde library corresponds well to rest of the language.

A different example of a library in the same category of things, although not as complex, is smallvec. Due to implementing the stdlib traits like AsRef<[T]>, Index, etc (and a lot of similar methods) it mostly feels like working with a Vec and can be used wherever a slice can be used.

I would also argue when using important libraries requires writing code that doesn't feel like Rust it is generally treated as a deficiency of the language. I believe async, Future and proc_macro are language/stdlib features added to make crates like serde and tokio feel more like the rest of the language. I'm not by any means claiming that numerics/data/scientific kind of programming is as important for Rust as web/async/network kind of programming (it is clearly not). But I'm not sure I agree that the weirdness of using Array/Views is acceptable.

1 Like

I'm not at all familiar with the compiler internals. I assume the main overlapping problem is the assumption on fat pointers being twice the pointer length? To what extent is this hard coded in the compiler?

I imagine finding, implementing and stabilizing an interface for DSTs would also be non-trivial. Do you consider this very little work compared to implementing support for fatter pointers?

I also consider the Array view type general enough to warrant a place in the language/stdlib. Custom DST would of course be nice as it would give the option of placing this type in stdlib instead of as a native type. But assuming that implementing View only requires some of the work required for full custom DST, it would perhaps open the door for custom DSTs being considered without requiring all the work?

I'm not so sure this is viable for all parts of a view. The problem is that the stride is not dependent on the size of the window but also the original Array. This means that even a small window could be impossible to create if the Array itself was large enough. A 2D view would need to use u16 for stride which is pushing it and a 4D view would need to use u8 which seems impossible to store the necessary stride information in.

I think this is correct as well. Improving the Index(Mut) traits would certainly relieve one of the ergonomics issues. But a fully satisfied solution requires a new DST (either as a native type or by creating it with a custom DST feature).

I'm sorry but I can't make it work. Here's my code and a playground link:

let mut a = nalgebra::dmatrix![1., 2., 3., 4., 5., 6., 7.];
    
// This works
*&mut a.column_mut(5) += nalgebra::dmatrix![1.0];
    
// This does not work: "cannot assign to expression"
a.column_mut(5) += nalgebra::dmatrix![1.0];
    
// This does not work as dereference is not possible
*a.column_mut(5) += nalgebra::dmatrix![1.0];

The second method could work if function calls were considered place expressions. But they aren't :frowning:

https://doc.rust-lang.org/stable/reference/expressions.html#place-expressions-and-value-expressions

2 Likes

My point was more that the Rust language doesn't even make it ergonomic to handle non-NaN floats or generic modular arithmetic, so I don't know where the expectation that generic multi-dimensional arrays should be neat and tidy is coming from.

I don't think you're going to do very well basing arguments of deficiency on feelings. There is no objective measure of how Rust is supposed to feel (or what feelings are 'Rust' feelings.) It's a toolset that operates in some manner. Introducing new language features directly changes what feels like Rust. Thus you are not proposing to make a library feel more like Rust, you're proposing to make the language more internally varied to support more surface uniformity. That's certainly a tradeoff worth considering, but it is a tradeoff, not simply something to be responded to according to a willingness to declare the language deficient because you feel like it.

(Uniformity is not in itself a goal. You wouldn't walk into a sand-paper factory and demand the paper be made smooth so as to be more useful as notebook paper, citing how rough it is on your fingers.)

3 Likes

I apologize if I have in any way appropriated what Rust is supposed to be. Perhaps deficiency was a bad formulation. Your formulation is more accurate than mine. It is the non-uniform surface that I experience as problematic when I'm using Rust with dynamic arrays.

My motivation is to use a Rust for scientific computing. A lot of these applications requires heavy computing and I believe Rust's performance and type-system can be advantageous in this domain. I find the inability to implement the stdlib and language features (like indexing) disappointing, and it is a big reason I can't wholeheartedly recommend Rust to my colleagues and collaborators.

I'm aware this is a tradeoff. If my proposal is obviously unacceptable I'm sincerely unaware and only bringing this up in good faith. I had never looked at the rustc source code before yesterday, so I'm completely clueless in regards to what the tradeoff actually is. That is the sole reason I made this thread, to ask persons knowledgeable about the rust compiler how big this tradeoff actually is.

I have referenced other thread discussing this issue as an annoyance and not accepted RFCs aiming to solve it. I made my best attempt to find previous discussion to this "middle ground" solution, but I couldn't find anything so i expect it to be novel or obviously bad.

In my almost complete ignorance it seems like a good starting point, after adding the View type in all relevant places, to update Ref in rustc_middle::ty::layout to return layouts longer than 2 ptr lengths. I assume after this is done things will start breaking and give some indication of to what degree the compiler actually expects DST references to be 2 ptr lengths. I'm not sure I want to go through this if the suggestion is unacceptable, which is again why I posted this thread.

I wasn't trying to argue that the proposal was unacceptable, just that the motivation should probably be clearer. I've tried to implement generic math libraries several times, and they all inevitably fall into disrepair due to 1) inability to optimize due to overly friendly interface choices, or 2) inability to be generic, due to overly strict internal requirements.

So it is not surprising or unexpected to me at all that working with ndarray is clunky, not because the language is deficient, but because they've chosen to tackle a hard problem, and presumably consider the clunky syntax to be worth the cost. You don't always need a generic array library, and there are multiple ways to implement them if you do, so I'm not convinced that a competing library couldn't do better by just making different choices. If they had just decided up front to not use these kinds of macros and traits, who's to say it wouldn't look like perfectly normal Rust with just a few extra function calls here and there?

1 Like

The biggest flaw with proposals to make indexing return a custom view type, as I understand it, is actually quite simple and fundamental: thing[index] isn't actually sugar for calling Index::index! It's actually quite complicated and very directly coupled to references and autoref rules, in that roughly:

  • thing[index] is typed as a place (rvalue) of type Index::Output.
  • If the place is used by mutable reference, either via autoref rules or directly taking &mut of the place,
    • IndexMut::index_mut is called.
  • If the place is used by shared reference, either via autoref rules or directly taking & of the place,
    • Index::index is called.
  • If the place is not autoref'd or explicitly re-referenced,
    • Index::index is called and immediately dereferenced by the compiler, initiating an (attempt to) copy.
  • (I have no idea how it interacts with ptr::addr_of[_mut]!.)

Any proposal to hook thing[index] syntax to return a GAT has to resolve how closely coupled it currently is to references. Note that returning custom DSTs suffer no such issue, as they work normally with composition via reference.

2 Likes

I think I better understand your feedback now. I will attempt to reformulate parts of the original post to make it clear that this is not related directly to ndarray. It is just used as a convenient example.

I initially expected it to be like you are suggesting, that ndarray sacrificed non-clunkyness for something more in line with its vision. After min const generics landed I assumed it would be possible to make something less clunky and I recently started working on my own experimental array library. It is made only with usability in mind, and nothing will be sacrificed due to performance (its after all mainly an experiment at this point). One of the core design decisions is that dimensions should always be known statically, so indexing a view will always give a view with one less dimension. This will allow to index a view similarly to a static array. This is how i imagined it.

// This code example does not work. It is impossible to implement such `View` type
let array = [[2, 3, 5, 7], [11, 13, 17, 19], [23, 29, 31, 37]];
let view = array.as_ref()[(1..2, 1)];
for i in 0..view.shape()[0] {
    assert_eq(array[1+i][1], view[i]);
}

But this is unfortunately completely impossible to my best knowledge. The closest I'm able to get is

let array = [[2, 3, 5, 7], [11, 13, 17, 19], [23, 29, 31, 37]];
let view: &View<_, 1> = array.as_view().i((1..2, 1));
for i in 0..view.shape()[0] {
    assert_eq(array[1+i][1], view[i]);
}

A different problem is that it requires an intermediate variable when creating a Cow from a static array. The result of this is that a Cow<View> can not be returned from a function as the the lifetime is tied to the intermediate variable. Maybe supporting Cow goes as a performance optimization, but it seems like a loss of user flexibility to provide both an owned variant and a reference type without allowing the user to use stdlib features expected from that pattern. Code example is below:

const ARRAY: [[i32; 4]; 3] = [
    [0, 1, 2, 3],
    [4, 5, 6, 7],
    [8, 9, 10, 11]];

fn main() {
    let view: View<_, 2> = ARRAY.as_view(); // <- The lifetime of cow is tied to this variable rather than the &'static ARRAY
    let mut cow = Cow::Borrowed(&view);  // <- This variable cannot be returned from a function even though &ARRAY is 'static
    cow.to_mut()[[2, 2]] = 14;
}

I can mention more problems. But they all seem to be related to the impossibility of returning references to views from rust arrays and custom owned dynamic array types. By themselves, each of this little issue feels non-important. But there are so many of them that it significantly worsen the experience when all of them is put together. Even when the dynamic array library is written with usability in mind.

I assume that means this new (non custom) built in DST will also suffer no such issue?

Basically it is of no importance that the following works

// This does not compile
values.column_mut(0) += 1.;

As long as functions are capable of returning a &View instead of a View the following is completely in line with the rest of the language.

*values.column_mut(0) += 1.;

And it does not need to interfere with returns being value-expressions and can still prohibit things like

vec.len() += 1.;

I had an RFC for an IndexGet returning an owned type somewhere, but I kinda shelved it due to lack of interest, and also because having it return a GAT would have strictly worse semantics than a custom DST due to lack of reborrowing, and also because there would be no distinction between readonly and mutable. In the end, it's a use case begging for Custom DSTs, which have been stalled since forever :frowning:

We've made some progress recently, though, with the rfc-approval of ptr::metadata. That finally gives us the prerequisite shared vocabulary to talk about what integration would look like.

5 Likes

Here's a short update:

I made some progress in my experiment of implementing the view type (Currently implemented with the syntax [T[DIM]]) as an built in DST where references are "fatter" than 1 ptr size of metadata.

Although my understanding of the compiler have somewhat improved by this experiment, I still don't understand the whole picture of what I need to be doing in the compiler. I'm therefore still highly interested in getting feedback on what I'm attempting to do.

My impression is that implementing a view as a built in type is significantly easier than supporting custom DST and might be interesting as an alternative. I suspect this is partially due to fully flexible layouts of refs is more difficult than just adding one more special case, and partially due to the amount of details required to get correct with custom DST compared to a relatively straight forward memory view type.

I only implemented the built in type and the following test on the size of the ref of this type:

#[test]
fn test_ref_size() {
    assert_eq!(std::mem::size_of::<&[usize[1]]>(), (1+1*2)*std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&[usize[2]]>(), (1+2*2)*std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&[usize[3]]>(), (1+3*2)*std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&[usize[4]]>(), (1+4*2)*std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&[usize[5]]>(), (1+5*2)*std::mem::size_of::<usize>());
    assert_eq!(std::mem::size_of::<&[usize[6]]>(), (1+6*2)*std::mem::size_of::<usize>());
}

I've looked into the core::ptr::Pointee, and I believe implementing this for the view is the next step towards actually implementing methods on the array view. Although I'm not going to do this before I've gotten some more feedback on the design itself.

The code where I've implemented the array view can be found here: Add view internal type to the compiler · kjetilkjeka/rust@5ae88fb · GitHub (The array view type is parsed as [T[DIM]] but is sometimes incorrectly printed/formated as [DIM[T]], This code is of course not created to actually being merged and It shouldn't be relevant for this little experiment)

@bluss sorry for tagging you in here if you're busy with more important things. But I would love to hear what you or someone else actively working on ndarray thinks about it. I realize something a bit more fleshed out design wise, perhaps a pre-RFC, is probably required to get feedback from a wider part of the community. But perhaps this is at an acceptable level to get feedback from someone working with exactly these kind of things?