How to memmove to shift an array in rust

Hello

Pursuing my journey on Rust i tumble on a pickle.
I need to make insertion on a very large array at a spectif index (to keeps the array sorted).

In c i would have proceed as such

int64 array[612352];
int size; // representing how much the array is flled yet
// ...
// index is where we will, after shifting, add the new item
memmove(&array[index + 1], &array[index], (size - index * sizeof(array[0]));

Knowing that speed is important, how can i perform a similar operation in rust ?

You can use slice::copy_within.

5 Likes

Also, for an array that long you probably don't want to have it on the stack, and thus the better answer is probably https://doc.rust-lang.org/std/vec/struct.Vec.html#method.insert.

4 Likes

Thanks for the answer,
I've checked the doc but can't figure out how to use in my case ?
Somehing in the line of (keeping the same variable name as in the C example ?

array.copy_within(index.., index + 1);

The aim is an executable that will build a binary file, so the program won't live long (juste the generation time)

Since array/stack allow faster manipulation than Vec/heap, if i've understand correctly will it really be an issue?

It doesn't allow faster manipulation; once you have it it's just memory.

Stack is just cheaper to acquire and release -- and that makes a big difference for something like a short-lived [u8; 3]. But you have a 4 MiB array that's (presumably) long-lived. In comparison, the default stack size for a thread in Windows looks like it's 1 MiB. So saving one heap allocation for something that big is not at all worth it when you're massively increasing your chances of panicking for stack exhaustion.

(And, as a bonus, Vec has methods for exactly the "insert at this position" that you're trying to do.)

3 Likes

Thank you :wink:

1 Like

If you need to maintain a sorted order efficiently, you should consider using BTreeSet rather than Vec. BTreeSet is a much better data structure for this, it doesn't need to move everything in memory just to insert one element.

4 Likes

I think you only wanted to move index..size -- if you tried to move all index.. forward then the last entry would move out of bounds, which is a panic condition.

1 Like

Didn't klnow about it thanks, but won'y be able to use it since I need acces to the indexes and it seems i can't do that with BTreeSet's.

With vector you are moving hundreds of thousands elements just to add one. That's extremely inefficient and allocation speed is not a problem compared to that.

Technically rope should be able to do what you want, but I'm not sure any implementations for Rust.

Depending what you need the indexes for, also check out IndexSet in indexmap::set - Rust

1 Like

Learning a lot but i think Vec is the solution
I need both be able to retrieve indexes and to insert at a specific index (keep it sorted as i fill the array)

Keeping in mind that you mentioned the program is run infrequently and doesn't live long, and O(n²) over half a million elements just isn't that big a deal - around a minute worst case.

If you do find the input to it growing and speed becoming an issue, "roll a rope type" sounds about right. Even a single level "vec of vecs of 512-1024 elements, which are split down the middle on overflow and - if relevant - coalesced with half/all of an adjacent vec on underflow" should put tight bounds on number of bytes shifted on insert, and you can convert to/from usize abstract indices by summing over component vec lengths.
(Optionally maintaining a cumulative-sum array as you shift things, possibly in a weird shape like "for every index multiple of 1024 which vec does it end up in", depending on what the index-retrieving inner loop wants.)