SmallVecDeque — small vector optimization for a ring buffer

[kotauskas]

Vec and VecDeque are similar in that they both use the same allocation method; they just use the allocation differently. With MaybeUninit<T::Item> and some additional ring buffer management, implementing a SmallVecDeque should be pretty simple.

[ghost]

I think so. There are often times when we want a deque that only contains 1 or 2 elems for the most time.

[mbrubeck]

Similar to issue #220, I think I would prefer to see this as a separate crate, built on top of the smallvec crate if appropriate.

[fleabitdev]

Assuming SmallVecDeque is implemented similarly to VecDeque, I can see a few challenges:

• At least one element is always unused. For a small inline buffer, this seems wasteful.

• The buffer length must be a power of two, so SmallVecDeque<usize, 10> would store either eight or sixteen inline elements. It might be better to completely forbid non-power-of-two sizes.

• The capacity is one less than the buffer length. Either SmallVecDeque<usize, 3> would store four inline elements, or SmallVecDeque<usize, 4> would have an inline capacity of three. Users might unexpectedly upgrade to the next power-of-two buffer size, or unexpectedly spill from inline storage to heap storage.

It might be worth experimenting with an entirely different ring-buffer algorithm for SmallVecDeque, rather than porting VecDeque directly.