为什么C++代码的位置会影响性能？

Question

我正在进行一项性能测试，并发现改变代码的顺序可以使其更快，而不会影响结果。

性能是使用chrono库来测量时间执行。

vector< vector<float> > U(matrix_size, vector<float>(matrix_size,14));
vector< vector<float> > L(matrix_size, vector<float>(matrix_size,12));
vector< vector<float> > matrix_positive_definite(matrix_size, vector<float>(matrix_size,23));

for (i = 0; i < matrix_size; ++i) {         
   for(j= 0; j < matrix_size; ++j){
//Part II : ________________________________________
    float sum2=0;               
    for(k= 0; k <= (i-1); ++k){
      float sum2_temp=L[i][k]*U[k][j];
      sum2+=sum2_temp;
    }
//Part I : _____________________________________________
    float sum1=0;       
    for(k= 0; k <= (j-1); ++k){
      float sum1_temp=L[i][k]*U[k][j];
      sum1+=sum1_temp;
    }           
//__________________________________________
    if(i>j){
      L[i][j]=(matrix_positive_definite[i][j]-sum1)/U[j][j]; 
    }
    else{
       U[i][j]=matrix_positive_definite[i][j]-sum2;
    }   
   }
}

我使用 g++ -O3 (GCC 7.4.0 在 Intel i5/Win10 上) 进行编译。

如果 Part II 在 Part I 之前执行，则改变 Part I & Part II 的顺序可以获得更快的结果。发生了什么?

以下是整个程序的链接。

- cho_uc

---

多快？ - Evg

我有点希望-O3应该能够知道哪个顺序更可取。 事实上存在差异是奇怪的。 这可能与内存中分配这些“矩阵”的位置有关（与对齐有关）。 因此，有时一个版本比另一个版本更快，而在某些情况下则相反。（附言：不要使用vector<vector>表示矩阵，这是一个糟糕的选择。） - ALX23z

我使用clang 7.0和gcc 8.2运行了两个版本，发现在性能方面没有任何差异。 - mfnx

“@ALX23z 我有点期望 -O3 应该能够知道哪个顺序更可取。” 我不这么认为...编译器非常聪明...但还没有那么聪明...我很确定没有编译器会交换第一部分和第二部分。 - mfnx

顺便提一下，你在做冗余的工作，你两次求和了部分 0..min(i,j)。而且，你扔掉了其中一个 sum1/sum2。我会先重构这段代码，避免不必要的计算。也许编译器能够在某个版本中注意到这一点，而在另一个版本中则不能。 - geza

Answer 1

我会尝试使用perf stat -d <app>运行两个版本，并查看性能计数器差异所在。

当进行基准测试时，您可能希望固定CPU频率，以避免影响分数。

---

将循环对齐到32字节边界通常会增加8-30%的性能。更多细节请参见Causes of Performance Instability due to Code Placement in X86 - Zia Ansari, Intel。

尝试使用-O3 -falign-loops=32 -falign-functions=32 -march=native -mtune=native编译您的代码。

- Maxim Egorushkin

---

我使用了“-O3 -march=native -mtune=native -falign-loops=32 -falign-functions=32”，但仍然得到了相同的结果。无论何时编译，结果都是一致的（快3-4倍）。不过还是谢谢你，你提供的链接可能可以给我一些启示。 - cho_uc

@cho_uc 我建议你使用 perf stat -d <app> 运行两个版本，看看性能计数器的差异在哪里。 - Maxim Egorushkin

Answer 2

运行perf stat -ddd命令，与提供的程序一起玩耍，可以发现两个版本之间的主要区别在于预取。"最初的回答"

part II -> part I   and   part I -> part II (original program)
   73,069,502      L1-dcache-prefetch-misses

part II -> part I   and   part II -> part I (only the efficient version)
   31,719,117      L1-dcache-prefetch-misses

part I -> part II   and   part I -> part II (only the less efficient version)
  114,520,949      L1-dcache-prefetch-misses

注意：根据编译器探查器，part II -> part I 与 part I -> part II 非常相似。

我猜，在对 i 进行第一次迭代时，part II 几乎没有作用，但对 j 进行迭代会使 part I 按照一种模式访问 U[k][j]，这将为下一次对 i 的迭代提供便利的预取。

原始答案翻译成“最初的回答”。

- prog-fh

Answer 3

更快的版本类似于将循环移动到 if (i > j) 内部时获得的性能。

if (i > j) {
    float sum1 = 0;
    for (std::size_t k = 0; k < j; ++k){
        sum1 += L_series[i][k] * U_series[k][j];
    }
    L_parallel[i][j] = matrix_positive_definite[i][j] - sum1;
        L[i][j] /= U[j][j];
}
if (i <= j) {
    float sum2 = 0;
    for (std::size_t k = 0; k < i; ++k){
        sum2 += L_series[i][k] * U_series[k][j];
    }
    U_parallel[i][j] = matrix_positive_definite[i][j] - sum2;
}

我会假设在某些情况下编译器能够自行进行转换。对于我来说，这只发生在-O3。 （1950X，msys2 / GCC 8.3.0，Win10）

我不知道这是哪种优化，以及必须满足什么条件才能应用它。这不是-O3明确列出的选项之一（-O2+全部选项还不够）。显然，当使用std::size_t而不是int作为循环计数器时，它已经不再执行。

- Darklighter

---

将int更改为std::size_t，将k <= (i-1)更改为k < i，将k <= (j-1)更改为k < j仍然会给我带来相同的性能差距。但是您的答案可能让我想到了为什么我有奇怪的表现。我猜测当i=0或j=0时程序的行为会很奇怪，因为此时我们有k=-1。 - cho_uc

@cho_uc，我已经添加了我的系统规格，你能否也把你的加到问题中呢？ - Darklighter

这里不是 k = -1，而是条件 k <= -1，但是对我没有任何影响。 - Darklighter

完成！我正在使用Intel i5/Win10上的Cygwin GCC 7.4.0（没有并行化）。 - cho_uc