std::vector::reserve 的性能惩罚

Question

inline void add(const DataStruct& rhs) {
   using namespace boost::assign;
   vec.reserve(vec.size() + 3);
   vec += rhs.a, rhs.b, rhs.c;
}

上述函数执行了大约17000次，我看到它的表现（当然涉及到一些转换）比调用vector::reserve差2个数量级。我一直以为即使对于小值，reserve也可以加速push_back，但事实并非如此，我找不到任何明显的原因。是reserve阻止了函数内联吗？调用size()太昂贵了吗？这取决于平台吗？我将尝试在干净的环境中编写一些小型基准测试来确认这一点。

编译器：gcc (GCC) 4.4.2，带有-g -O2参数。

- pmr

---

你尝试为17000 * 3个输入保留空间了吗？你的额外函数调用可能会带来一些开销，这可能解释了差异。 - int3

@splicer：这个数字是由测试数据决定的。实际调用次数是可变的。 - pmr

我的观点是，你所做的只有在处理较大数字时才有效率。James Schek的答案为您提供了一种使用可变数量调用的方法，只要您知道开始的总数。否则，最好让默认实现为您处理它。 - int3

你是否在同一类实例上调用了add()函数？如果是这种情况，每次调用add()都会使vec增长3个元素，而单独使用pushback则会更少地增长vec。 - Patrick

Answer 1

GCC实现的reserve()方法会分配确切数量的元素，而push_back()方法会按指数增长将内部缓冲区扩大两倍，因此您会破坏指数增长，并在每次迭代中强制重新分配/复制。在ltrace或valgrind下运行测试并查看malloc()调用次数。

- Nikolai Fetissov

---

+1. 我刚刚查看了GCC源代码并打算写同样的内容。 - P Shved

通过push_back()实现的缓冲区的指数增长是由标准或实现定义保证的吗？ - pmr

标准实际上保证指数增长，因为这是获得分摊O(1) push_back 行为的唯一合理方式（不合理的解决方案包括分配所有内存 ;)）。 - MSalters

GCC的行为也可以解释：通过让您精确设置期望的大小，它们允许您在您知道实际需要多少内存的情况下不浪费内存的机会。 - Matthieu M.

我一直认为指数增长也适用于reserve，而且reserve只是保证元素分配会预先分配而不会因为内存耗尽而在push_back时失败。今天遇到与提问者相同的惊讶，我有点希望有一个reserve变体可以保证后续分配（至少对于POD），但仍然表现出自然增长。 - Dwayne Robinson

Answer 2

只有在事先知道需要多少空间时，才使用reserve。

Reserve需要复制整个向量...

如果你做了一个push_back操作,向量太小，那么它会执行reserve(vec.size()*2)的操作。

如果你不知道你的向量将有多大，并且需要随机访问，请考虑使用std::deque。

- Tristram Gräbener

---

嗯，我认为公正地说，这是一种在平均情况下经过数学证明具有最佳性能的启发式方法。 - int3

我认为它既不是启发式算法，也不是正式算法。它是一种策略，在许多使用场景下都能很好地发挥作用。 - Dolphin

我在某个地方读到过，用1.5倍乘法效果更好。我不记得是在哪里看到的，他们做了什么样的假设，或其他任何细节。显然，使用更大的常数进行乘法可以减少重新分配的次数，并更有效地利用内存。 - David Thornley

同样的，对于在耗尽时将大小乘以n，每个n-1个push_back调用都会多制作一份副本。因此，将大小乘以1.5的速度正好慢了两倍。 - P Shved

将当前分配大小乘以任何常数（0除外）将导致对数增长。更改常数只是调整，大O性能仍然相同。1.5偏向于较小的向量，2偏向于较大的向量。他们选择2是因为在计算机领域中它是一个不错的圆整数字，并且任何调整都将毫无意义，因为我的用法会与你的使用不同。如果你需要调整行为，可以使用size()和reserve()轻松地覆盖默认行为。 - deft_code

Answer 3

只有在您预先知道元素的数量时才使用reserve()。在这种情况下，reserve()一次性为所有元素保留空间。

否则，只需使用push_back()并依赖默认策略 - 它将指数级地重新分配，并大大减少重新分配的次数，以略微次优的内存消耗为代价。

- sharptooth

Answer 4

当std::vector需要重新分配内存时，它会将其分配大小增加N * 2，其中n是其当前大小。这导致向量增长时的重新分配数量呈对数级增长。

如果std::vector改为按固定量增加其分配空间，则随着向量增长，重新分配的数量将线性增长。

你所做的实质上是使向量按常量3增长，意味着线性增长。线性明显比对数更差，特别是在处理大量数据时。

通常，唯一优于对数的增长方式是常量增长。这就是标准委员会创建reserve方法的原因。如果可以避免所有重新分配（常量），则性能将优于默认的对数行为。

话虽如此，您可能希望考虑Herb Sutter关于更喜欢std::deque而不是vector的评论。 www.gotw.ca/gotw/054.htm

- deft_code

Answer 5

将保留区域移到添加操作之外。

每次调用“add”时，您都会预留至少3个额外的元素。根据vector的实现方式，这可能会导致每次调用“add”时增加支持数组的大小。这肯定会导致性能差异。

使用reserve的正确方法如下：

vec.reserve(max*3);
for(int i=0; i<max; i++)
   add(i);

- James Schek

Answer 6

如果您对代码进行了分析，我敢打赌您会发现 += 非常快，问题在于 reserve 操作使性能下降。只有在您对向量的增长大小有一定了解时，才应使用 reserve。如果您能提前猜测，则进行一次 reserve 操作即可，否则请使用默认的 push_back。

- Dolphin