std::vector::emplace_back 的性能与 POD 结构的分配

Question

在下面的示例中，对于普通旧数据 (POD) 结构，我看到了元素分配（给定一个正确大小的向量）与 emplace_back（给定一个具有保留存储的向量）相比的性能优势。有人可以详细说明这种差异的来源吗？

非常感谢您！

备注

这个问题是在一个更大的项目中提出的，下面只是一个 MWE
我确实查看了编译器资源管理器，但没有想出好的解决方案
我知道赋值只是因为结构是 POD，但我确实希望编译器能够优化开销，因为 C++ 应该具有零开销抽象
也欢迎对代码提出任何一般性建议，感谢您的输入:)

代码

#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>

using std::cout;
using std::endl;
using std::vector;
using std::size_t;

typedef std::chrono::high_resolution_clock hrc;
typedef std::chrono::microseconds ms;
using std::chrono::duration_cast;

struct Data {
  int x, y;

  inline Data() noexcept: x(0), y(0) {}

  inline Data(int x, int y) noexcept: x(x), y(y) {}
};

int main() {
  constexpr size_t n = 1000000;
  constexpr size_t reps = 5;

  for (size_t rep = 0; rep < reps; rep++) {
    {
      vector<Data> vec;
      vec.reserve(n);
      auto t1 = hrc::now();
      for (size_t i = 0; i < n; i++)
        vec.emplace_back(i, -i);
      auto t2 = hrc::now();
      cout << "Emplace Back: " << duration_cast<ms>(t2 - t1).count() << " ms" << endl;

      // Check
      size_t sum = 0;
      for (auto const &elem : vec)
        sum += elem.x;
      if (sum != ((n * (n - 1)) / 2))
        return EXIT_FAILURE;
    }

    {
      vector<Data> vec;
      vec.resize(n);
      auto t1 = hrc::now();
      for (size_t i = 0; i < n; i++)
        vec[i] = Data(i, i);
      auto t2 = hrc::now();
      cout << "Assign      : " << duration_cast<ms>(t2 - t1).count() << " ms" << endl;

      // Check
      size_t sum = 0;
      for (auto const &elem : vec)
        sum += elem.x;
      if (sum != ((n * (n - 1)) / 2))
        return EXIT_FAILURE;
    }
  }
}

输出

sysctl -n machdep.cpu.brand_string && clang++ -v && clang++ -o main -std=c++17 -O3 main.cpp && ./main
Intel(R) Core(TM) i5-3210M CPU @ 2.50GHz
Apple clang version 12.0.0 (clang-1200.0.32.29)
Target: x86_64-apple-darwin19.6.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin
Emplace Back: 6162 ms
Assign      : 1000 ms
Emplace Back: 2874 ms
Assign      : 864 ms
Emplace Back: 2149 ms
Assign      : 855 ms
Emplace Back: 2062 ms
Assign      : 934 ms
Emplace Back: 2678 ms
Assign      : 1030 ms

Answer 1

您希望测量的内容

emplace_back
通过 emplace_back 在 vec

中预分配的 space 中创建 Date 的实例

作业
创建 Date 的实例并将其分配给 vec.

中已存在的 Date 对象

您可能应采取的措施（由于优化）

emplace_back
同上：在 vec.
中预分配的 space 中通过 emplace_back 创建一个 Date 的实例增加 size 并检查是否必须分配新的 space。

作业
只是分配 - 在这种情况下，因为 Date 是一个非常简单的对象 - i 到 [=25= 中已创建对象的 x 和 y 的成员] 步骤。

因此对于分配案例，您完全错过了创建 Date 对象所需的时间，因为您没有在测量中包括 resize。

进一步说明

您在 assign 案例中的 vec.resize(n); 默认情况下用 n 元素填充向量（新放置称为 n次）。在循环中，对那些创建的对象进行赋值。

对于第一种情况 (emplace_back)，向量的 size（不是容量）在每次迭代中增加一个，并且它以 [= 开始每个添加对象的生命周期79=]placement new，而对于第二种情况 (assign)，size 没有改变，您只将 Date 对象分配给已经建造好的。

