为什么vector(size)比new []慢？

Question

我正在对一些STL算法进行基准测试,我对以下代码所花费的时间感到惊讶:(我用time命令测量了g ++编译代码[无优化] )

#include <vector>
struct vec2{
    int x, y;
    vec2():x(0), y(0) {}
};
int main(int argc, char* argv[]){
    const int size = 200000000;
    std::vector<vec2> tab(size); //2.26s
//  vec2* tab = new vec2[size]; //1.29s
//  tab[0].x = 0;
//  delete[] tab;
    return 0;
}

向量初始化所需的时间是2.26秒,而new(和delete)需要1.29秒.矢量ctor做什么需要更长的时间？new[]在每个元素上调用构造函数,就像vectorctor一样,对吧？

然后我用-O3编译,它运行得更快,但两个代码之间仍然存在差距.(我分别得到了0.83秒和0.75秒)

有任何想法吗？

Answer 1

速度将取决于实现,但是矢量较慢的最可能原因是矢量不能默认构造其元素.矢量元素始终是复制构造的.例如

std::vector<vec2> tab(size);

实际上被解释为

std::vector<vec2> tab(size, vec2());

即第二个参数从默认参数中获取其值.该载体然后分配原始内存和拷贝从外部传递到新向量的每个元素(通过使用拷贝构造)该默认构造的元件.这通常比默认构造每个元素更慢(如同new[]).

为了说明代码草图的差异,new vec2[size]大致相当于

vec2 *v = (vec2 *) malloc(size * sizeof(vec2));

for (size_t i = 0; i < size; ++i)
  // Default-construct `v[i]` in place
  new (&v[i]) vec2();

return v;

而vector<vec2>(size)大致相当于

vec2 source; // Default-constructed "original" element

vec2 *v = (vec2 *) malloc(size * sizeof(vec2));

for (size_t i = 0; i < size; ++i)
  // Copy-construct `v[i]` in place
  new (&v[i]) vec2(source);

return v;

根据实施情况,第二种方法可能会变慢.

虽然速度的两倍差异很难证明,但对非优化代码进行基准测试也没有任何意义.您在优化代码中观察到的差异远远小于人们在这种情况下可能合理预期的差异.

Answer 2

两个版本都初始化内存.

正如几个人所指出的那样,向量使用复制构造,而数组使用默认构造函数.您的编译器似乎比前者更好地优化后者.

请注意,在Real Life中,您很少想要一举初始化如此庞大的阵列.(有什么用的是一堆零？显然你打算最终把其他东西放在那里......初始化数百兆字节对缓存不友好.)

相反,你会写如下:

const int size = 200000000;
std::vector<vec2> v;
v.reserve(size);

然后,当您准备将真实元素放入向量中时,您可以使用v.push_back(element).该reserve()分配存储器中而不对其进行初始化; 在push_back()拷贝构造成预留空间.

或者,如果要将新元素放入向量中,可以使用v.resize(v.size()+1)然后修改该元素v.back().(这就是"池分配器"可能工作的方式.)虽然这个序列将初始化元素然后覆盖它,但它将全部发生在L1缓存中,这几乎和没有初始化它一样快.

因此,为了公平比较,请尝试使用大型向量(with reserve)与数组来创建一系列不相同的项目.你应该发现矢量更快.