Equivalent to C++ std::deque?

Hi,

I need a container that won't try to reallocate because I will insert a huge number of elements in it.
In C++, I use a std::deque because it enables to have "islands" of memory that point to each other and never move in memory as long as they have one element.

In rust, VecDeque uses a -growable- ring buffer so it doesn't qualify, memory has to be contiguous.
Using a linked list with nodes as Vec seems like the closest strategy right now but it's manual and requires some code of mine to manage the jump calculations (easy, but don't wan't to).

What would be the "best" container/crate to achieve this ?

You could create a Vec<Vec<T>>, and make sure the inner vectors only receive as many elements as their initial capacity. This is similar to the strategy which typed_arena uses.

3 Likes

Nice,
will do this !

There is also chunked-bytes but I'm not sure if it's still maintained.

1 Like

Looks good as well! Thanks yyogo!

Feel free to share more about your motivation. You say “I will insert a huge number of elements in it”. But that’s hardly giving justification. Is it about performance? Modern OS should reallocate large amount of memory very quickly. Growing even a multiple GB large Vec on my laptop takes less than 10ms, compared to the full seconds it takes to actually copy similar amounts of data.[1] As far as I’m aware, the operating system can move the data in virtual memory very quickly by just readdressing full pages at a time.

More often than not, the best container in Rust is just simple plain Vec. Make sure you at least measure that any actual work you do with your data structure doesn’t suffer a lot more from the overhead on every single element access of using something with multiple indirections like Vec<Vec<T>>, compared to the tiny overhead of reallocations.

As far as I’m aware the main (or perhaps only) motivation for std::deque in C++ not to move elements is that in C++ moving values can have more overhead and be more undesired (due to pointer invalidation) than in Rust, where the borrow checker doesn’t really allow datatypes that cannot freely be moved. Unless of course in case your motivation here is that you need do not invalidate pointers, i.e. you’re writing unsafe Rust, and thus have motivations e.g. similar to why typed_arena works the way it does.


Note that you didn’t say much about your use-case. If you actually need double ended queue functionality, then I haven’t tested whether or not VecDeque can profit from efficient reallocation in the same way – and I’d assume perhaps it can not because the data at the tail of the ring buffer would be copied normally. So if that’s your use case, then something more chunked might still be more useful…[2] (also presumably in case of double-ended-queue style access, the double indirection could be avoided).


  1. And by the way, with the typical doubling strategy, reallocations only happens so rarely, that asymptotically it wouldn’t even matter if they weren’t this insanely quick. ↩︎

  2. the argument of asymptotics still applies though… as mentioned, measureing the performance is always the ultimate way to determine what’s best ↩︎

4 Likes

Yes, you are right, the chunked approach is to make sure we can allocate as much as possible on possibly limited devices.

On our beefy servers, I would care much but we had a situation where too much contiguous memory led to a crash (on limited resource devices). The goal is to have a service as stable as possible no matter where it's run (wasm or native rust).

You are right, my question was out of context and I hope I corrected that.

We will use a Vec<Vec<>>, it should get us far enough.

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.