c++ - 已知大小时向 vector 添加元素的基准测试

Question

我已经为将新元素添加到我知道其大小的 vector 做了一个小基准。

代码:

struct foo{
    foo() = default;
    foo(double x, double y, double z) :x(x), y(y), z(y){

    }
    double x;
    double y;
    double z;
};

void resize_and_index(){
    std::vector<foo> bar(1000);
    for (auto& item : bar){
        item.x = 5;
        item.y = 5;
        item.z = 5;
    }
}

void reserve_and_push(){
    std::vector<foo> bar;
    bar.reserve(1000);
    for (size_t i = 0; i < 1000; i++)
    {
        bar.push_back(foo(5, 5, 5));
    }
}

void reserve_and_push_move(){
    std::vector<foo> bar;
    bar.reserve(1000);
    for (size_t i = 0; i < 1000; i++)
    {
        bar.push_back(std::move(foo(5, 5, 5)));
    }
}

void reserve_and_embalce(){
    std::vector<foo> bar;
    bar.reserve(1000);
    for (size_t i = 0; i < 1000; i++)
    {
        bar.emplace_back(5, 5, 5);
    }
}

然后我调用了每个方法 100000 次。

结果:

resize_and_index: 176 mSec 
reserve_and_push: 560 mSec
reserve_and_push_move: 574 mSec 
reserve_and_embalce: 143 mSec

调用代码:

const size_t repeate = 100000;
auto start_time = clock();
for (size_t i = 0; i < repeate; i++)
{
    resize_and_index();
}
auto stop_time = clock();
std::cout << "resize_and_index: " << (stop_time - start_time) / double(CLOCKS_PER_SEC) * 1000 << " mSec" << std::endl;


start_time = clock();
for (size_t i = 0; i < repeate; i++)
{
    reserve_and_push();
}
stop_time = clock();
std::cout << "reserve_and_push: " << (stop_time - start_time) / double(CLOCKS_PER_SEC) * 1000 << " mSec" << std::endl;


start_time = clock();
for (size_t i = 0; i < repeate; i++)
{
    reserve_and_push_move();
}
stop_time = clock();
std::cout << "reserve_and_push_move: " << (stop_time - start_time) / double(CLOCKS_PER_SEC) * 1000 << " mSec" << std::endl;


start_time = clock();
for (size_t i = 0; i < repeate; i++)
{
    reserve_and_embalce();
}
stop_time = clock();
std::cout << "reserve_and_embalce: " << (stop_time - start_time) / double(CLOCKS_PER_SEC) * 1000 << " mSec" << std::endl;

我的问题:

1. 为什么我会得到这些结果？是什么让 emplace_back 优于其他人？
2. 为什么 std::move 会使性能稍微变差？

基准测试条件:

• 编译器:VS.NET 2013 C++ 编译器(/O2 最大速度优化)
• 操作系统:Windows 8
• 处理器:Intel Core i7-410U CPU @ 2.00 GHZ

另一台机器(通过 horstling ):

VS2013、Win7、至强 1241 @ 3.5 Ghz

resize_and_index: 144 mSec
reserve_and_push: 199 mSec
reserve_and_push_move: 201 mSec
reserve_and_embalce: 111 mSec

Answer 1

首先，reserve_and_push 和 reserve_and_push_move 在语义上是等价的。您构造的临时 foo 已经是一个右值(已经使用了 push_back 的右值引用重载)；将它包装在一个移动中不会改变任何东西，除了可能会使编译器的代码模糊不清，这可以解释轻微的性能损失。 (虽然我认为它更可能是噪音。)此外，您的类(class)具有相同的复制和移动语义。

其次，如果将循环体写为 resize_and_index 变体可能会更优化

item = foo(5, 5, 5);

虽然只有分析才能证明这一点。关键是编译器可能会为三个单独的分配生成次优代码。

第三，你也应该试试这个:

std::vector<foo> v(100, foo(5, 5, 5));

第四，这个基准对编译器非常敏感，因为编译器意识到这些函数实际上没有做任何事情，只是简单地优化了它们的完整主体。

现在进行分析。请注意，如果您真的想知道发生了什么，则必须检查编译器生成的程序集。

第一个版本执行以下操作:

1. 为 1000 个 foo 分配空间。
2. 循环并默认构造每一个。
3. 遍历所有元素并重新分配值。

这里的主要问题是编译器是否意识到第二步中的构造函数是空操作并且它可以省略整个循环。组装检查可以证明这一点。

第二个和第三个版本执行以下操作:

1. 为 1000 个 foo 分配空间。
2. 1000 次:
   1. 构造一个临时的 foo 对象
   2. 确保仍有足够的分配空间
   3. 将临时文件移动(对于您的类型，等同于拷贝，因为您的类没有特殊的移动语义)到分配的空间中。
   4. 增加 vector 的大小。

编译器这里有很大的优化空间。如果它将所有操作内联到同一个函数中，它就会意识到大小检查是多余的。然后它可以意识到你的移动构造函数不能抛出，这意味着整个循环是不可中断的，这意味着它可以将所有增量合并到一个赋值中。如果它不内联 push_back，它必须将临时文件放在内存中并传递对它的引用；它可以通过多种方式对此进行特殊处理以提高效率，但不太可能。

但除非编译器执行其中的某些操作，否则我预计此版本会比其他版本慢很多。

第四个版本做了以下事情:

1. 为 1000 个 foo 分配足够的空间。
2. 1000 次:
   1. 确保仍有足够的分配空间
   2. 使用带有三个参数的构造函数在分配的空间中创建一个新对象
   3. 增加大小

这和前面的类似，有两点不同:第一，MS标准库实现push_back的方式，它要检查传递的引用是否是vector本身的引用；这大大增加了函数的复杂性，抑制了内联。 emplace_back 没有这个问题。其次，emplace_back 获取三个简单的标量参数而不是对堆栈对象的引用；如果函数没有被内联，则传递的效率要高得多。

除非您专门使用 Microsoft 的编译器，否则我强烈建议您与其他编译器(及其标准库)进行比较。我还认为我建议的版本会打败你们所有的四个版本，但我还没有对此进行分析。

最后，除非代码真的对性能很敏感，否则你应该编写最可读的版本。 (这是我的版本获胜的另一个地方，IMO。)