c++ - bool 数组上的原始循环比转换或 for_each 快 5 倍

原文 标签 c++ performance c++17 clang++

根据我之前对转换和 for_each 进行基准测试的经验，它们的执行速度通常比原始循环稍快，当然，它们更安全，因此我尝试将所有原始循环替换为转换、生成和 for_each。今天，我比较了使用 for_each、transform 和 raw 循环翻转 bool 值的速度，我得到了非常令人惊讶的结果。 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)

在这个例子中，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; 
}

使用索引的示例得到了更好的优化，使用 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 矢量化 该操作通过将数组视为两个 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 更擅长向量化一些数学运算。