bool 数组上的 Raw Loop 比转换或 for_each 快 5 倍

Question

根据我之前在基准测试 transform 和 for_each 方面的经验，它们通常比原始循环执行得稍快，当然，它们更安全，所以我尝试用 transform、generate 和for_each。今天，我比较了使用 for_each、转换和原始循环翻转布尔值的速度，我得到了非常令人惊讶的结果。 raw_loop 执行速度比其他两个快 5 倍。我真的找不到一个很好的理由来说明为什么我们会产生如此巨大的差异？

#include <array>
#include <algorithm>


static void ForEach(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    std::for_each(a.begin(), a.end(), [](auto & arg) { arg = !arg; });
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(ForEach);

static void Transform(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    std::transform(a.begin(), a.end(), a.begin(), [](auto arg) { return !arg; });
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(Transform);


static void RawLoop(benchmark::State& state) {
  std::array<bool, sizeof(short) * 8> a;
  std::fill(a.begin(), a.end(), true);

  for (auto _ : state) {
    for (int i = 0; i < a.size(); i++) {
      a[i] = !a[i];
    }
    benchmark::DoNotOptimize(a);
  }
}
BENCHMARK(RawLoop);

clang++ (7.0) -O3 -libc++ (LLVM)

Answer 1

在这个例子中，clang 向量化索引但（错误地）未能向量化迭代。

总结结果，使用原始循环与使用 std::transform 或 std::for_each 之间没有区别。 但是，有区别在使用索引和使用迭代之间，以及为了 这个特定问题 的目的，clang 在优化索引方面比在优化迭代方面更好，因为索引被矢量化了。 std::transform 和 std::for_each 使用迭代，所以它们最终变得更慢（在 clang 下编译时）。

索引和迭代有什么区别？ - 索引是当您使用整数索引到数组时 - 迭代是指将指针从 begin() 递增到 end()。

让我们使用索引和迭代来编写原始循环，并比较迭代（使用原始循环）与索引的性能。

// Indexing
for(int i = 0; i < a.size(); i++) {
    a[i] = !a[i];
}

// Iterating, used by std::for_each and std::transform
bool* begin = a.data();
bool* end   = begin + a.size(); 
for(; begin != end; ++begin) {
    *begin = !*begin; 
}

使用索引的示例是 better-optimized，使用 clang 编译时运行速度提高 4-5 倍。

为了证明这一点，让我们添加两个额外的测试，都使用原始循环。一个将使用迭代器，另一个将使用原始指针。


static void RawLoopIt(benchmark::State& state) {
  std::array<bool, 16> a;
  std::fill(a.begin(), a.end(), true); 

  for(auto _ : state) {
    auto scan = a.begin(); 
    auto end = a.end(); 
    for (; scan != end; ++scan) {
      *scan = !*scan; 
    }
    benchmark::DoNotOptimize(a); 
  }
 }

BENCHMARK(RawLoopIt); 

static void RawLoopPtr(benchmark::State& state) {
  std::array<bool, 16> a;
  std::fill(a.begin(), a.end(), true); 

  for(auto _ : state) {
    bool* scan = a.data(); 
    bool* end = scan + a.size(); 
    for (; scan != end; ++scan) {
      *scan = !*scan; 
    }
    benchmark::DoNotOptimize(a); 
  } 
}

BENCHMARK(RawLoopPtr);

当使用从 begin 到 end 的指针或迭代器时，这些函数在性能上 与使用 std::for_each 或 std::transform.

Clang Quick-bench results:

运行当地的 clang 基准测试证实了这一点：

me@K2SO:~/projects/scratch$ clang++ -O3 bench.cpp -lbenchmark -pthread -o clang-bench
me@K2SO:~/projects/scratch$ ./clang-bench
2019-07-05 16:13:27
Running ./clang-bench
Run on (8 X 4000 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.44, 0.55, 0.59
-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
ForEach          8.32 ns         8.32 ns     83327615
Transform        8.29 ns         8.28 ns     82536410
RawLoop          1.92 ns         1.92 ns    361745495
RawLoopIt        8.31 ns         8.31 ns     81848945
RawLoopPtr       8.28 ns         8.28 ns     82504276

GCC 没有这个问题。

就此示例而言，索引或迭代之间没有根本区别。它们都对数组应用了相同的转换，编译器应该能够对它们进行相同的编译。

的确，GCC 能够做到这一点，所有方法运行 比在 clang 下编译的相应版本更快 。

GCC Quick-bench results:

GCC 本地结果：

2019-07-05 16:13:35
Running ./gcc-bench
Run on (8 X 4000 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 8192K (x1)
Load Average: 0.52, 0.57, 0.60
-----------------------------------------------------
Benchmark           Time             CPU   Iterations
-----------------------------------------------------
ForEach          1.43 ns         1.43 ns    484760981
Transform        1.44 ns         1.44 ns    485788409
RawLoop          1.43 ns         1.43 ns    484973417
RawLoopIt        1.44 ns         1.44 ns    482685685
RawLoopPtr       1.44 ns         1.44 ns    483736235

索引实际上比迭代更快吗？不。索引速度更快，因为 clang 对其进行了矢量化。

在幕后，既不会迭代也不会索引。相反，gcc 和 clang vectorize 通过将数组视为两个 64 位整数并在其上使用 bitwise-xor 来对操作进行矢量化。我们可以在用于翻转位的程序集中看到这一点：

       movabs [=15=]x101010101010101,%rax
       nopw   %cs:0x0(%rax,%rax,1)
       xor    %rax,(%rsp)
       xor    %rax,0x8(%rsp)
       sub    [=15=]x1,%rbx

迭代速度较慢当由 clang 编译时 因为出于某种原因，clang 在使用迭代时无法向量化操作。 这是clang 中的一个缺陷，并且专门适用于此问题。随着 clang 的改进，这种差异应该会消失，这不是我现在会担心的事情。

不要micro-optimize。让编译器处理它，如有必要，测试 gcc 或 clang 是否为您的特定 use-case 生成更快的代码 。两者都不是对所有情况都更好。例如，clang 更擅长向量化一些数学运算。

bool 数组上的 Raw Loop 比转换或 for_each 快 5 倍

Raw Loop on an array of bool is 5 times faster than transform or for_each

c++

performance

clang++

c++17

在这个例子中，clang 向量化索引但（错误地）未能向量化迭代。

GCC 没有这个问题。

索引实际上比迭代更快吗？不。索引速度更快，因为 clang 对其进行了矢量化。