c++ - Eratosthenes C++代码筛在连续运行中会加快速度-为什么？

Question

我快速检查了一下这个问题，但找不到答案-尽管我猜可能是在这里提过的。

我在用C++编写一个简单的实现erathesthenes筛子的方法，并对结果计时:

#include <iostream> 
#include <math.h>


int main() {

  int n = 100000;
  int seive [n];

  for (int i=0; i<n; i++) {
    seive[i] = i;
  }

  for (int i=2; i < ceil(sqrt(n)); i++) {
    for (int j=i*2; j<=n; j+=i) {
      seive[j-1] = -9;
    }
  }

  for (int i=0; i<n; i++) {
    if (seive[i] != -9) {
      std::cout << i+1 << "\n";
    }
  }

  return 0;
}

我使用以下命令进行编译:

g++ seive.cpp -o seiveCpp

然后使用以下命令计时:

time ./seiveCpp

第一次:

./seiveCpp  0.01s user 0.01s system 10% cpu 0.184 total

第二次:

./seiveCpp  0.01s user 0.01s system 58% cpu 0.034 total

第三次:

./seiveCpp  0.01s user 0.01s system 59% cpu 0.037 total

等等

如果我重复多次，似乎第一次运行代码总是比所有连续时间慢5倍。

发生这种情况的原因是什么？

我正在2017年MacBook Pro，2.3 GHz双核Intel Core i5上运行此程序，并使用Apple clang版本11.0.0(clang-1100.0.33.12

Answer 1

原因是由于分支预测器。第一次运行计算机时，对程序一无所知，但是在执行计算机时，它会在代码跳转中(对于和如果)查找逻辑，然后可以更好地预测应采用哪个分支。在现代处理器中，命令流水线很长，因此正确的跳转预测可以显着减少工作时间。

因此，按执行时间比较几种算法，最好的做法是运行一百次并花费最少的时间。