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

u2nhd7ah 于 2023-01-16 发布在其他

关注(0)|答案(5)|浏览(150)

我是一名R开发人员，使用C语言进行算法开发，我有一个问题，为什么一个看起来很慢的C循环实际上比另一种方法快。
在R中，我们的布尔类型实际上可以有三个值，true、false和na，我们在C级别上使用int来表示。
我正在研究一个向量化的&&操作（是的，我们在R中已经有了这个操作，请耐心等待），它也可以处理na的情况。

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

注意，它的工作原理类似于C中的&&，只是na值在与false以外的任何值组合时传播，在这种情况下，我们“知道”&&永远不会为真，所以我们返回false。
现在来看实现。假设我们有两个向量，v_out和v_x，我们想对它们执行向量化&&。我们可以用结果覆盖v_out。一个选项是：

// 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，编译时使用的是Clang。

It 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;
}

基于评论中的几个问题，这里有几点需要澄清，以供未来读者参考：

我在一台2018年的15英寸MacBook Pro上，配备了2. 9 GHz的6核英特尔i9-8950HK（6核Coffee Lake）
我测试的特定Clang版本是Apple clang version 13.1.6 (clang-1316.0.21.2.5)和Target: x86_64-apple-darwin21.6.0
我受到R的限制，只能使用int作为数据类型（尽管有更有效的选项），并使用以下编码：false = 0、true = 1、na = INT_MIN。我提供的可重现示例考虑到了这一点。
最初的问题实际上并不是要求代码运行得更快。我只是想了解一下我的两种if/else方法之间的区别。也就是说，一些答案表明 branchless 方法可以更快，我真的很感谢那些用户提供的解释！这极大地影响了我正在工作的实现的最终版本。

来源：https://stackoverflow.com/questions/73816657/why-is-this-seemingly-slower-c-loop-actually-twice-as-fast-as-the-other-way

5条答案

按热度按时间

pdsfdshx1#

**如果您希望快速矢量化代码，一般不要执行短路求值，也不要执行分支。**您希望编译器能够使用8位元素，通过SIMD运算一次处理16或32个元素。（编译器可以将if优化为无分支代码，前提是无条件地执行这项工作是安全的，包括解引用，而且没有副作用，这被称为 if-conversion，通常对于像这样的代码的自动矢量化是必要的。）

你也不想让编译器担心它不被允许访问一些内存，因为C抽象机不允许。例如，如果所有的v_out[i]元素都是false，v_x可能是一个NULL指针，而不会导致UB！所以编译器 * 不能 * 发明对C逻辑根本不读的对象的读访问。
如果v_x真的是一个数组，而不仅仅是一个指针，那么编译器就会知道它是可读的，并且可以通过将短路逻辑转换为无分支来发明对它的访问。（如自动矢量化），它可能选择不这样做。分支代码在实践中经常会因为真假（和NA）的随机混合而变慢。
正如您在编译器的汇编输出（Clang 15 -O2 on Compiler Explorer）中所看到的，选项1使用SIMD进行自动矢量化，并行地无分支处理4个可选布尔值（仅使用SSE2，更多使用-march=native）。它可能反映了Apple Clang将对main中的真实的代码执行的操作。）

**支持NA状态的3态布尔值可以用2位实现，其方式与按位AND执行&&运算的方式相同。**您可以将其数组存储为每个unsigned char一个数组，或每个字符压缩4个数组，从而将矢量化运算的吞吐量提高四倍，但代价是访问速度变慢。（或者通常每个char对应CHAR_BIT/2，但在主流的x86 C实现中，这是4。）

F = 00
N = 10（二进制，因此C 0b10又称为2）
T = 11
转换为具有val & 1的bool。
转换 * 从 * bool到0b11 * b或其他东西，以将低位广播到两个位置。

F & anything = 0，因为F是全零位。这对于任何位模式都是成立的，“聪明”的部分是N&T = T&N = N，因为T中的set位是N中的set位的超集。

这也适用于||和按位|：F|N == N和F|T == T，因为0|x == x。对于任何相同的输入，也是x|x == x，所以我们仍然可以在那里使用。

N = 0b10在执行“或”运算时不会设置低位，但在执行“与”运算时会将其清除。
我忘了你说的是C而不是C++，所以这个基本的类 Package 器（只够演示几个测试调用者）可能不相关，但是在纯C中为unsigned char *c1, *c2执行c1[i] &= c2[i];的循环将以完全相同的方式自动矢量化。

struct NBool{ // Nullable bool, should probably rename to optional bool
    unsigned char val;
    static const unsigned char F = 0b00;
    static const unsigned char T = 0b11;
    static const unsigned char N = 0b10;  // N&T = N;  N&N = N;  N&F = F

    auto operator &=(NBool rhs){   // define && the same way if you want, as non-short-circuiting
        val &= rhs.val;
        return *this;
    }
    operator bool() { return val & 1; }

    constexpr NBool(unsigned char x) : val(x) {};
    constexpr NBool& operator=(const NBool &) = default;

};

#include <stdint.h>
#include <stdlib.h>

bool test(NBool a){
    return a;
}

bool test2(NBool a){
    NBool b = NBool::F;
    return a &= b;   // return false
}

void foo(size_t len, NBool *a1, NBool *a2 )
{
    for (std::size_t i = 0 ; i < len ; i++){
        a1[i] &= a2[i];
    }
}

（我认为“Nullable”并不是一个真正正确的术语，它可以是NaN / NA;读起来总是安全的，而且它不是一个引用，可能是optional_bool，就像C++ std::optional，它是一个值，可能存在，也可能不存在。
这个代码是在编译器资源管理器上用GCC和Clang编译的，Clang自动矢量化非常好，用一个展开的循环执行vandps。在-march=haswell上，vpand具有更好的吞吐量。）但是无论如何它仍然受到1/时钟存储和2/时钟负载的限制;即使数据在L1 d高速缓存中是热的，这也会在具有如此低的计算强度的加载/存储上形成很多瓶颈。
（英特尔的优化手册指出，即使Skylake的峰值L1 d带宽是每时钟2个负载+1个存储（96字节，32字节向量），持续带宽更像是每时钟84字节。）
它仍然可以相对接近于每个时钟周期32字节的AND，AVX，所以这是32个NBool &操作，或者如果每个字节封装4个NBool，每个时钟128个。
可以使用pslld xmm, 7/pmovmskb将NBools压缩为1位bool的压缩位图，以提取每个字节的低位（在将其移位到高位之后）。
如果每个字节存储4个字节，则某些SIMD位操作是为了打包成布尔值，可能是将vpshufb打包成4位LUT，以便将NBool对打包成半字节底部的一对布尔值，然后合并？或者使用标量BMI 2 pext从64位中每隔一位提取一次，如果您使用Zen 3或Haswell或更高版本，用于快速pext。