Why does VecDeque.as_slices() return two slices?

What is the reasoning behind this and how does Rust decide on which side to put which values?

Essentially, that's just how the queue itself is implemented internally - it's based on a so-called "ring buffer", that is, it allocates some space and then uses both ends of this space as head and tail of the queue.

Where is the boundary - depends on how exactly the queue was used. For example, if we do this:

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(10);
    
    deque.push_back(1u8);
    deque.push_front(2);
    println!("{:?}", deque.as_slices());
}

...this code prints ([2], [1]), i.e. head and tail will be in different slices. On the other hand, of we push from one side only, like this -

use std::collections::VecDeque;

fn main() {
    let mut deque = VecDeque::with_capacity(10);
    
    deque.push_back(1u8);
    deque.push_back(2);
    println!("{:?}", deque.as_slices());
}

...we'll have ([1, 2], []), i.e. everything is stored in one place.

2 Likes

Would you say that this vector type is well suited for fast updates of time series data?
Does push_front vs push_back differ in performance? In JS unshift vs push differs greatly in performance.

I need a fixed size array where new items are added to the left, and the last item is popped.

Doesn't seem to be true when pushing on one side, I still get numbers in two slices.

use std::collections::VecDeque;

fn main() {

    let mut buf = VecDeque::new();
    buf.push_front(100);
    buf.push_front(1);
    buf.push_front(0);
    buf.push_front(1);
    buf.push_front(1);
    buf.push_front(1);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(2);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(3);
    buf.push_front(3);

    // dbg!(&buf[0]);
    // buf.make_contiguous().sort();
    dbg!(buf.as_slices());
}

VecDeque does front/back insertions in O(1) if it doesn't need to reallocate. You can easily wrap it so that it always pops before pushing when full, that would make it a constant sized ring buffer.

how do I limit the size?

Here's what an example VecDeque looks like internally

capacity: 12
len: 10
          back    front
             V        V
[5, 6, 7, 8, 9, _, _, 0, 1, 2, 3, 4]

The two slices you get are portions of the same buffer on either side of the _ (uninitialized) items. When you do push_front it decrements front and writes the item to the _ under front. When you do pop_front, it reads the item from front and increments front. And the back operations are the same, but with increment and decrement swapped. If back or front reach the end of the buffer, they wrap around.

I think you get two nonempty slices in your example because when the buffer gets full, all the items are copied over into a new, larger buffer starting from the beginning (essentially doing a make_contiguous), which means the first push_front after that will wrap around to the end. If you use push_back instead, it acts like a regular Vec with all the uninitialized spots at the end.

If you're doing something like a rolling average, then yeah this works great. Popping from either end is always fast, and pushing is fast unless it needs to grow the buffer. But if you give it the right capacity to start with and always pop and push in pairs, then it won't have to grow at all.

5 Likes

It's a little bit more complicated than that. The code for growing the vector has three different strategies to move around the smallest number of elements. I guess this is an optimisation for the case where realloc returns an extended version of the same memory region. So growing the ring buffer does not neccessarily make the elements contiguous.

From the source code of VecDeque::handle_capacity_increase()

        // Move the shortest contiguous section of the ring buffer
        //
        // H := head
        // L := last element (`self.to_physical_idx(self.len - 1)`)
        //
        //    H           L
        //   [o o o o o o o . ]
        //    H           L
        // A [o o o o o o o . . . . . . . . . ]
        //        L H
        //   [o o o o o o o o ]
        //          H           L
        // B [. . . o o o o o o o . . . . . . ]
        //              L H
        //   [o o o o o o o o ]
        //            L                   H
        // C [o o o o o . . . . . . . . . o o ]

EDIT

It's not realloc() but Allocator::grow() is used.

EDIT 2

Well, turns out after some debugging that the the grow() method of the current default allocator (rustc 1.76.0) will eventually call realloc() ^^ This was a fun trip into the rust standard library :slight_smile:
Also there is some more stuff I wrote above that's not correct, but my day was long so if you care, check out the standard library yourself. I found that debugging it with the jetbrains IDE called RustRover is a blast.

6 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.