为什么对std::tuple的std::vector进行排序比对std::array的std::vector进行排序更快？

Question

我很好奇对一个 vector <vector<int>> 进行排序是否比对一个 vector <array <int, 3>> 进行排序慢。这个 vector 的维度是 1000000 x 3，下面是我用来实现这个问题的驱动代码：

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
    vector <vector<int>> v(1000000, vector <int> (3));

    srand(time(nullptr));
    for(int i = 0; i < 1000000; ++i){
        for(int j = 0; j < 3; ++j){
            v[i][j] = rand();
        }
    }

    double start = clock();
    sort(v.begin(), v.end());
    cout << (clock()-start)/(CLOCKS_PER_SEC/1000) << endl;

    return 0;
}

使用gcc 7.5.0的命令"g++ -O3 sorting_test.cxx"编译，运行时间约为300毫秒。将v声明为vector <array <int, 3>>将运行时间减少一半，约为149毫秒。

然而，将v声明为vector <tuple<int, int, int>>比以上两种方式表现更好，平均运行时间大约为100毫秒。

我可以在某种程度上理解为什么array选项比vector选项更快(array大小是常量表达式，而不像vector)，但我不知道为什么tuple会胜过它们两个。有人能向我解释一下吗？

填充tuple <int, int, int>的代码如下：

srand(time(nullptr));
for(int i = 0; i < 1000000; ++i){
    get <0> (v[i]) = rand();
    get <1> (v[i]) = rand();
    get <2> (v[i]) = rand();
}

- ahskdjfk

---

我的猜测与 vector、array 和 tuple 中 < 运算符的定义有关。对于 vector 和 array，需要使用循环来比较。而 tuple 可能使用折叠操作，虽然比较次数相同，但没有循环开销。 - NathanOliver

展示填充元组向量的代码。另外，最好使用srand(0)以获得可重复的结果。 - rustyx

参见 此链接 了解什么是折叠表达式。 - NathanOliver

另外，向量指向动态分配的内存，这对缓存利用率来说不太好。而数组的向量存储所有数据都是连续的。此外，在64位结构中，交换两个向量涉及48字节，而在这种情况下仅交换数组的一半。 - Daniel Langr

内部执行交换。也许在“元组”情况下需要交换的内存量较少。 - Damien

Answer 1

虽然整个程序的反汇编过程太大了，但这展示了 array 和 tuple 之间 operator< 的核心区别：https://godbolt.org/z/h1Y33e

实际上，在元组版本中，您有三个元素的固定比较，而在数组版本中，您有一个循环。

尽管我感到惊讶的是编译器没有展开循环。

编辑：看起来clang优化它们都成为非循环代码：https://godbolt.org/z/cMExTb（我没有完全阅读它，但我只看到向前跳转）

- Fatih BAKIR

---

也许比较一下交换操作的汇编代码会很有趣：https://godbolt.org/z/sGsK7Y。 - Daniel Langr

在这种特定情况下（小数组），数组应该等于元组以达到更好的性能，但如果数组变得更大，则可能会失去优势。 - Waqar

对于clang汇编，数组和元组版本具有完全相同的指令，但由于libstdc++的std::tuple布局是反向的，它们以不同的顺序读取三个整数。 - Justin