boost::container::vector比std::vector更快吗？为什么？

Question

我进行了一项有趣的测试，测试对象为boost vector和std vector，如下所示

int N = 10000;
{
    boost::timer::auto_cpu_timer t;
    std::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

{
    boost::timer::auto_cpu_timer t;
    boost::container::vector<int> v;
    for (int i = 0; i < N; ++i)
    {
        v.insert(v.begin(), i);
    }
}

win32版本，使用vc2010编译，/O2 /Oy-选项

当N = 10000时：

使用std vector：0.140849秒（墙上时间），0.140401秒用户时间 + 0.000000秒系统时间= 0.140401秒CPU时间（99.7%）

使用boost vector：0.056174秒（墙上时间），0.062400秒用户时间+ 0.000000秒系统时间 = 0.062400秒CPU时间（111.1%）

当N = 100,000时：

std：14.050757秒（墙上时间），14.055690秒用户时间+ 0.000000秒系统时间= 14.055690秒CPU时间（100.0%）

boost：5.585048秒（墙上时间），5.584836秒用户时间+ 0.000000秒系统时间= 5.584836秒CPU时间（100.0%）

向两个vector都添加reserve（N）后，CPU时间变化不大。

它们之间有什么区别吗？Boost比std快得多，原因是什么？谢谢。

检查sizeof()，std::vector为16，而boost::container::vector为12。

- user1899020

---

1. 发布您的编译器标志，否则就不会发生。
2. 发布“N”的值。

- Ed S.

Boost可能对于为新条目保留内存的策略有所不同。你尝试手动保留N个条目了吗？ - Sergey Kalinichenko

一个 N 值为 10,000 的测试非常小！相对速度可能因 N 的不同值而有所不同。在其他进程运行的机器上进行单个测试可能并不具有代表性。你使用了哪些编译器标志？使用了哪个编译器？那个编译器的版本是什么？ - Richard

在两种情况下，在循环之前调用v.reserve(N)后，再次尝试进行测试。 - Praetorian

有趣的是，在我的系统上（Linux x86，gcc 4.7.2，-O2，boost1.50），无论我是否使用.reserve（N），boost版本始终比STL版本慢。也许，连续插入10万个元素可能过于特定，无法成为容器实现整体速度的良好衡量标准吧 ;) ? - us2012

Answer 1

请记住，所有代码的速度都会因编译器和编译器版本之间的差异而有所不同。标准库提供可在各种平台上移植的代码，但很难保证速度。

如果您只在自己的机器上运行此代码，则应选择更快的选项（如果这是您想要的）。如果您问这个问题是因为您想做出普遍更快的选择，那么我认为除了测试之外没有其他方法来知道它。

当一个人以一般方式思考速度时，正如您似乎在思考的那样，您希望评估插入许多不同数量的对象，运行许多复制测试，并使用各种对象（类，双精度，字符等）。您还可以选择使用不同数量的空闲堆栈空间执行所有这些操作。如果您不考虑所有因素，那么您的问题默认变成：“为什么在我的特定情况下有速度差异？”通常很难说。

一个更好的问题可能是：“在各种测试条件下，我观察到两个类似功能的代码之间存在速度差异。它们之间是否有一些架构差异可以解释这一点？”答案可能是。

Cplusplus.com on std::vector

在内部，向量使用动态分配的数组来存储它们的元素。当插入新元素时，该数组可能需要重新分配以增长大小，这意味着需要分配一个新数组并将所有元素移动到其中。从处理时间的角度来看，这是一项相对昂贵的任务，因此，向量不会在每次添加元素到容器时重新分配。

相反，向量容器可以分配一些额外的存储空间来容纳可能的增长，因此容器的实际容量可能大于严格包含其元素（即其大小）所需的存储空间。库可以实现不同的增长策略来平衡内存使用和重新分配，但无论如何，重新分配只应在对数增长间隔的大小上发生，以便为向量末尾的单个元素插入提供摊销常数时间复杂度（参见push_back）。

从这里我们可以看到，您所看到的行为取决于您使用的STL库的特定版本，并且增长应该是对数级别的，并且增长通常需要大量复制。deque不需要大量复制，因此在您的测试中可能更好地扩展。

据推测，boost::container 的功能类似。我不知道因为我找不到有关它的写作。但我发现了this：

Boost.Container提供的所有容器都实现了就地插入，这意味着对象可以直接从用户参数构建到容器中，而不创建任何临时对象。对于没有变参模板支持的编译器，插入会被模拟到有限（10）个参数。

如果std::vector没有使用类似的架构，而是创建临时对象，这可能会导致运行时间差异。但是可能不适用于int类型。也许其他人可以找到不同的架构差异。

- Richard

Answer 2

boost::container 中的容器类大量使用扩展分配器，这些分配器不仅允许分配和释放、构造和析构，还可以扩展已分配的内存块。这意味着在许多情况下减少了复制操作，本质上相当于 C++ 中的 c realloc 函数。

char * data = malloc(size);
// fill until size, now you need more space
realloc(newdatasize);
// now we have more space*
// *for risks and side effects consult the manual

https://www.boost.org/doc/libs/1_68_0/doc/html/container/extended_allocators.html

当插入int时，"放置插入"优化都不相关，因为int是平凡构造的（这意味着在这种情况下，接受的答案不是正确的解释）。

- Wolfgang Brehm