Improve `VecDeque` implementation

[joboet]

VecDeque currently allocates one extra empty element because it needs to discern between an empty and full queue. Besides wasting memory, this means VecDeque::new cannot currently be const.

Solution

The most elegant solution would be to reimplement VecDeque based off the (third) technique described by Juho Snellman in this blog post. In this implementation, the buffer indexes are not clamped to the buffer size, but instead use the whole range of usize. Only when accessing an element are they masked to fit. The length of the buffer is defined by the wrapping distance between the two indexes. By limiting the capacity to values smaller than isize::MAX (which Rust's memory model dictates anyway), an empty queue (with head == tail) is strictly different from a full queue (where head - tail == capacity).

In the described implementation, the capacity is always be a power of two so that wrapping arithmetic can be used. This is great for performance and simplifies the implementation, but may result in significant unused memory when a large but precise capacity is required. Therefore, Eli Dupree proposed a variation where the indexes are kept smaller than 2 * capacity using modular arithmetic, which would relax the above requirement but incur higher runtime cost since the more expensive modular arithmetic needs to be used.

Links and related work

• Previous discussion on Rust Internals

@rustbot label +T-libs +T-libs-api

By limiting the capacity to values smaller than isize::MAX (which Rust's memory model dictates anyway), an empty queue (with head == tail) is strictly different from a full queue (where head - tail == capacity).

Note: That limit is for isize::MAX bytes. You can handle an array of usize::MAX ZSTs just fine. And indeed, Vec handles it fine.

But it seems like VecDeque::<()>::with_capacity(isize::MAX + 1) fails already, so that's not a breaking change.

[joboet]

By limiting the capacity to values smaller than isize::MAX (which Rust's memory model dictates anyway), an empty queue (with head == tail) is strictly different from a full queue (where head - tail == capacity).

Note: That limit is for isize::MAX bytes. You can handle an array of usize::MAX ZSTs just fine. And indeed, Vec handles it fine.

But it seems like VecDeque::<()>::with_capacity(isize::MAX + 1) fails already, so that's not a breaking change.

Since the size is known at compile, ZSTs can be checked for without any performance hit. Also, since their address and order is irrelevant, it should be possible to use just one of the indices as counter for the number of elements, which should make operations faster.

[leonardo-m]

Let's keep in mind the sequence of implementation bugs that have being found in VecDeque. It's one of those situations where having a formal proof of code is useful.

[workingjubilee]

VecDeque currently allocates one extra empty element because it needs to discern between an empty and full queue. Besides wasting memory, this means VecDeque::new cannot currently be const.

It is intended that const capabilities expand to allow expressing this. Redesigning VecDeque around this limitation, if it would affect correctness, doesn't seem necessary.

[joboet]

VecDeque currently allocates one extra empty element because it needs to discern between an empty and full queue. Besides wasting memory, this means VecDeque::new cannot currently be const.

It is intended that const capabilities expand to allow expressing this. Redesigning VecDeque around this limitation, if it would affect correctness, doesn't seem necessary.

The implementation in the blog post does not have any known errors, so correctness is not affected. On the other hand, even if VecDeque::new could be made const with the current design, the issue of over-allocating would still persist. Additionally, with the proposed variation, conversions from Vec would be essentially free.

Let's keep in mind the sequence of implementation bugs that have being found in VecDeque. It's one of those situations where having a formal proof of code is useful.

Definitely, but I do not think that this should block the usage of an objectively better implementation.

[the8472]

Therefore, Eli Dupree proposed a variation where the indexes are kept smaller than 2 * capacity using modular arithmetic, which would relax the above requirement but incur higher runtime cost since the more expensive modular arithmetic needs to be used.

We could even check if the capacity is a power of two and then do masking and otherwise do modular arithmetic.

But imo that should be done separately from allowing non-allocating VecDeque::new since that should be much simpler.

[mqudsi]

Just a point: the solution proposed by Eli Dupree was actually originally proposed by dizzy57 in the comments on the original jsnell article on 2016-12-14.

@the8472 I don't think it would make sense to check the capacity and then use one of two methods depending on if it's a power-of-two or not: that's additional branches, more code complexity, etc all to avoid some integer math.

[the8472]

I would hope those branches branches are well-predicted and cheaper than divisions.

[Sp00ph]

I wrote this reddit post yesterday, and got some replies saying I should maybe comment on here so here goes nothing:
I've written a Deque implementation which should be basically a drop in replacement for alloc::collections::VecDeque, which allows for empty buffers (so Deque::new can be const fn, and Deque::from(Vec) is a free conversion), and also allows for non-power of 2 capacities, which means Deque::shrink_to_fit can actually shrink to fit.

I've done some differential fuzzing, comparing my implementation against the std VecDeque, and I'm reasonably certain my implementation is correct.

I've also run the VecDeque benchmarks on my Deque (courtesy of https://www.reddit.com/user/jrf63/ who ported the benchmarks), and it seems most operations are similar in speed, if not a bit faster for my Deque. One exception is the extend_chained_trustedlen benchmark, where for whatever reason, VecDeque is almost 10x faster than my Deque, despite their Extend-impls being very similar. I have yet to figure out where that slowdown comes from.

Other than that, is there any chance an implementation similar to / based on my Deque could land in alloc? On reddit, there seemed to be a few people who were quite excited about a possible free Vec -> Deque conversion in std.

[the8472]

VecDeque documentation doesn't promise that it'll size its capacity to a power-of-two so that kind of rewrite should be ok in principle. Other collection impls have been replaced piecemeal or wholesale before (e.g. HashMap). And free conversions are enticing, even if VecDeque is a bit more niche than Vec itself.

Since it'll likely touch a lot of code, including some unsafe code, you should be prepared for a long review time though and try to keep the diff as small as reasonable (without doing contortions).

Does your deque also work for ZSTs?

[Sp00ph]

It does work for ZSTs, just like Vec it doesn't allocate for ZSTs, its capacity is always usize::MAX and some of the functions that copy stuff around (make_contiguous, rotate_{right,left} and so on) also skip the copying for ZSTs to minimize the required work.

[the8472]

One exception is the extend_chained_trustedlen benchmark

That's due to a specialization that eliminates repeated reallocation and bounds-checks.

[Sp00ph]

And as for the diff size, I'm not sure a lot of the VecDeque code is salvageable, so I would've preferred to just replace it outright, as most of the algorithms and functions would need to be replaced anyways.