Efficient memory usage in Rust

help
1

Hi all,

I'm writing some code to use as little memory as possible, but I'm somewhat unclear on some concepts of memory allocation. I have two main examples in which I'm not sure what the best approach is.

1. I have an array which stores information about a system of N (= const) particles; its coordinates (x, y, as f32) and label (first particle = 1, and so on). I was planning on storing the coordinates in a tuple, such as in the following data type:

[(u32, (f32, f32)); N]

But I wasn't sure if it would be more efficient in memory to store the coordinates as its own array of length 2 (since x and y are of the same data type), i.e.

[(u32, [f32; 2]); N]

Is there a significant difference between the data types, or are they similar in terms of memory usage?

2. I need to generate a 2D square matrix (of side A) of u32 values. This time, I wasn't sure whether to use a 2D array using ndarray, such as:

ArrayBase<OwnedRepr<u32>, Dim<[usize; 2]>>

or whether it would more efficient to declare the array as type:

[[u32; A]; A]

I also had a couple of memory usage-related questions, if possible. I assume it is generally more efficient to allocate arrays on the stack, than say, allocating a Vec on the heap? Are there any situations in which it would be better to keep variables on the heap, such as if the arrays are large? Thanks!

2

No difference. [f32; 2] and (f32, f32) have the same layout in memory: The two elements are simply stored adjacent to each other, with no padding or other overhead.

The two representations you list here have more or less equivalent layouts. The main differences are:

  1. The ndarray type always allocates its storage on the heap.
  2. Built-in arrays [[u32; A]; A] have lengths that are known at compile-time, which might help with certain optimizations, especially when A is small.

This depends a lot on your use case. Using a heap type can be more efficient if you want to move ownership without copying the entire matrix to a new location. Also, space on the stack is much more limited than the heap.

In general, yes, the larger the array, the more likely it is that you will want to store it on the heap.

8 Likes
3

Maybe you could save some memory by not storing the label in the array? Are the labels just consecutive integers?

1 Like
4

An important caveat here is that while the layout of [f32; 2] is guaranteed to have that layout, (f32, f32) is not and it could change at any time, e.g. it could have extra padding bits or store the floats out of order.

7 Likes
5

(See also UCG 36.)

1 Like
6

A workaround for that is to guarantee the layout by defining a #[repr(C)] type for the coordinates, rather than using a tuple.

1 Like
7

Is it? C guarantees that the ordering of struct members is the source order, and that there’s no padding before the first member, but allows arbitrary padding otherwise. In some hypothetical 64-bit system a struct x(f32, f32) might be padded and aligned to 2x64 bits, whereas a [f32; 2] is still guaranteed to be exactly 64 bits.

8

Rust has quite precise guarantees about the #[repr(C)] annotation. You can find them here.

The alignment of the struct is the alignment of the most-aligned field in it.

The size and offset of fields is determined by the following algorithm.

Start with a current offset of 0 bytes.

For each field in declaration order in the struct, first determine the size and alignment of the field. If the current offset is not a multiple of the field's alignment, then add padding bytes to the current offset until it is a multiple of the field's alignment. The offset for the field is what the current offset is now. Then increase the current offset by the size of the field.

Finally, the size of the struct is the current offset rounded up to the nearest multiple of the struct's alignment.

2 Likes
9

If you come from a java / python / javascript backend, you may also be surprised to know that the following types does not imply any extra run-time or memory-size cost compared to the array or tuple variants:

struct Coord {
    x: f32,
    y: f32,
}

struct Particle {
    label: u32,
    pos: Coord,
}

In more "dynamic" languages, code like this may imply separate vtables and that a Particle is two separate heap allocations (one for the particle itself and one for the pos), but in Rust the memory representation of a Particle is the same¹ as for the tuple (u32, f32, f32).

Note 1

The same, that is, except for possible differences in alignment and padding. In this case, I don't think there would be a difference, but e.g. if the y coordinate would be an f64 (while the other fields are typed as above), a Coord might be eight-bytes-aligned and either be reoredered so y comes before x or contain four bytes of padding. Then the Particle may become 4 bytes label + 4 bytes padding + 16 bytes padded Coord giving 24 bytes total, or the compiler might be able to reorder it as 12 bytes of Coord immediatley followed by 4 bytes of label making 16 bytes in total.

The rules for padding and alignment is rather complex, and I don't really know them. I don't think you need to know them either, but in cases where size is important it may be a good idea to check, maybe by asserting your expected type sizes.

5 Likes
10

Thanks! So #[repr(C)] guarantees a C-compatible layout, but actually goes further than that in what it promises.

11

C does have such precise guarantees about its struct layout. #[repr(C)] goes further on things which doesn't exist as-is in C like ZST and enums with associated data, but for boring types like struct with integers/pointers it's pretty much "what C does".

6 Likes
12

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.