为什么std::pair比std::tuple更快？

Question

这里是用于测试的代码。

元组测试：

using namespace std;

int main(){

    vector<tuple<int,int>> v;


    for (int var = 0; var < 100000000; ++var) {
        v.push_back(make_tuple(var, var));
    }
}

配对测试：

#include <vector>

using namespace std;

int main(){

    vector<pair<int,int>> v;


    for (int var = 0; var < 100000000; ++var) {
        v.push_back(make_pair(var, var));
    }
}

我使用Linux time命令进行了时间测量。 结果如下：

|       |   -O0   |    -O2   |
|:------|:-------:|:--------:|
| Pair  |   8.9 s |  1.60 s  |
| Tuple |  19.8 s |  1.96 s  |

我在想，为什么这两种数据结构在 O0 下会有这么大的区别，因为它们应该非常相似。在 O2 中只有微小的差异。

为什么在 O0 中的差异如此之大，而且为什么会有任何差异呢？

编辑：

带有 v.resize() 的代码

Pair：

#include <vector>

using namespace std;

int main(){

    vector<pair<int,int>> v;

    v.resize(100000000);

    for (int var = 0; var < 100000000; ++var) {
        v[var] = make_pair(var, var);
    }
}

元组：

#include<tuple>
#include<vector>

using namespace std;

int main(){

    vector<tuple<int,int>> v;

    v.resize(100000000);

    for (int var = 0; var < 100000000; ++var) {
        v[var] = make_tuple(var, var);
    }
}

结果：

|       |   -O0   |    -O2   |
|:------|:-------:|:--------:|
| Pair  |  5.01 s |  0.77 s  |
| Tuple |  10.6 s |  0.87 s  |

编辑：

我的系统

g++ (GCC) 4.8.3 20140911 (Red Hat 4.8.3-7)
GLIBCXX_3.4.19

- user4233758

---

针对两种情况的循环，我建议在循环前使用v.reserve(100000000)，以使测试更加准确。 - Jonathan Potter

在基准测试时，使用“-O0”进行性能测试是毫无意义的，只需比较优化后的代码即可。 - Paul R

为了性能测量，您应该运行并测量您的程序不止一次，而是x次，然后取测量运行时间的平均值（或中位数）。否则，您可能会遇到某个系统调用，以某种不可确定的方式改变您的测量结果。 - Sorin Totuarez

请先确保你正确地测量时间：https://dev59.com/iGox5IYBdhLWcg3wvWsy#9006802 - Maxim Egorushkin

我想知道使用-O3会有什么不同。 - BЈовић

Answer 1

你缺少一些关键信息：你使用哪个编译器？你用什么来衡量微基准的性能？你使用哪个标准库实现？

我的系统：

g++ (GCC) 4.9.1 20140903 (prerelease)
GLIBCXX_3.4.20

无论如何，我运行了您的示例，但首先保留向量的适当大小以消除内存分配开销。因此，有趣的是，我观察到了相反的一些有趣现象 - 与您看到的相反：

g++ -std=c++11 -O2 pair.cpp -o pair
perf stat -r 10 -d ./pair
Performance counter stats for './pair' (10 runs):

      1647.045151      task-clock:HG (msec)      #    0.993 CPUs utilized            ( +-  1.94% )
              346      context-switches:HG       #    0.210 K/sec                    ( +- 40.13% )
                7      cpu-migrations:HG         #    0.004 K/sec                    ( +- 22.01% )
          182,978      page-faults:HG            #    0.111 M/sec                    ( +-  0.04% )
    3,394,685,602      cycles:HG                 #    2.061 GHz                      ( +-  2.24% ) [44.38%]
    2,478,474,676      stalled-cycles-frontend:HG #   73.01% frontend cycles idle     ( +-  1.24% ) [44.55%]
    1,550,747,174      stalled-cycles-backend:HG #   45.68% backend  cycles idle     ( +-  1.60% ) [44.66%]
    2,837,484,461      instructions:HG           #    0.84  insns per cycle        
                                                  #    0.87  stalled cycles per insn  ( +-  4.86% ) [55.78%]
      526,077,681      branches:HG               #  319.407 M/sec                    ( +-  4.52% ) [55.82%]
          829,623      branch-misses:HG          #    0.16% of all branches          ( +-  4.42% ) [55.74%]
      594,396,822      L1-dcache-loads:HG        #  360.887 M/sec                    ( +-  4.74% ) [55.59%]
        20,842,113      L1-dcache-load-misses:HG  #    3.51% of all L1-dcache hits    ( +-  0.68% ) [55.46%]
        5,474,166      LLC-loads:HG              #    3.324 M/sec                    ( +-  1.81% ) [44.23%]
  <not supported>      LLC-load-misses:HG       

      1.658671368 seconds time elapsed                                          ( +-  1.82% )

