erastosthenes c ++代码的筛选在连续运行中加快了速度-为什么？

Question

我对这个问题进行了快速检查，但找不到答案-尽管我想它可能以前曾在这里提过。

我在弄乱用C ++编写eratosthenes筛子的简单实现并确定结果的时间：

#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

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

所以要按执行时间比较一些算法，优良作法是运行一百次并花费最少的时间。

Answer 2

考虑到很大的差异，我猜想当您开始第一次运行时，CPU处于较低性能模式，但是在第一次运行时，在负载下，操作系统会将其切换为较高性能模式，您观察到它处于降低状态执行时间。

Answer 3

[当操作系统第一次必须将文件加载到内存中时多次运行程序时，下次可能已经存在该文件（尽管根据编译器/链接器的设置，仍然可能需要重定位，即位置是否独立）。 -code生成）。如果您在单个进程中多次运行相同的代码，则分支位置答案将更有可能适用（这是收集性能数据时的一个好主意-将时序代码放入程序中并多次运行感兴趣的代码，为每个循环计时，而不是多次运行整个程序并使用外部时间程序。]