Why does VecDeque<T> waste space by design?

239 points Sp00ph

A while back I noticed that VecDeque::new isn't marked as a const fn, which seemed a bit weird to me, as by now all other collections have const fn new()s. When digging into the code, I found a few oddities:

  • VecDeque::new eagerly allocates, which doesn't seem to fit the spirit of rusts lazily allocating collections.
  • The buffer of a VecDeque seems to always leave one space free, growing one item before the buffer is full and not when it's completely full (unlike Vec<T>).
  • The size is always a power of two, to make the wrapping logic simpler, which means that e.g. VecDeque::shrink_to_fit can actually still leave up to almost half the buffer empty.

The reason for the empty dummy slot seems to be that VecDeques keep track of their head and tail internally, and that its head always needs to point to actual allocated memory, and can't just dangle (I think?). Naturally, I decided to completely write my own Deque implementation to prove that this wastage isn't necessary, which instead of keeping track of head and tail, keeps track of head and len, and allows the buffer to be completely empty. This way, all of the above points can be addressed nicely:

  • Because the buffer can be empty, Deque::new doesn't have to allocate and can be marked as a const fn.
  • The dummy slot isn't necessary in my implementation, as i don't keep track of head and tail, but instead of head and len.
  • The size doesn't need to be a power of two, as it's still possible to implement the wrapping logic without branching (it's written as an if-else, but llvm optimizes to to cmov on x86-64, and even without conditional moves it's easy to replace the branch with simple bitmasks), which means that e.g. Deque::shrink_to_fit can actually always shrink to the minimum required size, instead of the next power of two.

My implementation is close to feature-complete, afaik it's only missing try_reserve()/try_reserve_exact() and some std-specific stuff that isn't possible to use in a normal rust program. If you're interested, here's the code:

Playground

GitHub Gist

I'm reasonably sure my implementation is correct (did some fuzzing), and from what I've seen, it performs similarly well to VecDeque, so my question is, is there any actual reason for VecDeques limitations mentioned above, or is it just this way because the first person implemented it like this?