c++ - 如何理解棘手的加速

Question

抱歉这个问题可能太抽象了，但对我来说这很实用+可能有一些专家有类似的经验并且可以解释一下。

我有一个大代码，大约 10000 行大小。

我注意到如果我放在某个地方

if ( expression ) continue;

其中表达式总是假(用代码和cout的逻辑双重检查)，但取决于未知参数(因此编译器在编译期间不能简单地去掉这一行)程序的速度增加25%(计算结果相同)。如果我测量循环本身的速度，则加速因子大于 3。

为什么会发生这种情况以及在没有这些技巧的情况下使用这种加速可能性的可能方法是什么？

附:我使用 gcc 4.7.3，-O3 优化。

---

更多信息:

1. 我尝试了两种不同的表达方式，都有效。

2. 如果我将这一行改为:

   if ( expression ) { cout << " HELLO " << endl; continue; };
   

   加速消失了。

3. 如果我将这一行改为:

   expression;
   

   加速消失了。

4. 围绕该行的代码如下所示:

   for ( int i = a; ;  ) {
     do {
       i += d;
       if ( d*i > d*ilast ) break;
   
         // small amount of calculations, and conditional calls of continue;
   
     } while ( expression0 );
     if ( d*i > dir*ilast ) break;
   
     if ( expression ) continue;
   
      // very big amount calculations, and conditional calls of continue;
   
   }
   

   for 循环看起来很奇怪。这是因为我已经修改了循环以捕获这个瓶颈。最初表达式等于表达式0，而不是do-loop，我只有这个继续。

5. 我尝试使用 __builtin_expect 来理解分支预测。与

     // the expression (= false) is supposed to be true by branch prediction.
   if ( __builtin_expect( !!(expression), 1) ) continue; 
   

   速度提升 25%。

     // the expression (= false) is supposed to be false by branch prediction.
   if ( __builtin_expect( !!(expression), 0) ) continue; 
   

   加速消失了。

6. 如果我使用 -O2 而不是 -O3 效果就消失了。该代码比带有 false 条件的快速 O3 版本稍慢 (~3%)。

7. “-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize”也是如此。再加一个选项:“-O2 -finline-functions -funswitch-loops -fpredictive-commoning -fgcse-after-reload -ftree-vectorize -fipa-cp-clone”效果会被放大。使用“line”的速度是一样的，没有“line”的代码会慢 75%。

8. 原因就在条件运算符后面。所以代码看起来像这样:

   for ( int i = a; ;  ) {
   
         // small amount of calculations, and conditional calls of continue;
   
     if ( expression ) continue;
   
       // calculations1
   
     if ( expression2 ) {
       // calculations2
     }
   
      // very big amount calculations, and conditional calls of continue;
   
   }
   

   表达式2 的值几乎总是假的。所以我改成这样:

   for ( int i = a; ;  ) {
   
         // small amount of calculations, and conditional calls of continue;
   
     // if ( expression ) continue; // don't need this anymore
   
       // calculations1
   
     if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
       // calculations2
     }
   
      // very big amount calculations, and conditional calls of continue;
   
   }
   

   并且已经获得了预期的 25% 加速。甚至更多一点。而且行为不再取决于临界线。

如果有人知道 Material ，可以不用猜测就能解释这种行为，我会很高兴阅读并接受他们的回答。

Answer 1

找到了。

原因在于下面的条件运算符。所以代码看起来像这样:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  if ( expression ) continue;

    // calculations1

  if ( expression2 ) {
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

表达式2 的值几乎总是假的。所以我改成这样:

for ( int i = a; ;  ) {

      // small amount of calculations, and conditional calls of continue;

  // if ( expression ) continue; // don't need this anymore

    // calculations1

  if ( __builtin_expect( !!(expression2), 0 ) ) { // suppose expression2 == false
    // calculations2
  }

   // very big amount calculations, and conditional calls of continue;

}

并且已经获得了预期的 25% 加速。甚至更多一点。而且行为不再取决于临界线。

---

我不知道如何解释，也找不到足够的分支预测 Material 。

但我想重点是应该跳过计算2，但编译器不知道这一点，并且默认情况下假设表达式2 == true。 同时假设在简单的继续检查中

if ( expression ) continue;

expression == false，并且很好地跳过了计算2，因为在任何情况下都必须这样做。 如果我们有更复杂的操作(例如 cout)，它会假设表达式为真并且这个技巧不起作用。

如果有人知道 Material ，可以不用猜测就能解释这种行为，我会很高兴阅读并接受他们的回答。