Hacker News new | ask | show | jobs
by taco9999 457 days ago
What benefits does this have over a standard VecDeque?
2 comments

The elements are completely contiguous, which can be nice for passing off (subslices) to other APIs, maximum speed iteration, etc.
Does 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?
Both 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?
I'd love to see performance numbers for this, if they're available. My hunch is that indexing cost would be about the same.
They 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
There are many situations where those little differences completely vanish because of instruction pipelining. Only way to know is to actually measure it.
>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.

For context: a VecDeque is a ring buffer backed by an array.