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

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

根据我以前对基准转换的经验,它们通常比原始循环执行得稍快,当然,它们更安全,所以我尝试用转换、生成和为每个原始循环替换所有原始循环。今天,我比较了使用for-each、transform和raw循环翻转布尔值的速度,得到了非常令人惊讶的结果。原始回路的执行速度是其他两个回路的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)
enter image description here

最佳答案

在本例中,clang对索引进行矢量化,但(错误地)未能对迭代进行矢量化。
为了总结结果,使用原始循环与使用std::transformstd::for_each没有区别。然而,使用索引和使用迭代之间有一个区别,对于这个特定的问题,clang在优化索引方面比优化迭代更好,因为索引是矢量化的。std::transformstd::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); 

当使用从beginend的指针或迭代器时,这些函数的性能与使用std::for_eachstd::transform相同。
Clang Quick-bench results:
enter image description here
这可以通过在本地运行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:
enter image description here
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更擅长对一些数学运算进行向量化。

相关文章:

c++ - 用于iostream的C ++包装器类,使用带有运算符<< [duplicate]的std :: endl等流修饰符

c++ - Qt中的C ++信号到QML插槽

python - 在Python 2中有效地对10 ** 6位数字进行排序

c++ - C ++ 17在编译时将带有已删除副本构造函数的类添加到std :: vector

c++ - 可变参数模板中的功能参数

c++ - 控制台宽度;假设默认还是被设为……?

c++ - boost :: shared_ptr并分配派生类

c - 有人可以解释以下内存分配C程序的性能行为吗?

c# - 将List <T>定制为ListCustomMinIndexedForEach <T>的问题(从无关的实现中剥离)

c++ - 为STL随机数生成器编写Factory方法