c++ - 第一个方法调用比使用相同数据的连续调用花费的时间长 10 倍

Question

我正在为我的快速排序执行一些执行时间基准。在对完全相同的输入数据进行的 100 次连续测量中，第一次调用快速排序似乎比所有连续调用花费的时间大约长 10 倍。这是操作系统准备执行程序的结果，还是有其他解释？此外，在计算平均运行时间时丢弃第一次测量是否合理？

下面的条形图说明了执行时间(毫秒)与方法调用次数的关系。每次调用该方法时，它都会处理完全相同的数据。

要生成此特定图形，主要方法调用 quicksort_timer::time_fpi_quicksort(5, 100)，其实现如下所示。

static void time_fpi_quicksort(int size, int runs)
{
    std::vector<int> vector(size);
    for (int i = 0; i < runs; i++)
    {
        vector = utilities::getRandomIntVectorWithConstantSeed(size);
        Timer timer;
        quicksort(vector, ver::FixedPivotInsertion);
    }
}

getRandomIntVectorWithConstantSeed实现如下

   std::vector<int> getRandomIntVectorWithConstantSeed(int size)
   {
      std::vector<int> vector(size);
      srand(6475307);
      for (int i = 0; i < size; i++)
         vector[i] = rand();
      return vector;
   }

CPU 和编译

CPU:Broadwell 2.7 GHz Intel Core i5 (5257U)

编译器版本:Apple LLVM 版本 10.0.0 (clang-1000.11.45.5)

编译器选项:-std=c++17 -O2 -march=native

Answer 1

是的，它可能是包含排序函数代码(以及计时代码本身)的页面上的页面错误。 10x 还可以包括加速到最大涡轮时钟速度。

不过，缓存并不合理:您在计时区域外编写(微小)数组，除非编译器以某种方式使用您的 Timer 的构造函数对 init 进行了重新排序。第一次内存分配要慢得多很容易解释，也许第一次必须进行系统调用以获取新页面，但稍后调用 new (构造 std::vector)只是从空闲列表中获取缓存中已经很热的内存。

训练分支预测器也可能是一个重要因素，但您预计在现代 Intel CPU 中的 TAGE 分支预测器或 CPU 中的感知器预测器之前需要运行超过 1 次现代 AMD，“学习”了所有分支的完整模式。但也许他们在第一次运行后就接近了。

请注意，通过在每次调用时使用 srand()，您每次都会生成相同的随机数组。测试分支预测是否正确解释，删除 srand 这样你每次都会得到不同的数组，看看时间是否保持更高。

您使用的是什么 CPU、编译器版本/选项等？