问题：

为什么这个看起来较慢的C循环实际上是另一种方式的两倍？

司徒运锋

2023-03-14

我是一名将C用于算法目的的R开发人员，我有一个问题，为什么看起来很慢的C循环实际上比其他方法更快。

在R中，我们的布尔类型实际上可以有3个值，true、false和na，我们在C级别使用int表示这一点。

我正在研究矢量化

 F && F == F
 F && T == F
 F && N == F

 T && F == F
 T && T == T
 T && N == N

 N && F == F
 N && T == N
 N && N == N

请注意，它的工作原理如下

现在到实现，假设我们有两个向量v_out和v_x，我们想执行矢量化的

// Option 1
for (int i = 0; i < size; ++i) {
  int elt_out = v_out[i];
  int elt_x = v_x[i];

  if (elt_out == 0) {
    // Done
  } else if (elt_x == 0) {
    v_out[i] = 0;
  } else if (elt_out == na) {
    // Done
  } else if (elt_x == na) {
    v_out[i] = na;
  }
}

另一种选择是：

// Option 2
for (int i = 0; i < size; ++i) {
  int elt_out = v_out[i];

  if (elt_out == 0) {
    continue;
  }

  int elt_x = v_x[i];

  if (elt_x == 0) {
    v_out[i] = 0;
  } else if (elt_out == na) {
    // Done
  } else if (elt_x == na) {
    v_out[i] = na;
  }
}

我有点期望第二个选项更快，因为它避免了在不需要时访问v_x[i]。但事实上，当使用-O2编译时，它的速度是原来的两倍！

在下面的脚本中，我得到以下计时结果。请注意，我在Mac上，并用叮当声编译。

Seems reasonable with O0, they are about the same.
2x faster with O2 with Option 1!

Option 1, `clang -O0`
0.110560

Option 2, `clang -O0`
0.107710

Option 1, `clang -O2`
0.032223

Option 2, `clang -O2`
0.070557

有人能解释一下这是怎么回事吗？我最大的猜测是，这与选项1中v_x[i]总是被线性访问有关，这非常快。但是在选项2中，v_x[i]本质上是随机访问的（某种程度上），因为它可能访问v_x[10]，但不需要从v_x直到v_x[120]的另一个元素，因为这种访问不是线性的，所以可能要慢得多。

可复制的脚本:

#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
#include <time.h>

int main() {
  srand(123);

  int size = 1e7;
  int na = INT_MIN;

  int* v_out = (int*) malloc(size * sizeof(int));
  int* v_x = (int*) malloc(size * sizeof(int));

  // Generate random numbers between 1-3
  // 1 -> false
  // 2 -> true
  // 3 -> na
  for (int i = 0; i < size; ++i) {
    int elt_out = rand() % 3 + 1;

    if (elt_out == 1) {
      v_out[i] = 0;
    } else if (elt_out == 2) {
      v_out[i] = 1;
    } else {
      v_out[i] = na;
    }

    int elt_x = rand() % 3 + 1;

    if (elt_x == 1) {
      v_x[i] = 0;
    } else if (elt_x == 2) {
      v_x[i] = 1;
    } else {
      v_x[i] = na;
    }
  }

  clock_t start = clock();

  // Option 1
  for (int i = 0; i < size; ++i) {
    int elt_out = v_out[i];
    int elt_x = v_x[i];

    if (elt_out == 0) {
      // Done
    } else if (elt_x == 0) {
      v_out[i] = 0;
    } else if (elt_out == na) {
      // Done
    } else if (elt_x == na) {
      v_out[i] = na;
    }
  }

  // // Option 2
  // for (int i = 0; i < size; ++i) {
  //   int elt_out = v_out[i];
  //
  //   if (elt_out == 0) {
  //     continue;
  //   }
  //
  //   int elt_x = v_x[i];
  //
  //   if (elt_x == 0) {
  //     v_out[i] = 0;
  //   } else if (elt_out == na) {
  //     // Done
  //   } else if (elt_x == na) {
  //     v_out[i] = na;
  //   }
  // }

  clock_t end = clock();
  double time = (double) (end - start) / CLOCKS_PER_SEC;

  free(v_out);
  free(v_x);

  printf("%f\n", time);
  return 0;
}

更新:基于评论中的几个问题，以下是对未来读者的几点澄清:

> < li>

我使用的是2018款15英寸Macbook Pro，配有2.9 GHz 6核英特尔酷睿i9处理器。

我用Apple clang版本13.1.6（clang-1316.0.21.2.5）和目标：x86_64-Apple-darwin21.6.0

我受到R的限制，只能使用int作为数据类型（即使有更有效的选项）和以下编码：false=0， na=int_MIN 。我提供的可复制示例尊重这一点。

最初的问题实际上并不是请求让代码运行得更快，我只是想知道我的两种if/else方法之间的区别。也就是说，一些答案表明无分支方法可以快得多，我真的很感谢那些用户提供的解释！这极大地影响了我正在开发的实现的最终版本。

共有3个答案

邵阳德

2023-03-14

请注意，它的工作原理如下

与其将值表示为严格的枚举，不如允许2或3的数值来表示na（您可以在显示时检查这一点，或者在所有数字处理之后进行规范化步骤）。这样，不需要条件逻辑（因此也不需要昂贵的分支预测）：我们只是逻辑-或位于2s位置的位（无论运算符如何），以及逻辑-和（或任何运算符）位于1s位置的位。

int is_na(int value) {
    return value & 2;
}

void r_and_into(unsigned* v_out, unsigned* v_x, int size) {
  for (int i = 0; i < size; ++i) {
    unsigned elt_out = v_out[i];
    unsigned elt_x = v_x[i];
    // this can probably be micro-optimized somehow....
    v_out[i] = (elt_out & elt_x & 1) | ((elt_out | elt_x) & 2);
  }
}

如果我们被迫使用INT_MIN来表示N/A值，我们可以从观察2s补码中的情况开始：它只有一个位集（符号位，在无符号值中最重要）。因此，我们可以使用该位值而不是具有相同无条件逻辑的2，然后将任何（INT_MIN|1）结果更正为INT_MIN：

const unsigned MSB_FLAG = (unsigned)INT_MIN;

void r_and_into(int* v_out, int* v_x, int size) {
  for (int i = 0; i < size; ++i) {
    unsigned elt_out = (unsigned)v_out[i];
    unsigned elt_x = (unsigned)v_x[i];
    elt_out = (elt_out & elt_x & 1) | ((elt_out | elt_x) & MSB_FLAG);
    // if the high bit is set, clear the low bit
    // I.E.: AND the low bit with the negation of the high bit.
    v_out[i] = (int)(elt_out & ~(elt_out >> 31));
  }
}

（所有这些强制转换可能不是必需的，但我认为使用无符号类型进行按位操作是一种很好的做法。无论如何，它们都应该得到优化。）