为什么 VecDeque 比 Vec 慢？

Question

我开始一箱的优化性能，和我换了Vec一个VecDeque。容器按排序顺序维护元素（它应该相当小，所以我还没有尝试尝试堆）并且偶尔会从中间拆分成两个单独的容器（我还没有尝试过堆的另一个原因）drain.

我希望第二个操作要快得多：我可以复制集合的前半部分，然后简单地旋转并减少原始（现在是第二个）集合的长度。然而，当我跑我#[bench]的测试中，执行上述操作的次数可变数目，（低于百万NS / iters）我观察到的性能下降与VecDeque：

	测试一个	测试 b	测试 c	测试d
维克	12.6	5.9	5.9	3.8
维克德克	13.6	8.9	7.3	5.8

一个可重现的例子（要点）：

#![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周围的指针; 请参阅文档和实现。然而，它的性能甚至比 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 ns/iter）差。

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

Answer 1

AVecDeque就像 aVec但支持有效地从两端推送和弹出。为此，它使用单个连续缓冲区（就像 a Vec），但将其视为两个分区；一个头和一个尾巴。

结构布局如下：

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

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

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

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

与Vec：

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

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

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

最后添加一个项目很快，但在开始添加一个项目需要复制所有现有项目以腾出空间。

VecDeque这种布局使大多数操作变得更加复杂，这将略微降低其性能。甚至检索它的长度也更复杂：

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

重点VecDeque是使某些操作更快，即推送和弹出集合的开始。Vec在这方面非常慢，特别是如果有很多项目，因为它涉及移动所有其他项目以腾出空间。的结构VecDeque使这些操作快速，但与Vec.

您的测试似乎没有利用VecDeque的设计，因为它们主要是对 的调用insert，这涉及在两种情况下对许多项目进行昂贵的复制。