c++ - 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 个数量级。

我一直认为即使对于较小的值，储备也可以加快 push_back 的速度，但这似乎不是真的，我找不到任何明显的理由为什么不应该这样。保留会阻止函数的内联吗？对 size() 的调用是否太贵了？这取决于平台吗？我将尝试编写一些小型基准测试，以在干净的环境中确认这一点。

编译器：gcc (GCC) 4.4.2带 -g -O2

score 27 · Accepted Answer

GCC 实现reserve()将分配确切数量的元素，同时push_back()将内部缓冲区翻倍以指数方式增长，因此您正在击败指数增长并在每次迭代时强制重新分配/复制。ltrace在or下运行测试valgrind并查看malloc()调用次数。

score 7 · Accepted Answer

如果您事先知道它将使用多少地方，请仅使用保留。

Reserve 将需要复制您的整个向量...

如果你做一个 push_back 并且向量太小，那么它将做一个保留 (vec.size()*2)。

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

score 7 · Accepted Answer

reserve()仅当您事先知道元素的数量时才使用。在这种情况下reserve()，一次为所有元素提供空间。

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

score 5 · Accepted Answer

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

相反，如果 std::vector 将其分配的空间增长了一个常数，那么重新分配的数量将随着向量的增长而线性增长。

您所做的基本上是使向量以恒定量 3 增长，这意味着线性增长。线性显然比对数更糟糕，尤其是对于大数字。

通常，唯一比对数更好的增长是恒定的。这就是标准委员会创建储备方法的原因。如果您可以避免所有重新分配（常量），您将比默认的对数行为表现更好。

也就是说，您可能需要考虑 Herb Sutter 关于更喜欢 std::deque 而不是向量www.gotw.ca/gotw/054.htm的评论

score 3 · Accepted Answer

将储备移到添加之外。

每次调用“添加”时，都会保留至少 3 个额外元素。根据向量的实现，几乎每次调用“add”时，这可能会增加支持数组的大小。那肯定会导致您描述的性能差异。

使用储备的正确方法是这样的：

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

score 3 · Accepted Answer

如果你分析了我打赌的代码，你会看到 += 非常快，问题是储备正在杀死你。当您对向量将增长到多大有所了解时，您实际上应该只使用储备。如果你能提前猜到，那就做一个预留，否则就用默认的 push_back。

6 回答 6