为什么VecDeque比Vec慢？

html5 • • 问答

我开始一箱的优化性能，和我换了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

回答

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，这涉及在两种情况下对许多项目进行昂贵的复制。

以上是为什么VecDeque比Vec慢？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>