Первый вызов метода занимает в 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;
   }

Процессор и компиляция

Процессор: Broadwell 2,7 ГГц Intel Core i5 (5257U)

Версия компилятора: Apple LLVM версия 10.0.0 (clang-1000.11.45.5)

Параметры компилятора: -std=c++17 -O2 -march=native

Answer 1

Да, это может быть ошибка страницы на странице, содержащей код для функции сортировки (и сам код синхронизации). 10x также может включать в себя увеличение до максимальной скорости турбо тактовой частоты.

Кэширование, однако, неправдоподобно: вы пишете (крошечный) массив за пределами временной области, если компилятор каким-то образом не переупорядочил init с помощью конструктора вашего Timer, Выделение памяти намного медленнее в первый раз, это легко объяснимо, возможно, придется сделать системный вызов, чтобы получить новую страницу в первый раз, но позже вызовы new (чтобы создать std::vector), просто извлекая уже загруженную память из свободного списка.

Обучение предикторов ветвления также может быть важным фактором, но вы ожидаете, что потребуется более 1 прогона, прежде чем предикторы ветвей TAGE в современном процессоре Intel или предикторы персептрона в современном AMD "изучат" полную схему: все ветвления. Но, может быть, они сблизятся после первого запуска.

Обратите внимание, что каждый раз вы создаете один и тот же случайный массив, используя srand() на каждый звонок. Чтобы проверить, является ли предсказание ветвления объяснением, удалите srand так что вы каждый раз получаете разные массивы и смотрите, будет ли время намного выше.

Какой процессор, версию / опции компилятора и т. Д. Вы используете?

Answer 2

Вероятно, это связано с кэшированием, поскольку память должна быть извлечена из DRAM и выделена в кэш данных ЦП с первого раза. Это требует (намного) больше задержки, чем нагрузки, которые попадают в кэш процессора.

Затем, когда ваши инструкции находятся в конвейере, они следуют той же ветке, что и инструкции из того же источника памяти, поскольку их не нужно аннулировать, поскольку указатель тот же.

Было бы интересно, если бы вы реализовали 4 метода с более или менее одинаковыми функциями, а затем переключились между ними, чтобы посмотреть, что произойдет.