std::tuple比std::array更快吗？

Question

我有一个二维数组，列数固定为4，但行数非常大。我发现使用vector<tuple>而不是vector<array>或vector<vector>可以快近两倍，比后者快五倍。虽然使用tuple有点麻烦，但我定义了一个访问函数来解决这个问题：

typedef tuple<int,int,int,int> Tuple;
// access the i-th element
inline int &tget (Tuple &t, int i) {
    switch (i) {
        case 0: return std::get<0>(t); 
        case 1: return std::get<1>(t); 
        case 2: return std::get<2>(t); 
        case 3: return std::get<3>(t); 
    }   
}
vector<Tuple> array; 
// this gives the element in i-th row and j-th column
tget(array[i],j); 

我觉得这非常令人惊讶，想知道这种性能提升来自哪里，是否存在一种类似于vector<vector>或vector<array>的简洁解决方案，使用下标operator[]，并具有与tuple相同的性能？ 更新： 我正在使用带有标准的，并使用-O3进行优化。 因为有人问操作，所以在此进行解释。首先，2D数组被填充了多达1M行。首先我会预留空间，然后使用push_back函数添加元素。然后我对数组进行排序，最后在其中进行二进制搜索。

这是我编写的代码块。输入将是几个测试用例(=T)，每个测试用例都需要一个整数(N最大为20)，然后再读取N个整数到中。由于该函数具有指数特性，因此总和变得非常大（4^(N/2) 最高约一百万）。要在数组和元组之间进行测试，请切换typedef并注释/取消注释访问函数中的返回行。有四行/块必须在// if array// if tuple注释中进行切换，并且注释指定在注释中。

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
#include <array>
using namespace std;

typedef vector<int>::iterator VecIt;

// HERE you can switch between the two types 
typedef tuple<int,int,int,int> Tuple;       // define it as a tuple
//typedef array<int,4> Tuple;               // define it as array
inline int &tget (Tuple &t, int i) {
  //  return t[i];                          // if it's an array, uncomment This too

  // if it's an array comment the switch case                                                                                                                                                                                                                                                                                                                                                                                                                                               
    switch (i) {
        case 0: return std::get<0>(t);
        case 1: return std::get<1>(t);
        case 2: return std::get<2>(t);
        case 3: return std::get<3>(t);
        default:
          cerr << "tuple index out of bound" << endl;
    }
}

void comp_sums(VecIt v, VecIt vend, vector<Tuple> &sums){
    if (v==vend)
        return;
    int size = sums.size();
    for (int i=0; i<size; i++) {
        for (int j=1; j<4; j++){
            sums.push_back(sums[i]);
            tget(sums.back(),j) += *v;
        }
        tget(sums[i],0) += *v;
    }
    v++;
    comp_sums(v, vend, sums);
}

void docase( ) {
    int N;
    cin >> N;
    vector<int> lens(N);
    int lsum = 0;
    for (int i=0; i<N; i++) {
        cin >> lens[i];
        lsum += lens[i];
    }
    if (lsum % 4 != 0 ) {
        cout << 0 << endl;
        return;
    }
    lsum = lsum/4;

    vector<Tuple> sums1, sums2;
    Tuple z(0,0,0,0);                             // if it's a tuple
    //Tuple z = {0,0,0,0};                        // If it's an array 
    sums1.push_back(z); sums1.reserve(1<<N/2);
    sums2.push_back(z); sums2.reserve(1<<N/2);
    comp_sums(lens.begin()+1, lens.begin()+N/2, sums1);
    comp_sums(lens.begin()+N/2+1, lens.end(), sums2);
    sort(sums1.begin(), sums1.end());
    sort(sums2.begin(), sums2.end());
    long count = 0;
    for (int i=0; i<sums1.size(); i++) {
        for (int k=0; k<4; k++) {
            //Tuple t({lsum,lsum,lsum,lsum});     // if it's an array
            Tuple t(lsum,lsum,lsum,lsum);         // if it's a tuple
            for (int j=0; j<4; j++)
                tget(t,j) -= tget(sums1[i],(j+k)%4);
            tget(t,k) -= lens[0];
            tget(t,0) -= lens[N/2];
            bool neg = false;
            for (int j=0; j<4; j++)
                if (tget(t,j)<0){
                    neg = true;
                    break;
                }
            if (neg)
                continue;
            auto LB = lower_bound(sums2.begin(), sums2.end(), t);
            auto UB = upper_bound(LB, sums2.end(), t);
            count += (UB - LB);
        }
    }
    cout << count/6 << endl;
}


int main() {
    std::ios_base::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) docase();
}

这里还有一个我使用的测试输入。第一行表示有T = 18个不同的测试用例。每个测试用例的第一行是N（最多20），然后是N个整数。算法呈指数增长，因此小数字并不意味着只有几个操作。在测量时间时，我已经考虑了I/O：

