预分配和矢量

Question

在c ++中,对于向量,即使向量动态地分配空间,为什么预分配是如此重要

Answer 1

首先,99%的案例不太可能"如此重要".

这基本上是一种优化.由于vector不知道你要添加多少个元素,它假设一个小的默认值,如果你试图添加一个新元素并且没有足够的空间来容纳一个新元素,它将不得不增长添加.增长操作可能很昂贵,因为它可能需要分配一个全新的缓冲区,将向量的当前内容复制到新缓冲区,并释放旧缓冲区.通过预先分配足够的空间,如果您知道要添加多少元素,则可以避免不必要的增长.

像任何性能优化一样,除非是瓶颈,否则不要担心它.此外,如果您不知道要添加多少元素,请让矢量决定.不要假设随机选择的数字比实现默认值更好.

Answer 2

其他答案已经涵盖了这个理论，但我还想加入一些数字来了解正在发生的事情。

有一次我编写了一个小测试套件来比较构造函数中的std::vector push_back、reserve+ push_back、大小（应该与resize） +operator[]和原始动态数组相同；这是 10000000 秒的结果int：

matteo@teoubuntu:~/cpp/vectorbenchmark2$ ./vectorbenchmark2 
Insert the number of elements: 10000000
Insert the number of iterations: 100
Minimum allocation for each benchmark 40000000 bytes.
Starting benchmark std::vector<int> (push_back/iterator, without reserve)... benchmark completed.
Results: 173.1 +/- 2.4 ms
Starting benchmark std::vector<int> (push_back/iterator, with reserve)... benchmark completed.
Results: 122.17 +/- 0.57 ms
Starting benchmark std::vector<int> (sized with constructor/operator[])... benchmark completed.
Results: 115.95 +/- 0.66 ms
Starting benchmark new int[]... benchmark completed.
Results: 121.33 +/- 0.84 ms
Starting benchmark malloc+memset... benchmark completed.
Results: 123.9 +/- 4.3 ms
Starting benchmark malloc... benchmark completed.
Results: 117.7 +/- 2.3 ms
Starting benchmark std::list<int>... benchmark completed.
Results: 552 +/- 35 ms

每个基准测试都包括数据结构的分配、用随机数填充它以及重新读取volatile变量中的所有内容。测试按照要求的第二个参数中指定的次数执行（在本次运行中我设置了 100 次）；时间是用 测量的gettimeofday。显示的结果是每个类别的所有时间计算的平均值和标准差。整个事情的代码可以在这里找到。

我们可以从这些数据中得出什么结果？

• 第一个明显的结果是，push_back不使用预分配是最慢的方法：在这些条件下，它比push_back 使用预分配慢约 41%。因此，如果时间是一个关键因素，并且计算或多或少您vector需要多大并不困难，reserve可能真的很方便。显然，如果你的分配+填充通常需要大约 10 毫秒，即使将其减少 40% 也不会被真正注意到；像往常一样，在有意义的地方（即瓶颈）进行优化。
• 另一个有趣的结果是初始化数组的大小（而不是使用 进行“透明”预分配reserve）甚至更快；我认为这是因为我们没有在紧密循环中调用push_back（必须更新“官方尺寸”）；vector相反，operator[]它几乎只做一个指针和并且很容易内联。也许使用迭代器（在这种情况下vector基本上是指针）可以获得更多东西。
• 有趣的是，具有ready- resized的唯一真正的竞争者vector是simple malloc，它没有任何附加功能，并且不适合非POD类型（并且在这个测试中仍然导致性能稍差）。这是一件很棒的事情，既vector可以如此高效，又可以保持其优势（我正在和你们说话，那些mallocs为了所谓的性能提升而传播 C 风格的人！）
• std::list（用于比较）是其中最慢的 - 但我们已经知道了:)

显然是YMMV；首先，这些是特定架构、特定编译器及其特定 STL 实现（即 g++ 4.4.5）的结果。reserve然后，我认为使用“复杂”类型（带有构造函数、复制构造函数等）可能会颠倒/方法的位置resize（resize需要构造 中的所有对象vector，但我认为不需要reserve）。一些更改也可能来自更改所使用的原始类型（intvs longvsshort等）。

此外，除了第一个和最后一个测试之外，所有测试之间的差异很小；它肯定比标准差大得多，但我认为即使标准库中的微小变化也可能会改变它们的一些相对结果。此外，改变元素的数量也应该会产生明显的影响，因为这些时间是不同大 O 操作的总和，因此增加或减少元素的数量可以改变总和中的主要附录。

测试条件（无聊的东西）

AMD Phenom X4 955 (3.2 GHz x4)，4 GB RAM DDR3

编译器：

matteo@teoubuntu:~/cpp/vectorbenchmark2$ g++ --version
g++ (Ubuntu/Linaro 4.4.4-14ubuntu5) 4.4.5
Copyright (C) 2010 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

操作系统/内核：

matteo@teoubuntu:~/cpp/vectorbenchmark2$  uname -a
Linux teoubuntu 2.6.35-24-generic #42-Ubuntu SMP Thu Dec 2 02:41:37 UTC 2010 x86_64 GNU/Linux

编译选项：

matteo@teoubuntu:~/cpp/vectorbenchmark2$ make
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF BenchmarkFunctors.o.d -c -o BenchmarkFunctors.o BenchmarkFunctors.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF main.o.d -c -o main.o main.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   -MMD -MF Utils.o.d -c -o Utils.o Utils.cpp
g++ -O3 -Wall -Wextra -ansi -pedantic   BenchmarkFunctors.o main.o Utils.o -o vectorbenchmark2

测试套件代码