Первый вызов метода занимает в 10 раз больше, чем последовательные вызовы с одинаковыми данными. - PullRequest
Новая
       34

Первый вызов метода занимает в 10 раз больше, чем последовательные вызовы с одинаковыми данными.

2 голосов
/ 13 марта 2019

Я выполняю некоторые тесты времени выполнения для моей реализации быстрой сортировки. Кажется, что из 100 последовательных измерений на одних и тех же входных данных первый вызов быстрой сортировки занимает примерно в 10 раз больше времени, чем все последующие вызовы. Является ли это следствием того, что операционная система готовится выполнить программу, или есть какое-то другое объяснение? Кроме того, разумно ли отбрасывать первое измерение при вычислении среднего времени выполнения?

На приведенной ниже гистограмме показано время выполнения (в миллисекундах) в зависимости от номера вызова метода. Каждый раз, когда метод вызывается, он обрабатывает одни и те же данные.

execution time vs. method call number

Чтобы получить этот конкретный граф, основной метод вызывает 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

Ответы [ 2 ]

3 голосов
/ 14 марта 2019

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

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

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

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

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

0 голосов
/ 14 марта 2019

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

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

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

...