The generics trap

[lubomirkurcak]

I decided to write my own N-D array implementation using generics for the number of dimensions:

pub struct ArrayNd<const N: usize, T> {
    shape: [usize; N],
    data: Vec<T>,
}

I wrote a maze generation algorithm and realized it cleanly generalizes to N dimensions. Examples:

10 x 10

Array2d (21 x 21)

2 x 5 x 5

Array3d (5 x 11 x 11)

slice [0, .., ..]

slice [1, .., ..]

slice [2, .., ..]

slice [3, .., ..]

slice [4, .., ..]

That's pretty cool! Let's let users specify these dimensions from the CLI, I thought.

I added clap with a Vec<usize> param and then it hit me. Since my type is "generic" and compiles to actual constant-size instances, I will not be able to do this.

A solution would be to remove the generic N and rewrite the library to something like:

pub struct ArrayNd<T> {
    shape: Vec<usize>,
    data: Vec<T>,
}

That is a lot of work, loses compile-time checks, and is not even zero-cost.

I got an idea, why doesn't Rust provide a feature for "unspecified" or "run-time" generics? All unspecified parameters could be Boxed and you could only have a single compiled type for "run-time" use cases. (Of course, there could also be "half-specified" types.)

I would like to hear your opinions:

• Would "unspecified generics" be possible?
• Would "unspecified generics" be feasible?
• Are there other options that I'm missing?
• Have you encountered a similar situation?
• Have you ever felt a little disillusioned about generics?

Thanks for reading and replies.

[Cerber-Ursi]

@lubomirkurcak

why doesn't Rust provide a feature for "unspecified" or "run-time" generics?

In other words, why doesn't Rust have dependent types?

[a-rust-coder]

Well, actually, the purpose of generics is to quickly and easily derive variants of a type. If the compiler was allowing "unspecified" or runtime generics, it would be incredibly costly. This because when you have a generic, all the used variants of the type (Vec<usize> and ArrayND<5, bool> for example) are built. If you have the following type for example:

struct Array<const N: usize>([(); N]);

And in your code you use Array<1>, Array<2> and Array<3>, this is equivalent to having three types, like Array1, Array2 and Array3 for example. Knowing that, the compiler can perform some optimizations, and technically handles this as three different types.

So, now, let's have a look to what you suggest: you want to have N unknown at compile-time. Totally unknown, it means any value between 0 and usize::MAX, which is typically 2^64. If we keep the actual compiler behavior, you will need to have 2^64 variants of the impls, and to create it, you can't match over the runtime provided N. It means the simplest way to create a new value would be to implement From<Vec<T>> for Array<N>, for every N, and then store the function pointer on a 2^64 long array. It means... 128 exbibytes (EiB) of memory.

So, with the current compiler behavior, it's totally unrealistic.

Now, how could we do that? Well, in our case, it would be necessary to create a struct which allocates memory on the heap, because a value of an unknown size can't be passed on the stack or through registers. The struct should store his size, and avoid modifiying it. Generics cannot be used here, because the main point of a generic is compile time optimizations. In other words, it's... a Vec, with a static size.

So, yes, it would be possible, but no, it wouldn't be feasible (excepted if you have a very very very big RAM).

In your case, I'm afraid the only way is to use a Vec (or equivalent). You can have a wrapper around it so it has a static size. It's not very costly, because you can allocate the total size of the Vec when you create it and never change it. Other possibility if you really want to keep the generic, you can implement a trait for the type, then create an array of function pointers to create this object and return a Box, and limit the range available to the user. But actually, a Box isn't less costly than a Vec, even more, because if you want mutability you have to use an extra type inside (like Mutex, RwLock, ...).

For the personal story, no, I've never encoutenred situation like yours with dynamic generic need, but I 've frequently encoutered similar problem where a feature of the language let me think I could do something, but finally it wasn't possible. But I've never felt disillusioned, because I never found a problem that couldn't be solved in Rust. I've always found solution: sometimes it was a macro, other times my design or my architecture wasn't adapted, but I never got stucked.

[kpreid]

It's possible to use generics in a way which allows both statically and dynamically chosen dimensionality. Something like:

trait Shape {
    // methods for translating to/from linear indices and so on
}

impl<const N: usize> Shape for [usize; N] {...}
impl Shape for Vec<usize> {...}

pub struct ArrayNd<S, T> {
    shape: S,
    data: Vec<T>,
}
impl<S: Shape> ArrayNd<S, T> {...}

Then you can use either ArrayNd<[usize; 2], T> or ArrayNd<Vec<usize>, T> depending on the needs of the specific application. I believe this is broadly similar to how ndarray does it.