分支预测

现代 CPU 的流水线功能使得一个指令为执行完的时候就开始执行下一条指令，但是如果遇到分支，流水线就会停止。在遇到分支的时候 CPU 会进行预测，预测正确则继续执行，预测错误则回到分支重新执行。

  1. // 优化前
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <random>
  6. #include <chrono>
  8. constexpr size_t COUNT = 4 * 1024 * 1024;
  10. int main () {
  11.   std::default_random_engine e;
  12.   std::uniform_real_distribution<double> u(0.0, 1.0);
  13.   std::vector<double> vector(COUNT);
  14.   std::generate(vector.begin(), vector.end(), [&e, &u]() {return u(e);});
  16.   auto start_time = std::chrono::high_resolution_clock::now();
  17.   double res = 0;
  18.   for (int i = 0; i < COUNT; ++i) {
  19.     if (vector[i] > 0.5) {
  20.       res += vector[i];
  21.     }
  22.   }  
  24.   auto finish_time = std::chrono::high_resolution_clock::now();
  26.   std::clog
  27.   << "sum:"
  28.   << std::chrono::duration_cast<std::chrono::microseconds>(finish_time - start_time).count()
  29.   << "us"
  30.   << std::endl;
  32.   return 0;
  33. }
  35. // sum:38001us

遇到分支 vector[i] > 0.5 ，在 CPU 判断一个数字大于 0.5 之后，它会预测下一个数字也是大于 0.5 的。争对这个分支预测我们可以在创建完 vector 之后进行一次排序 std::sort(vector.begin(), vector.end()); 这样分支预测大部分时间都是正确的，除了在某个点上会错误。这样优化后的执行时间是 sum:14008us。

看出分支预测失败时对性能影响很大，我们尽量让分支预测成功，一种做法是让符合分支的和不符合分支的数分开放。实际编程要时刻注意数据和分支的对应，不要一次性去处理数据（sort）。毕竟 sort 对性能的开销也很大。

std::sort(vector.begin(), vector.end()); 可以用 std::partition(vector.begin(), vector.end(), [](double x) {return x < 0.5;}); 代替。

或者我们可以尽量避开分支 res += vector[i] > 0.5 ? vector[i] : 0; 代替分支。

如果一个分支的条件很少见 vector[i] > 0.99 我们可以加上 if (vector[i] > 0.99) [[unlikely]] {}（c++20） 来告诉编译器分支预测的概率。或者使用 __glibc_unlikely(vector[i] > 0.99) 牺牲可以移植性去提升性能。

内存访问

读取主存内存的时间往往是时钟周期的几百倍，意味着 CPU 在读取内存的 CPU 周期中，CPU 的控制单元会空闲几百个时钟周期。内存读取的特性，开销很大，批量读取（通常一次会读 64 个 字节）。

image.png

优化方法是，顺序访问优于随机访问，因为批量读取的特性，主存内存读取之后会将批量读取到的内容放到高速缓存中。

  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <random>
  5. #include <chrono>
  7. constexpr size_t COUNT = 4 * 1024 * 1024;
  9. int main () {
  10.   std::default_random_engine e;
  11.   std::uniform_real_distribution<double> u(0.0, 0.99);
  12.   std::vector<double> vector(COUNT);
  13.   std::generate(vector.begin(), vector.end(), [&e, &u]() {return u(e);});
  14.   std::vector<int> indexes(COUNT);
  15.   std::iota(indexes.begin(), indexes.end(), 0);
  17.   auto start_time = std::chrono::high_resolution_clock::now();
  18.   double res = 0;
  19.   for (int i = 0; i < COUNT; ++i) {
  20.     res += vector[indexes[i]];
  21.   }
  22.   auto finish_time = std::chrono::high_resolution_clock::now();
  24.   std::clog
  25.     << "sum:"
  26.     << res
  27.     << std::endl
  28.     << std::chrono::duration_cast<std::chrono::microseconds>(finish_time - start_time).count()
  29.     << "us"
  30.     << std::endl;
  32.   return 0;
  33. }
  35. // 16999us

如果在 indexes 后 std::random_shuffle(indexes.begin(), indexes.end()); 那么最后相加时间会是 33969us 。

我们可以尽量使用同一块内存去读写，这样效率更高。