VecDeque::split_off has unexpectedly poor performance characteristics when splitting off from the front.

[emilio]

I tried this code:

use std::collections::VecDeque;

fn huge_queue() -> VecDeque<usize> {
    const HUGE: usize = 1000000;
    let mut queue = VecDeque::with_capacity(HUGE);
    for i in 0..HUGE {
        queue.push_back(i);
    }
    queue
}

const CHUNK: usize = 123;
const FAST: bool = false;

fn main() {
    let mut queue = huge_queue();
    if FAST {
        while queue.len() > CHUNK {
            queue.rotate_left(CHUNK);
            let rest = queue.split_off(queue.len() - CHUNK);
            println!("Chunk of {}", rest.len());
        }
    } else {
        while queue.len() > CHUNK {
            let rest = queue.split_off(CHUNK);
            println!("Chunk of {}", queue.len());
            queue = rest;
        }
    }
    println!("Remaining: {}", queue.len());
}

I expected the FAST branch and the else branch to have comparable performance, instead it seems VecDeque::split_off from the front is much slower than expected (as one would expect of e.g. Vec::split_off which needs to shift all the elements).

[cuviper]

        while queue.len() > CHUNK {
            let rest = queue.split_off(CHUNK);
            println!("Chunk of {}", queue.len());
            queue = rest;
        }

If I understand, your expectation was that rest would actually get the original allocation, and queue would be replaced with a new allocation for the CHUNK items (before you assign it back). So only the smaller size would need a memory copy. Right?

Note that the docs explicitly say "Returns a newly allocated VecDeque," and "Note that the capacity of self does not change."

We recently went over a similar case with Vec::split_off(0) where #76682 had optimized it to avoid any memory copy, but issue #119913 and pull request #119917 reverted that. VecDeque should not necessarily be considered the same way, given different expectations about ring buffers, but maybe we should add VecDeque::split_off_front that explicitly keeps self as the back portion with the original allocation.

[emilio]

If I understand, your expectation was that rest would actually get the original allocation, and queue would be replaced with a new allocation for the CHUNK items (before you assign it back). So only the smaller size would need a memory copy. Right?

Correct.

Note that the docs explicitly say "Returns a newly allocated VecDeque," and "Note that the capacity of self does not change."

Yes, and I think that's unexpected. I agree it's documented :)

maybe we should add VecDeque::split_off_front that explicitly keeps self as the back portion with the original allocation.

That would be reasonable.