循环内if（循环不变）if语句的编译器优化

Question

我在 C 中有一个这样的函数（在伪代码中，删除了不重要的部分）：

int func(int s, int x, int* a, int* r) {
    int i;

    // do some stuff

    for (i=0;i<a_really_big_int;++i) {
        if (s) r[i] = x ^ i;
        else r[i] = x ^ a[i];
        // and maybe a couple other ways of computing r
        // that are equally fast individually
    }

    // do some other stuff

}

这段代码被调用得太多，以至于这个循环实际上是代码中的速度瓶颈。我想知道一些事情：

1. 由于 switch

   s

   是函数中的常量，好的编译器会优化循环以使分支不会一直减慢速度吗？

2. 如果没有，有什么好的方法来优化这段代码？

====

这是包含更完整示例的更新：

int func(int s,
         int start,int stop,int stride,
         double *x,double *b,
         int *a,int *flips,int *signs,int i_max,
         double *c)
{
  int i,k,st;
  for (k=start; k<stop; k += stride) {
    b[k] = 0;
    for (i=0;i<i_max;++i) {

      /* this is the code in question */
      if (s) st = k^flips[i];
      else st = a[k]^flips[i];
      /* done with code in question */

      b[k] += x[st] * (__builtin_popcount(st & signs[i])%2 ? -c[i] : c[i]);
    }
  }
}

---

编辑2：

如果有人好奇，我最终重构了代码并将整个内部 for 循环（带有

i_max

）提升到外面，使

really_big_int

循环变得更加简单，并且希望易于矢量化！ （并且还避免无数次执行一堆额外的逻辑）

Answer 1

优化代码的一个明显方法是将条件拉到循环之外：

if (s)
    for (i=0;i<a_really_big_int;++i) {
        r[i] = x ^ i;
    }
else
    for (i=0;i<a_really_big_int;++i) {
        r[i] = x ^ a[i];
    }

精明的编译器也许能够将其更改为一次多个元素的 r[] 赋值。

Answer 2

微观优化

通常不值得花时间——审查更大的问题更有效。

然而，要进行微观优化，尝试各种方法，然后对它们进行分析以找到最好的方法，可以做出适度的改进。

除了 @wallyk 和 @kabanus 好的答案之外，一些简单的编译器还受益于以 0 结尾的循环。

// for (i=0;i<a_really_big_int;++i) {
for (i=a_really_big_int; --i; ) {

---

[编辑第二次优化]

OP 添加了一个更完整的示例。问题之一是编译器无法假设

b

指向的内存与其他内存不重叠。这会阻止某些优化。

假设它们实际上不重叠，请在

restrict

上使用

b

来允许优化。

const

对于无法推断出这一点的较弱编译器也有帮助。

restrict

如果参考数据不重叠，其他人也可能受益。

// int func(int s, int start, int stop, int stride, double *x,
//     double *b, int *a, int *flips,
//     int *signs, int i_max, double *c) {

int func(int s, int start, int stop, int stride, const double * restrict x,
    double * restrict b, const int * restrict a, const int * restrict flips, 
    const int * restrict signs, int i_max, double *c) {

Answer 3

您的所有命令都是循环中的快速 O(1) 命令。

if

绝对是经过优化的，如果您的所有命令都是

r[i]=somethingquick

形式，那么您的 for+if 也是如此。您的问题可能归结为 big int 可以有多小？

快速

int main

从

INT_MIN

到

INT_MAX

求和为一个长变量，在 Windows 上的 Ubuntu 子系统上对我来说大约需要 10 秒。您的命令可能会将其乘以几倍，很快就会达到一分钟。最重要的是，如果您确实进行了大量迭代，这可能是无法避免的。

如果

r[i]

是独立计算的，这将是线程/多处理的经典用法。

编辑：

我认为

%

无论如何都会被编译器优化，但如果没有，请注意

x & 1

对于奇数/偶数检查要快得多。

Answer 4

假设x86_64，您可以确保指针对齐到16字节并使用intrinsics。如果它仅在具有 AVX2 的系统上运行，您可以使用 __mm256 变体（与 avx512* 类似）

int func(int s, int x, const __m128i* restrict a, __m128i* restrict r) {
    size_t i = 0, max = a_really_big_int / 4;
    __m128i xv =  _mm_set1_epi32(x);
    // do some stuff
    if (s) {
        __m128i iv = _mm_set_epi32(3,2,1,0); //or is it 0,1,2,3?
        __m128i four = _mm_set1_epi32(4);
        for ( ;i<max; ++i, iv=_mm_add_epi32(iv,four)) {
            r[i] = _mm_xor_si128(xv,iv);
        }
    }else{ /*not (s)*/
        for (;i<max;++i){
            r[i] = _mm_xor_si128(xv,a[i]);
        }
    }
    // do some other stuff   
}

Answer 5

虽然

if

语句将在任何像样的编译器上进行优化（除非你要求编译器不要优化），但我会考虑将优化写入（以防万一你在没有优化的情况下编译）。

此外，虽然编译器可能会优化“绝对”

if

语句，但我会考虑手动优化它，要么使用任何可用的内置函数，要么使用按位操作。

即

b[k] += x[st] *
        ( ((__builtin_popcount(st & signs[I]) & 1) *
           ((int)0xFFFFFFFFFFFFFFFF)) ^c[I] );

这将取

popcount

的最后一位（1 == 奇数，0 == 偶数），将其乘以常量（如果是奇数则所有位为 1，如果为真则所有位为 0），然后对

c[I]

值进行异或（与

0-c[I]

或

~(c[I])

相同。

这将避免在第二个

absolute

if 语句未优化的情况下发生指令跳转。

附注

我使用了一个 8 字节长的值，并通过将其转换为

int

来截断其长度。这是因为我不知道

int

在您的系统上可能有多长（在我的系统上是 4 个字节，即

0xFFFFFFFF

）。