C语言 整数上的无分支条件-快，但它们可以做得更快

Question

我一直在试验以下内容，并注意到这里定义的无分支"if"(现在用&-!!代替*!!)可以在64位Intel目标上将某些瓶颈代码加速多达(几乎)2倍。

// Produces x if f is true, else 0 if f is false.
#define  BRANCHLESS_IF(f,x)          ((x) & -((typeof(x))!!(f)))
// Produces x if f is true, else y if f is false.
#define  BRANCHLESS_IF_ELSE(f,x,y)  (((x) & -((typeof(x))!!(f))) | 
                                     ((y) & -((typeof(y)) !(f))))

注意，f应该是一个相当简单的表达式，没有副作用，这样编译器才能做最好的优化。

性能高度依赖于CPU和编译器。无枝"if"性能优异，铿锵有力;不过，我还没有发现没有分支的"if/else"更快的情况。

我的问题是:这些是安全的和可移植的写(意思是保证在所有目标上给出正确的结果)，他们可以做得更快吗?

无分支if/else的示例用法

这些计算64位最小值和最大值。

inline uint64_t uint64_min(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a <= b), a, b);
}
inline uint64_t uint64_max(uint64_t a, uint64_t b)
{
  return BRANCHLESS_IF_ELSE((a >= b), a, b);
}

无分支if

示例用法

这是64位模块加法-它计算(a + b) % n。分支版本(未显示)严重遭受分支预测失败，但无分支版本非常快(至少使用clang)。

inline uint64_t uint64_add_mod(uint64_t a, uint64_t b, uint64_t n)
{
  assert(n > 1); assert(a < n); assert(b < n);
  uint64_t c = a + b - BRANCHLESS_IF((a >= n - b), n);
  assert(c < n);
  return c;
}

更新:无分支的完整具体工作示例

下面是一个完整的C11程序，它演示了一个简单的if条件的分支和无分支版本之间的速度差异，如果您想在您的系统上尝试它。该程序计算模幂，即(a ** b) % n，用于非常大的值。

要进行编译，请在命令行中使用以下命令:

• -O3(或任何你喜欢的高优化级别)
• -DNDEBUG(禁用断言，为了速度)
• -DBRANCHLESS=0或-DBRANCHLESS=1分别指定分支或无分支行为

在我的系统中，如下所示:

$ cc -DBRANCHLESS=0 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 0
CPU time:  21.83 seconds
foo = 10585369126512366091
$ cc -DBRANCHLESS=1 -DNDEBUG -O3 -o powmod powmod.c && ./powmod
BRANCHLESS = 1
CPU time:  11.76 seconds
foo = 10585369126512366091
$ cc --version
Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)
Target: x86_64-apple-darwin14.1.0
Thread model: posix

因此，无分支版本的速度几乎是我系统上分支版本的两倍(3.4 GHz)。英特尔酷睿i7)

// SPEED TEST OF MODULAR MULTIPLICATION WITH BRANCHLESS CONDITIONALS
#include <stdio.h>
#include <stdint.h>
#include <inttypes.h>
#include <time.h>
#include <assert.h>
typedef  uint64_t  uint64;
//------------------------------------------------------------------------------
#if BRANCHLESS
  // Actually branchless.
  #define  BRANCHLESS_IF(f,x)          ((x) & -((typeof(x))!!(f)))
  #define  BRANCHLESS_IF_ELSE(f,x,y)  (((x) & -((typeof(x))!!(f))) | 
                                       ((y) & -((typeof(y)) !(f))))
#else
  // Not actually branchless, but used for comparison.
  #define  BRANCHLESS_IF(f,x)          ((f)? (x) : 0)
  #define  BRANCHLESS_IF_ELSE(f,x,y)   ((f)? (x) : (y))
