VecDeque : as_slices() not working as expected?

1

I'm new to Rust and still learning. While experimenting with VecDeque, I noticed a rather inconsistent (I believe) output from as_slices(). Below is my code:

fn main() {
    let mut deq = VecDeque::from([1, 2, 3]);
    
    deq.push_back(4);
    deq.push_back(5);
    deq.push_front(10);
    deq.push_front(9);
    
    println!("(front, back) = {:?}", deq.as_slices());
    
    while let Some(_front) = deq.pop_front() {
    }
    
    deq.push_back(1);
    deq.push_back(20);
    println!("(front, back) = {:?}", deq.as_slices());
    
    deq.push_front(10);
    deq.push_front(100);
    println!("(front, back) = {:?}", deq.as_slices());
    
}

The first time as_slices() was called, the output was as expected -

(front, back) = ([9, 10], [1, 2, 3, 4, 5]) // two slices with values from front and back respectively.

However, after using pop_front() to pop all values from deq, the subsequent push_back and push_front is always yielding one slice with all the values from deq and one empty slice.

(front, back) = ([1, 20], [])
(front, back) = ([100, 10, 1, 20], [])

Although the insertions happened as expected, the slices are different than before where I saw front and back values in separate slices.

Is this an expected behavior and why is this happening?

Code link : Rust Playground

Thank you!

2

semantically, the VecDeque is a double-ended queue, there's only the "front end" and the "back end" of the queue, there's no "front slice" and "back slice".

the fact as_slices() method exists is an optimization, for situations where the algorithm can take advantage of the fact that the elements are stored in (chunks of) continous memory.

it is only guarenteed that when you iterate through the two slices, the combined iteration order is the same as the "logical" order of the queue. it is NOT specified how the elements are partitioned, any split is possible, depending on the order how the elements are inserted and removed from the queue.

9 Likes
3

Thank you for the explanation.
However, I have a followup question. If the elements in the the slices can vary depending on how elements were added or removed, then comparing them using assert_eq (or similar macros) as given in the example in standard documentation for as_slices()
image
results in unpredictable outcomes? Like depending on the contents of the slices, the assertion may be true or false at run time as I cannot before hand know, how the vector will be partitioned into slices.

4

they are NOT unpredictable, or, in other words, the split is deterministic, but the exact result depends on the entire history of the insertion and deletion sequence (and maybe some implementation details too).

this is trackable for a simple test case, but it's impractical in real application code. the correctness of your algorithm should NOT depend on where the data items are located, though you can use this information for optmization purpose in special cases.

for example, suppose you have a specialized algorithm when all the elements are in a single continous range, you can do something like:

match deque.as_slices() {
    (ref data, &[]) => fast_algorithm_with_slice(data),
    _ => slow_algorithm_with_iterator(deque.iter()),
}

in this example, it's a logic error, e.g., if the fast_algorithm_with_slice(some_slice) gives different result than slow_algorithm_with_iterator(some_slice.iter()).

EDIT:

some clarification:

  1. the example is for demonstration purpose, you may have different "special case" to optimize for, it's not necessarily limited to the case where all elements are within a single continous slice. as a totally contrived example, you want to handle the special case where there were exactly 6 elements in the queue, and they were splitted into two slices of equal size:
match deque.as_slices() {
    (ref x@ &[x0, x1, x2], ref y@ &[x1, y1, z1]) => special_case(x, y),
    _ => general_case(deque.iter()),
}

  1. in case you do have an algorithm that is optimized for contigous array of elements, you'd better use deque.make_contigous(), which may move elements around, but it's probably still faster than an iterator based algorithm. after all, the "slow" algorithm needs to iterator all the elements anyway.

  2. when I mentioned logic error, I didn't mean it in the strict sense, but just in principle. after all, what is or isn't a logic error is completely up to the application.

3 Likes
5

Yes, it's unspecified, so it's unpredictable. The way the sequence is partitioned into two slices may change with a new version of Rust, for example.

But here is what happens in your example with the current implementation:

    let mut deq = VecDeque::from([1, 2, 3]);

At this point, the queue has capacity 3, is completely full, and looks like this:

1 2 3
^

