布尔数组上的Raw Loop比transform或for_each快5倍

Question

根据我以前在基准测试transform和for_each上的经验，它们的执行速度通常比原始循环要快一些，并且它们当然更安全，因此我尝试将所有原始循环替换为transform，generate和for_each。今天，我比较了可以使用for_each，transform和raw循环翻转布尔值的速度，并且得到了非常令人惊讶的结果。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 对索引进行矢量化，但（错误地）未能对迭代进行矢量化。

总结结果，使用原始循环和使用or之间没有区别。std::transformstd::for_each然而，使用索引和使用迭代之间存在差异，并且就这个特定问题而言，clang 更擅长优化索引而不是优化迭代，因为索引已矢量化。std::transform并std::for_each使用迭代，因此它们最终会变慢（在 clang 下编译时）。

索引和迭代有什么区别？ - 索引是指使用整数对数组进行索引 - 迭代是指从begin()to递增指针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; 
}

使用索引的示例得到了更好的优化，使用 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); 

当使用指针或迭代器 from beginto时end，这些函数的性能与使用or相同。std::for_eachstd::transform

Clang 快速实验结果：

通过在本地运行 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 快速实验结果：

海湾合作委员会本地结果：

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通过将数组视为两个 64 位整数并对它们使用按位异或来向量化操作。我们可以在用于翻转位的汇编中看到这一点：

       movabs $0x101010101010101,%rax
       nopw   %cs:0x0(%rax,%rax,1)
       xor    %rax,(%rsp)
       xor    %rax,0x8(%rsp)
       sub    $0x1,%rbx

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

不要进行微观优化。让编译器处理这个问题，如有必要，测试 gcc 或 clang 是否会为您的特定用例生成更快的代码。两者都不是对所有情况都更好。例如，clang 更擅长向量化一些数学运算。