编译器可以优化赋值情况，仅将 x 和 y 赋值给向量中已经存在的实例，而无需创建中间 Date 对象。

要以有意义的方式进行衡量，您需要包括 vec.reserve(n) 和 vec.resize(n)。目前，您只是衡量编译器优化过程中的一些差异。

如果您还包括 vec.reserve(n) 和 vec.resize(n)，则测量值会更接近。

对于像 Date 这样简单的类，赋值和回位之间不会有太大区别，因为 赋值循环中的构造 case 通常可以被优化掉。

当您包含 vec.reserve(n) 和 vec.resize(n) 时，时间是：

gcc 8.4

Emplace Back: 11594 ms
Assign      : 11516 ms
Emplace Back: 2001 ms
Assign      : 2691 ms
Emplace Back: 2523 ms
Assign      : 1847 ms
Emplace Back: 1956 ms
Assign      : 1277 ms
Emplace Back: 949 ms
Assign      : 903 ms

铿锵

Emplace Back: 2115 ms
Assign      : 2640 ms
Emplace Back: 765 ms
Assign      : 766 ms
Emplace Back: 666 ms
Assign      : 540 ms
Emplace Back: 535 ms
Assign      : 515 ms
Emplace Back: 537 ms
Assign      : 543 ms

Answer 2

首先，两个观察：

索引访问版本缺少对 y 参数的否定：
比较 vec.emplace_back(i, -i); 与 vec[i] = Data(i, i);
您打印的时间是微秒或“µs”（“ms”通常表示毫秒）。
鉴于 1,000,000 次迭代需要 864 us，一次迭代需要 0.8 ns，或者只是 几个 CPU 周期 。与 2.8 ns 相比，我们说的是每次迭代 几个周期 的差异。

然后是一些高级分析：

emplace_back 版本比通过索引访问分配的时间长的原因可能是因为 emplace_back 除了创建新元素外，还需要将向量增长 1。即使有足够的保留 space，矢量的增长涉及 (1) 检查如果有足够的 space，以及 (2) 更新内部矢量大小字段。

另一方面，向量索引访问不执行边界检查，更不用说更新任何大小了。它实际上与原始指针取消引用一样多。

元素类型，struct Data很简单。创建、复制或覆盖它所花费的时间可以忽略不计。

最后，我们分析生成的程序集以确定到底发生了什么：

emplace_back版本：

        leaq    8000000(%rax), %r14
        xorl    %ebp, %ebp
        movq    %rbx, %r12
        movq    %rax, 8(%rsp)
        jmp     .L14
.L73:
        movl    %ebp, %eax
        movd    %ebp, %xmm0
        addq    , %rbp
        addq    , %rbx
        negl    %eax
        movd    %eax, %xmm5
        punpckldq       %xmm5, %xmm0
        movq    %xmm0, -8(%rbx)
        cmpq    00000, %rbp
        je      .L72
.L14:
        movq    %r14, %r15
        subq    %r12, %r15
        cmpq    %rbx, %r14
        jne     .L73

索引访问版本：

        leaq    8000000(%rax), %r13
        . . .
        pxor    %xmm1, %xmm1
        movq    %rax, %r12
        movq    %rbp, %rax
.L27:
        movdqa  .LC3(%rip), %xmm2
        movdqa  %xmm1, %xmm0
        addq    , %rax
        paddq   .LC2(%rip), %xmm1
        paddq   %xmm0, %xmm2
        shufps  6, %xmm2, %xmm0
        movups  %xmm0, -16(%rax)
        cmpq    %rax, %r13
        jne     .L27

结论：

总体而言，编译器在两个版本中在内联和消除对象复制方面都做得很好。
第二个版本是矢量化的，每次迭代写入 2 个元素（可能是由于缺少 y 的否定）。
第一个版本做了更多工作 - 我们可以看到额外的计数 (addq , %rbp) 和检查 (cmpq 00000, %rbp)。

std::vector::emplace_back 的性能与 POD 结构的分配

Performance of std::vector::emplace_back vs. assignment for POD struct

c++

performance

stl

您希望测量的内容

您可能应采取的措施（由于优化）

进一步说明