Repository navigation
Improve VecDeque implementation #99805
Description
Activity
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::MAXZSTs 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.
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.
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.
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::newcould be madeconstwith the current design, the issue of over-allocating would still persist. Additionally, with the proposed variation, conversions fromVecwould 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.
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::newsince that should be much simpler.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.
I would hope those branches branches are well-predicted and cheaper than divisions.
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 foralloc::collections::VecDeque, which allows for empty buffers (soDeque::newcan beconst fn, andDeque::from(Vec)is a free conversion), and also allows for non-power of 2 capacities, which meansDeque::shrink_to_fitcan 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
VecDequebenchmarks on myDeque(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 myDeque. One exception is theextend_chained_trustedlenbenchmark, where for whatever reason,VecDequeis almost 10x faster than myDeque, despite theirExtend-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
Dequecould land in alloc? On reddit, there seemed to be a few people who were quite excited about a possible freeVec -> Dequeconversion in std.Reacted by Jonas Böttiger, Brad Gibson, Aaron Bies, Jiahao XU, ptrca, Rageking8, Jakub Beránek, adrian5, thekashifmalik, Zixuan Chen and 1 moreReacted by Brad Gibson, Aaron Bies, Rageking8, thekashifmalik and Thomas ten CateVecDeque 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?
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.
One exception is the extend_chained_trustedlen benchmark
That's due to a specialization that eliminates repeated reallocation and bounds-checks.
Reacted by Paolo Barbolini and ShirshakAnd 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.
2 remaining items
If I do change
VecDeque::newto be const, should I add a#[rustc_const_unstable]attribute? If so, whats the process for adding a feature for it? I never worked on the stdlib itself before, so I'm not very knowledgeable on how to do things like that.Yes, that is the correct attribute. I would recommend checking out the std-dev-guide, it might answer a few questions 😉 (I only discovered it a few days ago, and it's pretty good). For making a function
const, you should especially look at the "API Change Proposal" section. But you can make the functionconstin a separate step as well, if you prefer.Alrighty, with any luck I should have a working version ready later today, what exactly is the process to merge it? Do i just fork the repo, push my changes to the fork and then create a PR, or are there any additional required steps?
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.
I changed my mind about this btw, and am now just modifying the existing VecDeque instead.
Alrighty, with any luck I should have a working version ready later today, what exactly is the process to merge it? Do i just fork the repo, push my changes to the fork and then create a PR, or are there any additional required steps?
Yes, exactly. Perhaps include "r? @scottmcm" in the PR description to assign @scottmcm, I saw on Reddit that they were interested in this.
Reacted by scottmcmPerfect, thank you.
Yup, you can assign it to me.
One procedural thing: I would suggest ensuring your PR is only an implementation change, and doesn't — in that first PR — add any new API guarantees.
Because changing the implementation could always be reverted, and thus we can just do it. But new promises, like "
Vec→VecDequeis always O(1)" is something that would need a libs-api FCP because it's something that we can't just revert, which takes extra oversight and waiting periods. So let's get in the implementation first, then do follow-up PRs to add the new guarantees to be able to talk about them separately.Sure thing. The way I've written it now, it says that in its current implementation (the new one), it's a cheap conversion, but this isn't guaranteed and shouldn't be relied upon. Hope it's okay that way.
Yeah, something non-committal is fine.
Like the current one says
This avoids reallocating where possible, but the conditions for that are strict, and subject to change, and so shouldn’t be relied upon unless the
Vec<T>came fromFrom<VecDeque<T>>and hasn’t been reallocated.cc the ACP to constify and add conversion guarantees: rust-lang/libs-team#138
- added a commit that references this issue
on Jan 6, 2023
VecDequecurrently allocates one extra empty element because it needs to discern between an empty and full queue. Besides wasting memory, this meansVecDeque::newcannot currently beconst.Solution
The most elegant solution would be to reimplement
VecDequebased 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 ofusize. 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 thanisize::MAX(which Rust's memory model dictates anyway), an empty queue (withhead == tail) is strictly different from a full queue (wherehead - 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 * capacityusing 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
@rustbot label +T-libs +T-libs-api