VecDeque "wraparound" bug (or major misunderstanding)

help
1

VecDeque::as_slices() is not behaving as I would expect. I am using VecDeque as a plain old FIFO queue, only adding items with extend() and only removing with pop_front(). As far as I can tell from the documentation, with this sort of use, the b in let (a, b) = q.as_slices() should always be empty. However, after a moderate amount of insertions/removals, some items do end up in that b. Here is an example that quickly breaks.

I can avoid this behavior by greatly increasing the VecDeque's initial with_capacity() relative to how much it will be used (I've been using 10x or 100x what I would have, in my current workarounds).

This is with rustc 1.16.0 (30cf806ef 2017-03-10)

I would appreciate any help anyone can offer!

2

VecDeque docs describe it as

A double-ended queue implemented with a growable ring buffer.

The ring in ring buffer implies that this data structure is circular and will wrap around.

The example for as_slices[1] shows that b is not empty on subsequent calls, though the description fails to describe what the two slices represent.

[1]: VecDeque in std::collections - Rust

I have a bug[2] I'm trying to track down and the library I'm currently poking at in my example uses VecDeque as an intermediate buffer for parsing the MySQL protocol. The code works fine compiled as a debug target, but the release target suffers from random buffer corruption. The library uses VecDeque.extend and VecDeque.drain.

[2]: [1.19] Erratic (I/O?) behavior from release target that's non-existent in debug target · Issue #42610 · rust-lang/rust · GitHub

Maybe we're seeing the same thing.

3

According to the code[3], as_slices returns one slice when the data is contiguous in the buffer. If the data wraps around, then one slice (a) is the data at the end of the buffer, and the other slice (b) is the data at the front of the buffer.

[3]: https://doc.rust-lang.org/src/collections/vec_deque.rs.html#1856

I think this is the behavior you're observing. It's not a bug. Setting the buffer to a larger size just deferred the wrap around, but eventually, it will happen if you put enough data in the VecDeque.

1 Like
4

Ahhh, ok, I understand now. I must have missed that the 0,1,2 gets moved to the second one in that example; I remember looking at that and coming away thinking that push_back and push_front are explicitly going into the first and second slices (with the comment at the beginning about the "default" usage being push_back meaning there is some fancier behavior if you start using push_front as well).

I figured the simple "default" usage would give you a queue that hides implementation details like that. The VecDeque::as_slices documentation could really use a more explicit description of what's going on with those slices. I will see if they are willing to have it be elaborated.

Thanks for clearing up the behavior!