where ^ is a pointer indicating where the front is.

    deq.push_back(4);
    deq.push_back(5);

Now there isn't enough space, so a new larger queue with capacity 6 is allocated and all elements moved there:

1 2 3 _ _ _
^

and 4 and 5 are pushed to the back:

1 2 3 4 5 _
^

    deq.push_front(10);

10 is pushed to the front. The buffer is circular, so the front pointer wraps around:

1 2 3 4 5 10
          ^

    deq.push_front(9);

There is not enough space, so again the buffer is doubled. Elements from the two parts are moved to the beginning and to the end of the new buffer:

1 2 3 4 5 _ _ _ _ _ _ 10
                      ^

9 is added to the front:

1 2 3 4 5 _ _ _ _ _ 9 10
                    ^

    println!("(front, back) = {:?}", deq.as_slices());

You get the ([9, 10], [1, 2, 3, 4, 5]) output because of the wraparound.

    while let Some(_front) = deq.pop_front() {
    }

Things are extracted from the front, with the front pointer moving past 5, the last extracted element:

_ _ _ _ _ _ _ _ _ _ _ _ 
          ^

    deq.push_back(1);
    deq.push_back(20);
    println!("(front, back) = {:?}", deq.as_slices());

_ _ _ _ _ 1 20 _ _ _ _ _ 
          ^

    deq.push_front(10);
    deq.push_front(100);
    println!("(front, back) = {:?}", deq.as_slices());

_ _ _ 100 10 1 20 _ _ _ _ _ 
      ^

There happens to be no wraparound, so you get the ([100, 10, 1, 20], []) output.

12 Likes
6

Word of advice: read the docs. In some rare cases docs omit important part of the specification (when it's outrageous enough that developers of system library and or some Rust crate couldn't imagine it… that's usually worthy to report and fix), but most of the time what see in the documentation is what you get in runtime.

Notably: if some promise is not made in documentation then usually it doesn't hold – often on purpose, to have the freedom to change the implementation.

But in this case documentation, while not telling us much shows us test that verifies that we get some particular slices back, after few push operations.

I think this should be reported as documentation issue. Documentation should include something like this and explanations why direct comparison of slices is not advisable in tests, but only full sequence from two slices is guaranteed:

let mut deque = VecDeque::new();

deque.push_back(0);
deque.push_back(1);
deque.push_back(2);

let slices = deque.as_slices();
assert!(slices.0.iter().chain(slices.1.iter()).eq([0, 1, 2].iter()));

deque.push_front(10);
deque.push_front(9);

let slices = deque.as_slices();
assert!(slices.0.iter().chain(slices.1.iter()).eq([9, 10, 0, 1, 2].iter()));

Maybe worth filing a bug…

5 Likes
7

Thanks for noticing and reporting, BTW. Documentation fix is under review and would eventually land.

Rust project (and all other projects that try to have good documentation) rely on efforts of newbies like you to fix minor bugs: people who know how things actually work tend not to notice them because they don't think too much about these things that they already know… it usually takes someone new to come and ask “why it's described like this… it's wrong” before people may realize that documentation is not 100% correct.

3 Likes
8

Great to see this post leading to a fix! . Thank you all for taking time and effort to explain the inner working of the as_slices method.

9

And did, in fact, change in certain situations in 1.67 when VecDeque was rewritten and the capacity behaviour changed. So this isn't just hypothetical, and may well change again in future.

10

You should be able to use this function if you need a more predictable partition.
pub fn make_contiguous(&mut self) -> &mut [T]

1 Like
11

Yes, but in case we use the slice with contiguous values to do something, we could instead, just iterate over the original queue to access them instead of using make_contiguous and then as_slices to get a slice of contiguous values.
Now, I'm not sure if there is any performance penalty with iterating over the VecDeque vs iterating over single contiguous slice as I've not read the internal implementation. Whatever make_contiguous does to create a slice with all values in the queue(perhaps iterating over the queue?) could be same or similar in performance to us iterating over queue directly to access the values.

12

make_contiguous will rotate the elements if they're not already contiguous. Notably, that means it's a write to the underlying allocation (which is why it's always &mut, and there's no non-mut version).

If you can work over the two slices separately, that is fine with shared access.