对比：

g++ -std=c++11 -O2 tuple.cpp -o tuple
perf stat -r 10 -d ./tuple
Performance counter stats for './tuple' (10 runs):

        996.090514      task-clock:HG (msec)      #    0.996 CPUs utilized            ( +-  2.41% )
              102      context-switches:HG       #    0.102 K/sec                    ( +- 64.61% )
                4      cpu-migrations:HG         #    0.004 K/sec                    ( +- 32.24% )
          181,701      page-faults:HG            #    0.182 M/sec                    ( +-  0.06% )
    2,052,505,223      cycles:HG                 #    2.061 GHz                      ( +-  2.22% ) [44.45%]
    1,212,930,513      stalled-cycles-frontend:HG #   59.10% frontend cycles idle     ( +-  2.94% ) [44.56%]
      621,104,447      stalled-cycles-backend:HG #   30.26% backend  cycles idle     ( +-  3.48% ) [44.69%]
    2,700,410,991      instructions:HG           #    1.32  insns per cycle        
                                                  #    0.45  stalled cycles per insn  ( +-  1.66% ) [55.94%]
      486,476,408      branches:HG               #  488.386 M/sec                    ( +-  1.70% ) [55.96%]
          959,651      branch-misses:HG          #    0.20% of all branches          ( +-  4.78% ) [55.82%]
      547,000,119      L1-dcache-loads:HG        #  549.147 M/sec                    ( +-  2.19% ) [55.67%]
        21,540,926      L1-dcache-load-misses:HG  #    3.94% of all L1-dcache hits    ( +-  2.73% ) [55.43%]
        5,751,650      LLC-loads:HG              #    5.774 M/sec                    ( +-  3.60% ) [44.21%]
  <not supported>      LLC-load-misses:HG       

      1.000126894 seconds time elapsed                                          ( +-  2.47% )

正如您所见，对于我的情况来说，原因是前端和后端拖延周期的数量要高得多。

那么这是从哪里来的呢？我敢打赌这归结于一些失败的内联，类似于这里所解释的内容：std::vector performance regression when enabling C++11

确实，启用-flto可以使结果平衡：

Performance counter stats for './pair' (10 runs):

      1021.922944      task-clock:HG (msec)      #    0.997 CPUs utilized            ( +-  1.15% )
                63      context-switches:HG       #    0.062 K/sec                    ( +- 77.23% )
                5      cpu-migrations:HG         #    0.005 K/sec                    ( +- 34.21% )
          195,396      page-faults:HG            #    0.191 M/sec                    ( +-  0.00% )
    2,109,877,147      cycles:HG                 #    2.065 GHz                      ( +-  0.92% ) [44.33%]
    1,098,031,078      stalled-cycles-frontend:HG #   52.04% frontend cycles idle     ( +-  0.93% ) [44.46%]
      701,553,535      stalled-cycles-backend:HG #   33.25% backend  cycles idle     ( +-  1.09% ) [44.68%]
    3,288,420,630      instructions:HG           #    1.56  insns per cycle        
                                                  #    0.33  stalled cycles per insn  ( +-  0.88% ) [55.89%]
      672,941,736      branches:HG               #  658.505 M/sec                    ( +-  0.80% ) [56.00%]
          660,278      branch-misses:HG          #    0.10% of all branches          ( +-  2.05% ) [55.93%]
      474,314,267      L1-dcache-loads:HG        #  464.139 M/sec                    ( +-  1.32% ) [55.73%]
        19,481,787      L1-dcache-load-misses:HG  #    4.11% of all L1-dcache hits    ( +-  0.80% ) [55.51%]
        5,155,678      LLC-loads:HG              #    5.045 M/sec                    ( +-  1.69% ) [44.21%]
  <not supported>      LLC-load-misses:HG       

      1.025083895 seconds time elapsed                                          ( +-  1.03% )

