为什么GCC不尽可能地优化这组分支和条件？

Question

以下三段代码实现了完全相同的效果.然而,当在GCC 4.5.2上使用-O3编译时,许多迭代的时间变化非常明显.

1 - 正常分支,使用多个条件,最佳时间1.0:

// a, b, c, d are set to random values 0-255 before each iteration.
if (a < 16 or b < 32 or c < 64 or d < 128) result += a+b+c+d;

2 - 分支,手动使用按位或检查条件,最佳时间0.92:

if (a < 16 | b < 32 | c < 64 | d < 128) result += a+b+c+d;

3 - 最后,在没有分支的情况下获得相同的结果,最佳时间为0.85:

result += (a+b+c+d) * (a < 16 | b < 32 | c < 64 | d < 128);

当我作为基准程序的内循环运行时,上述时间对于每种方法都是最佳的.该random()接种每次运行前以同样的方式.

在我做这个基准之前,我假设GCC会优化差异.特别是第二个例子让我抓狂了头.任何人都可以解释为什么GCC不会将这样的代码变成等效的快速代码吗？

编辑:修正了一些错误,并明确表示无论是否使用,都会创建随机数,以免被优化掉.他们总是在原始基准测试中,我只是拙劣地把我放在这里的代码.

以下是实际基准测试功能的示例:

boost::random::mt19937 rng;
boost::random::uniform_int_distribution<> ranchar(0, 255);

double quadruple_or(uint64_t runs) {
  uint64_t result = 0;
  rng.seed(0);

  boost::chrono::high_resolution_clock::time_point start = 
    boost::chrono::high_resolution_clock::now();
  for (; runs; runs--) {
    int a = ranchar(rng);
    int b = ranchar(rng);
    int c = ranchar(rng);
    int d = ranchar(rng);
    if (a < 16 or b < 32 or c < 64 or d < 128) result += a;
    if (d > 16 or c > 32 or b > 64 or a > 128) result += b;
    if (a < 96 or b < 53 or c < 199 or d < 177) result += c;
    if (d > 66 or c > 35 or b > 99 or a > 77) result += d;
  }

  // Force gcc to not optimize away result.
  std::cout << "Result check " << result << std::endl;
  boost::chrono::duration<double> sec = 
    boost::chrono::high_resolution_clock::now() - start;
  return sec.count();
}

完整的基准可以在这里找到.

Answer 1

自我原来的答案以来,OP已经改变了一点.让我试着再次访问这里.

在情况1中,由于or短路,我希望编译器生成四个比较然后分支代码段.分支显然可能相当昂贵,特别是如果他们没有走预期的路径.

在第2种情况下,编译器可以决定进行所有四次比较,将它们转换为bool 0/1结果,然后将or所有四个部分按位,然后执行单个(附加)分支.这可能会对可能更少的分支进行更多比较.似乎减少分支数确实可以提高性能.

在第3种情况下,事情与2完全相同,除非最后通过明确地告诉编译器可以消除一个更多的分支"我知道结果将是零或一,所以只需将左边的东西乘以该值".乘法显然比硬件上的相应分支更快.这与第二个示例形成对比,在第二个示例中,编译器不知道按位的可能输出范围,or因此必须假设它可以是任何整数,并且必须进行比较和跳转.

历史的原始答案: 第一种情况在功能上与第二种和第三种情况不同,如果random有副作用(普通PRNG会这样),因此编制者可能会以不同方式对它们进行优化.具体来说,第一种情况只会random根据需要调用多次以通过检查,而在另外两种情况下random将始终调用四次.这将(假设random确实是有状态的)导致未来的随机数不同.

第二个和第三个之间的区别是因为编译器可能由于某种原因无法弄清楚按位的结果或者总是为0或1.当你给它一个提示来进行乘法而不是分支乘法可能由于流水线操作,出现的速度更快.