#endif
//------------------------------------------------------------------------------
// 64-bit modular multiplication.  Computes (a * b) % n without division.
static uint64 uint64_mul_mod(uint64 a, uint64 b, const uint64 n)
{
  assert(n > 1); assert(a < n); assert(b < n);
  if (a < b) { uint64 t = a; a = b; b = t; }  // Ensure that b <= a.
  uint64 c = 0;
  for (; b != 0; b /= 2)
  {
    // This computes c = (c + a) % n if (b & 1).
    c += BRANCHLESS_IF((b & 1), a - BRANCHLESS_IF((c >= n - a), n));
    assert(c < n);
    // This computes a = (a + a) % n.
    a += a - BRANCHLESS_IF((a >= n - a), n);
    assert(a < n);
  }
  assert(c < n);
  return c;
}
//------------------------------------------------------------------------------
// 64-bit modular exponentiation.  Computes (a ** b) % n using modular
// multiplication.
static
uint64 uint64_pow_mod(uint64 a, uint64 b, const uint64 n)
{
  assert(n > 1); assert(a < n);
  uint64 c = 1;
  for (; b > 0; b /= 2)
  {
    if (b & 1)
      c = uint64_mul_mod(c, a, n);
    a = uint64_mul_mod(a, a, n);
  }
  assert(c < n);
  return c;
}
//------------------------------------------------------------------------------
int main(const int argc, const char *const argv[const])
{
  printf("BRANCHLESS = %dn", BRANCHLESS);
  clock_t clock_start = clock();
  #define SHOW_RESULTS 0
  uint64 foo = 0;  // Used in forcing compiler not to throw away results.
  uint64 n = 3, a = 1, b = 1;
  const uint64 iterations = 1000000;
  for (uint64 iteration = 0; iteration < iterations; iteration++)
  {
    uint64 c = uint64_pow_mod(a%n, b, n);
    if (SHOW_RESULTS)
    {
      printf("(%"PRIu64" ** %"PRIu64") %% %"PRIu64" = %"PRIu64"n",
             a%n, b, n, c);
    }
    else
    {
      foo ^= c;
    }
    n = n * 3 + 1;
    a = a * 5 + 3;
    b = b * 7 + 5;
  }
  clock_t clock_end = clock();
  double elapsed = (double)(clock_end - clock_start) / CLOCKS_PER_SEC;
  printf("CPU time:  %.2f secondsn", elapsed);
  printf("foo = %"PRIu64"n", foo);
  return 0;
}

第二次更新:Intel vs. ARM性能

• 在32位ARM目标(iPhone 3GS/4S, iPad 1/2/3/4，由Xcode 6.1与clang编译)上的测试显示，在这些情况下，对于模幂代码，这里的无分支"if"实际上比三元?:慢2-3倍。因此，如果需要最大速度，这些无分支宏似乎不是一个好主意，尽管它们在需要恒定速度的极少数情况下可能有用。
• 在64位ARM目标(iPhone 6+， iPad 5)上，无分支的"if"运行速度与三进制?:相同-再次由Xcode 6.1与clang编译。
• 对于Intel和ARM(由clang编译)，无分支的"if/else"在计算min/max时大约是三元?:的两倍。

Answer 1

当然这是可移植的，!运算符保证给出0或1作为结果。然后将其提升为另一个操作数所需的任何类型。

正如其他人所观察到的，if-else版本的缺点是计算两次，但您已经知道了这一点，如果没有副作用，您就可以了。

让我吃惊的是你说这样更快。我本以为现代的编译器会自己执行这种优化。

编辑:所以我用两个编译器(gcc和clang)和配置的两个值测试了这个。

事实上，如果你没有忘记设置-DNDEBUG=1, 0版本的?:对gcc来说要好得多，并且做了我期望它做的事情。它基本上使用条件移动来使循环无分支。在这种情况下，clang不会进行这种优化，而是进行一些条件跳转。

对于带算术的版本，gcc的性能会变差。事实上，看到他这样做并不奇怪。它实际上使用imul指令，这些指令很慢。Clang在这里过得更好。"算术"实际上优化了乘法，并用条件移动代替了它们。

所以总结一下，是的，这是可移植的，但是如果这带来性能的改善或恶化将取决于你的编译器，它的版本，你正在应用的编译标志，你的处理器的潜力…