Semantic 2D-Matrix of Indices / Memory Layout

Dear all!

I am thinking about a nice data structure to represent meshes/polygons, which are basically read-only, after they are created once. So I won't be facing any re-allocation issues.

An example: I have a list of points in 2D, points = [[0.,0.], [1.,0.], [0.,1.], [1.,1.]] and a list of triangles, which saves the indices of the vertices, i.e elements = [[0,1,2], [3,2,1]].
However, a quad would have 4 vertices, pyramids 5, etc. This number is given at compile time.

In Python, Matlab or similar languages, I would just use a matrix (numpy, or whatever) for everything. However, it was pointed out to me that I "loose semantics" this way. Now I want to make use of Rust's typesystem as much as possible without loosing performance.

My first thought was to introduce something like this

type Id = usize;

struct Polygon<const N: usize> {
    data: Vec<Id>
}

and then have a elements: Vec<Polygon<N>>. But then I would basically have a Vec of Vecs, which is bad for CPU caching.
But how about arrays?

struct Polygon<const N: usize> {
    data: [Id; N]
}

Would elements: Vec<Polygon<N>> layout everything continuously in memory? As far as I understood, it would, which is a little bit counter-intuitive for me, since I've always thought that arrays are also pointers (like in C).

Or would even elements: [Polygon<N>; n_polygons] be better? If so, would there be any difference, if I used Box<[Polygon<N>; n_polygons]>? This way, the data would be on the heap, which is apparently caching-friendlier than the stack?

Thank you very much in advance!

Best,
welahi

Arrays aren't exactly pointers in C, but they do have "array decay" where attempting to pass them by value will pass a pointer to the array instead, etc. But Rust isn't designed that way, and you can pass them around without losing their size or count.


I think you basically have everything right:

  • All the T are layed out continuously in both [T; N] and Vec<T>
  • All the T are layed out continuously in both [[T; N]; M] and Vec<[T; N]>
  • You could use Box<[[T; N]; M]> instead of [[T; N]; M] to store it on the heap

As for which is better, I suspect Box if these could be any size at all (just so they're quicker to move around), but as always it would be better to measure and see.

2 Likes

Thank you very much!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.