第一个方法调用比使用相同数据的连续调用长10倍

Question

我正在为执行quicksort执行一些执行时间基准测试。在完全相同的输入数据的100次连续测量中，似乎对quicksort的第一次调用大约比所有连续调用长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

是的，它可能是页面上的页面错误，其中包含sort函数的代码（以及时序代码本身）。 10x还可以包括提升到最大turbo时钟速度。

但缓存并不合理：除非编译器以某种方式使用Timer的构造函数对init进行重新排序，否则您将在定时区域外编写（微小）数组。内存分配第一次慢得多，很容易解释它，可能不得不进行系统调用以便第一次获取新页面，但后来调用new（构造std :: vector）只是抓住已经热门的内容从空闲列表中缓存内存。

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

请注意，每次调用时都会使用srand()生成相同的随机数组。要测试分支预测是否为解释，请删除srand，以便每次都获得不同的数组，并查看时间是否保持更高。

你使用什么CPU，编译器版本/选项等？

Answer 2

可能是因为缓存，因为内存需要从DRAM中获取并在第一次在CPU的数据缓存中分配。这比在CPU缓存中遇到的负载多得多（多）延迟。

然后，当您的指令在管道中时，它们遵循相同的分支，因为它是来自相同内存源的指令，因为它不需要被无效，因为它是相同的指针。

如果您实现具有或多或少相同功能的4个方法然后在它们之间交换以查看发生的情况，那将会很有趣。