5 ms·
What benefits does this have over a standard VecDeque?
by taco9999 2y ago
What benefits does this have over a standard VecDeque?
- orlp 2y agoThe elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
- ufo 2y agoDoes it have to move or resize when one of the sides reaches the end of the array? I presume that would be slower than a ring buffer that only grows when it's completely filled?
- manwe150 2y agoBoth are O(1) datastructures, but indexing a ring buffer is slightly more costly compared to this and insertion is slightly more costly for this than a ring. Probably usually works out in favor of this design though for net performance usually?
- ufo 2y agoI'd love to see performance numbers for this, if they're available. My hunch is that indexing cost would be about the same.
- manwe150 2y agoThey both have an offset, but ring buffers aren’t contiguous so they also need a branch or modulus to handle wrap around. Either can be cheap, but clearly that is strictly more costly than not having the extra operation (even if very little). Only matters for random indexing also, since for mutation the situation is swapped
- ufo 2y agoThere are many situations where those little differences completely vanish because of instruction pipelining. Only way to know is to actually measure it.
- Arnavion 2y ago>Does it have to move or resize when one of the sides reaches the end of the array? Yes, it resizes when that happens, to double the size.
- ufo 2y agoFor context: a VecDeque is a ring buffer backed by an array.