data-structures - 为什么 VecDeque 比 Vec 慢？

Question

我开始优化 crate 的性能，我换了一个 Vec 对于 VecDeque .容器按排序顺序维护元素(它应该相当小，所以我还没有费心尝试堆)并且偶尔会从中间拆分成两个单独的容器(我还没有尝试过堆的另一个原因) drain .
我希望第二个操作要快得多:我可以复制集合的前半部分，然后简单地旋转并减少原始(现在是第二个)集合的长度。但是，当我运行 #[bench] 时测试，以可变次数执行上述操作，(低于百万纳秒/迭代)我观察到性能随着 VecDeque 而下降。 :



测试一个
测试 b
测试 c
测试d


维克
12.6
5.9
5.9
3.8

VecDeque
13.6
8.9
7.3
5.8


一个可重现的示例 ( gist ):

#![feature(test)]
extern crate test;

use std::collections::VecDeque;

fn insert_in_sorted_order_vec<E: Ord + Eq>(t: &mut Vec<E>, k: E) {
    match t.binary_search(&k) {
        Ok(i) => t[i] = k,
        Err(i) => t.insert(i, k),
    }
}

fn insert_in_sorted_order_vecdeque<E: Ord + Eq>(t: &mut VecDeque<E>, k: E) {
    match t.binary_search(&k) {
        Ok(i) => t[i] = k,
        Err(i) => t.insert(i, k),
    }
}

fn split_vec<T>(mut t: Vec<T>) -> (Vec<T>, Vec<T>) {
    let a = t.drain(0..(t.len() / 2)).collect();
    (a, t)
}

fn split_vecdeque<T>(mut t: VecDeque<T>) -> (VecDeque<T>, VecDeque<T>) {
    let a = t.drain(0..(t.len() / 2)).collect();
    (a, t)
}

#[cfg(test)]
mod tests {
    use super::*;
    use test::Bencher;

    static ITERS_BEFORE_SPLIT: u32 = 50;
    static ITERS_TIME: u32 = 10_000;

    #[bench]
    fn vec_manip(b: &mut Bencher) {
        b.iter(|| {
            let mut v = Vec::new();
            for i in 0..(ITERS_TIME / ITERS_BEFORE_SPLIT) {
                for j in 1..(ITERS_BEFORE_SPLIT + 1) {
                    insert_in_sorted_order_vec(&mut v, i * j / (i + j)); // 'random'-ish illustrative number
                }

                v = split_vec(v).1;
            }
        });
    }

    #[bench]
    fn vecdeque_manip(b: &mut Bencher) {
        b.iter(|| {
            let mut v = VecDeque::new();
            for i in 0..(ITERS_TIME / ITERS_BEFORE_SPLIT) {
                for j in 1..(ITERS_BEFORE_SPLIT + 1) {
                    insert_in_sorted_order_vecdeque(&mut v, i * j / (i + j)); // 'random'-ish illustrative number
                }

                v = split_vecdeque(v).1;
            }
        });
    }
}

Vec实现花费了 69.2k ns/iter，而 VecDeque实现花费了 91.8k。
我已经多次重复并验证了这些结果 - 为什么使用这种更灵活的数据结构会降低性能？
这些结果是通过运行 cargo bench 获得的.

Linux 5.11

3900X(12 核，3.8-4.6 GHz)

32GB 3200 MHz 内存

rustc 1.55.0 每晚

默认 cargo bench选项(优化，据我所知没有调试符号等)

编辑
我换了 split_vecdeque使用方法 split_off而不是 drain().collect() (见下文)。看起来这种方法保证不会重新分配或移动任何东西，而只是移动 head和 tail周围的指针；见 documentation和 implementation .然而，它的性能甚至比 98.2k ns/iter 的原始 VecDeque 还要差。对于较大的值(ITERS_BEFORE_SPLIT = 50_000，ITERS_TIME = 5_000_000)，尽管性能(21.8m ns/iter)优于 drain (23.1 ns/iter) 并且比 Vec 差(19.1 纳秒/迭代)。

fn split_vecdeque<T>(mut t: VecDeque<T>) -> (VecDeque<T>, VecDeque<T>) {
    let a = t.split_off(t.len() / 2);
    (t, a)
}

Answer 1

A VecDeque就像一个 Vec但支持有效地从两端推送和弹出。为了做到这一点，它使用了一个连续的缓冲区(就像 Vec 一样)，但将其视为两个分区；一个头和一个尾部。
结构布局如下:

pub struct VecDeque<T> {
    tail: usize,
    head: usize,
    buf: RawVec<T>,
}

缓冲区中的项目是这样排序的:

[[tail: 5, 6, 7] ...unused... [head: 1, 2, 3, 4]] 

将项目添加到集合的末尾将附加到尾部，使用一些未使用的空间。添加到集合的开头将添加到头部的开头，进入相同的空间。当头尾在中间相遇时， VecDeque已满，需要重新分配。
与 Vec相比:

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

它像这样使用它的缓冲区:

[1, 2, 4, 5, 6, 7 ...unused...] 

最后添加一个项目很快，但在开始添加一个项目需要复制所有现有项目以腾出空间。
大多数操作在 VecDeque这种布局变得更加复杂，这将略微降低其性能。甚至检索它的长度也更复杂:

pub fn len(&self) -> usize {
    count(self.tail, self.head, self.cap())
}

整点 VecDeque是为了使某些操作更快，即推送和弹出集合的开始。 Vec在这方面非常慢，特别是如果有很多项目，因为它涉及移动所有其他项目以腾出空间。 VecDeque的结构使这些操作更快，但与 Vec 相比以牺牲其他操作的性能为代价.
您的测试似乎没有利用 VecDeque的设计，因为它们以调用 insert 为主，这涉及在两种情况下对许多项目进行昂贵的复制。