c++ - bool 数组上的Raw Loop比transform或for_each快5倍

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

根据我之前对transform和for_each进行基准测试的经验，它们的执行速度通常比原始循环要快一些，并且它们当然更安全，因此我尝试将所有原始循环替换为transform，generate和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更好地向量化了一些数学运算。