18
8
132391 123854 21536 19482 133025 10945 121800 10311
8                                                                                                                                                             
12 4 12 4 4 12 12 24
8
131723 16253 23309 132227 125171 12253 16757 136227
8
8 4 4 8 4 8 12 24
8
12 12 12 8 4 8 12 28
8
115021 114654 112093 17443 20371 17810 17274 115190
8
8 8 4 4 12 4 12 20
8
12 4 4 4 4 12 12 28
8
8 12 8 12 8 4 12 28
8
4 12 8 12 8 8 4 24
20
34836 56869 24112 27796 198091 196472 50364 27364 29572 53701 52981 25779 202644 204884 53840 30056 48705 53092 43751 18419
20
207447 26867 41968 35977 36384 57042 40981 30191 47705 26907 248361 26003 53715 48237 27691 192772 60507 58194 20754 245913
20
34836 56869 24112 27796 198091 196472 50364 27364 29572 53701 52981 25779 202644 204884 53840 30056 48705 53092 43751 18419
20
207447 26867 41968 35977 36384 57042 40981 30191 47705 26907 248361 26003 53715 48237 27691 192772 60507 58194 20754 245913
20
4 2 2 4 4 2 4 2 4 2 2 4 4 3 3 4 2 3 4 1
20
2 3 2 2 3 2 3 4 3 2 4 4 4 3 2 3 4 4 3 3
20
4 4 4 4 3 3 3 2 2 4 2 4 2 2 4 2 2 2 2 1
20
4 4 2 3 4 3 4 3 2 4 4 2 2 4 3 4 3 3 2 4

- Ameer Jewdaki

---

你能展示一下基准测试结果吗，其中包括编译器和编译选项对性能提升的影响？ - nwp

我对你的发现感到非常惊讶。您启用了优化吗？ - Quentin

如果您没有进行基准测试，那么您是如何确定速度翻倍的呢？您一定以某种方式进行了测量。 - UnholySheep

“Extraordinary claims require extraordinary evidence”这句话的意思是，对于那些超乎寻常的主张，我们需要提供更为充分、更为可靠的证据。简单的解释是不够的，我们必须提供最小化、完整化和可验证化的例子来支持我们的观点。 - user7860670

基本上，我们不相信你。同样大小的“元组”和“数组”应该是相同的速度，所以我们认为还有其他的因素不同。 - Martin Bonner supports Monica

Answer 1

我猜测瓶颈是 std::tuple 的 operator< 与 std::array 相比。如果你使用以下这个用户自定义结构体：

struct my_struct {
    int a, b, c, d;
};

inline bool operator<(my_struct const& lhs, my_struct const& rhs) {
    return std::tie(lhs.a, lhs.b, lhs.c, lhs.d) <
        std::tie(rhs.a, rhs.b, rhs.c, rhs.d);
}

这比使用 std::tuple 或 std::array 慢了约5倍（在我的电脑上使用MinGW和Wandbox测试过）。

此外，operator< 的汇编代码对于 std::tuple 和 std::array 是不同的（使用 -O3），这可能解释了 std::tuple 和 std::array 之间的性能差异。

fun(std::array<int, 4ul> const&, std::array<int, 4ul> const&):
  mov ecx, DWORD PTR [rdi]
  cmp DWORD PTR [rsi], ecx
  lea rdx, [rsi+16]
  lea rax, [rdi+16]
  jg .L32
  jl .L31
.L25:
  add rdi, 4
  add rsi, 4
  cmp rax, rdi
  je .L36
  mov ecx, DWORD PTR [rsi]
  cmp DWORD PTR [rdi], ecx
  jl .L32
  jle .L25
.L31:
  xor eax, eax
  ret
.L32:
  mov eax, 1
  ret
.L36:
  cmp rdx, rsi
  setne al
  ret

fun(std::tuple<int, int, int, int> const&, std::tuple<int, int, int, int> const&):
  mov edx, DWORD PTR [rsi+12]
  cmp DWORD PTR [rdi+12], edx
  mov eax, 1
  jl .L11
  mov eax, 0
  jg .L11
  mov ecx, DWORD PTR [rsi+8]
  cmp DWORD PTR [rdi+8], ecx
  mov eax, 1
  jl .L11
  mov eax, 0
  jg .L11
  mov ecx, DWORD PTR [rsi+4]
  cmp DWORD PTR [rdi+4], ecx
  mov eax, 1
  jl .L11
  mov eax, 0
  jg .L11
  mov eax, DWORD PTR [rsi]
  cmp DWORD PTR [rdi], eax
  setl al
.L11:
  rep ret

- Holt

---

在元组的情况下，同时发生更多的操作/比较。就像我在我的答案中所说的：结构体上的操作比数组上的操作更好优化。 - Robert Andrzejuk

@RobertAndrzejuk 您是对的，所有 operator< 都是内联的，我不知道为什么上一次检查时不是这样。 "结构体的操作更容易优化" - 这似乎并不正确，因为1）在Wandbox上，数组的性能比元组好，2）如果是这种情况，我的自定义结构体应该像元组一样运行（operator< 的生成的汇编代码相同），或者至少比数组更好。 - Holt

Answer 2

另一个问题与您的问题类似： 用分层结构和类替换数组是否可行？

它包含代码和基准测试。

基本上发生的是，元组创建了一个结构，编译器能够更好地优化操作，而不是在元素数组上进行操作。

- Robert Andrzejuk