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

Question

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

我正在忙着用 C++ 编写埃拉托色尼筛法的简单实现并对结果进行计时：

#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 双核英特尔酷睿 i5 上使用 Apple clang 版本 11.0.0 (clang-1100.0.33.12

进行编译

Answer 1

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

所以要通过执行时间来比较几个算法，最好是运行一百次并花费最少的时间。

Answer 2

鉴于差异非常大，我猜测当您启动第一个运行时 CPU 处于较低性能模式，但随后从第一个运行开始加载OS 将其切换到更高性能模式，您观察到执行时间缩短。

确保您的笔记本电脑已连接到交流电源，并且如果您想避免这种影响，请禁用所有节能选项。

在任何情况下，缓存效果仍然存在（例如，可执行文件中的内容可能缓存在内存中）。但我认为这些不应该在 100 毫秒的数量级。

一般来说，当您对代码进行基准测试时，您应该始终进行预热运行s，因为出于某种原因总会在某种程度上产生这种影响。您通常希望在环境达到平衡状态时执行实际测试运行s，可以这么说。

Answer 3

当运行第一次 OS 多次调用程序时， OS 必须将文件加载到内存中，下一次它可能已经存在（尽管重定位可能仍然是必要的）取决于 compiler/linker 设置，即是否生成位置无关代码）。如果您运行在单个进程中多次使用相同的代码，则分支位置答案更有可能适用（这在收集性能数据时是个好主意 - 将计时代码放入程序中运行多次感兴趣的代码，为每个循环计时，而不是运行多次 ning 整个程序并使用外部时间程序）。

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

Sieve of eratosthenes c++ code speeds up in consecutive runs - why?

c++

cpu

performance