对于元组：

Performance counter stats for './tuple' (10 runs):

      1018.980969      task-clock:HG (msec)      #    0.999 CPUs utilized            ( +-  0.47% )
                8      context-switches:HG       #    0.008 K/sec                    ( +- 29.74% )
                3      cpu-migrations:HG         #    0.003 K/sec                    ( +- 42.64% )
          195,396      page-faults:HG            #    0.192 M/sec                    ( +-  0.00% )
    2,103,574,740      cycles:HG                 #    2.064 GHz                      ( +-  0.30% ) [44.28%]
    1,088,827,212      stalled-cycles-frontend:HG #   51.76% frontend cycles idle     ( +-  0.47% ) [44.56%]
      697,438,071      stalled-cycles-backend:HG #   33.15% backend  cycles idle     ( +-  0.41% ) [44.76%]
    3,305,631,646      instructions:HG           #    1.57  insns per cycle        
                                                  #    0.33  stalled cycles per insn  ( +-  0.21% ) [55.94%]
      675,175,757      branches:HG               #  662.599 M/sec                    ( +-  0.16% ) [56.02%]
          656,205      branch-misses:HG          #    0.10% of all branches          ( +-  0.98% ) [55.93%]
      475,532,976      L1-dcache-loads:HG        #  466.675 M/sec                    ( +-  0.13% ) [55.69%]
        19,430,992      L1-dcache-load-misses:HG  #    4.09% of all L1-dcache hits    ( +-  0.20% ) [55.49%]
        5,161,624      LLC-loads:HG              #    5.065 M/sec                    ( +-  0.47% ) [44.14%]
  <not supported>      LLC-load-misses:HG       

      1.020225388 seconds time elapsed                                          ( +-  0.48% )

所以记住，-flto 是你的朋友，而失败的内联可能会对大量模板化的代码产生极端影响。使用perf stat查找正在发生的情况。

- milianw

---

PS：我认为pair较慢，因为它可能使用元组实现，并碰巧达到了内联深度限制。 - milianw

错误的假设。std::pair 要求有两个名为 first 和 second 的真实数据成员，所以它不能用其他任何东西来实现。 - Sebastian Redl

在C++11中出现元组（tuple）之前，pair已经被引入到C++中，因此它不能由元组实现。此外，谁会为简单的结构使用更复杂的结构呢？ - phuclv

@LưuVĩnhPhúc pair 仍然可以使用 tuple 实现。我想代码是不断重写的。例如，C++ 编译器 就是 用 C++ 编写的 :) - Slaus

Answer 2

milianw没有讨论-O0与-O2的区别，因此我想为此添加说明。

如果没有优化，std::tuple比std::pair慢是完全可以预料的，因为它是更复杂的对象。一对具有精确的两个成员，因此它的方法很容易定义。但是元组具有任意数量的成员，并且迭代模板参数列表的唯一方法是使用递归。因此，大多数针对元组的函数处理一个成员，然后递归处理其余成员，因此对于二元组，您将有两倍的函数调用。

现在，当它们被优化时，编译器将内联该递归，因此不应存在显着差异。测试清楚地证实了这一点。这适用于一般情况下严重依赖模板的内容。可以编写模板以提供无或非常少的运行时开销的抽象，但这依赖于优化以内联所有微不足道的函数。

- Jan Hudec

---

我本来会沿着同样的推理线回答（任意数量的参数），但后来我发现std::tuple有一个额外的构造函数用于对成对参数的处理（http://www.cplusplus.com/reference/tuple/tuple/tuple/ (5)），这应该可以避免参数列表的迭代。 - Sorin Totuarez

那个构造函数在这里没有被使用。而且即使使用了，也无法避免递归，因为元组本身的结构是递归的。 - Jan Hudec

这是语言要求的吗？我本以为std::tuple可能会在标准中被规定为这样，但实现可以按照自己的意愿进行。例如，对于所有常见的（<9个元素）元组大小都有专门的特化。 - davidbak