Сито из кода etotosthenes ускоряется в последовательных прогонах - почему?

Question

Я быстро проверил этот вопрос, но не смог найти ответ - хотя я думаю, что он мог быть поднят здесь раньше.

Я возился с написанием простой реализации сита eratosthenes в 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

et c.

Если я повторяю это несколько раз, кажется, что выполнение кода всегда примерно в 5 раз медленнее в первый раз, чем все последующие времена.

В чем причина этого?

Я запускаю его на MacBook Pro 2017 года с двухъядерным процессором Intel Core i5 2,3 ГГц и компилирую с помощью Apple Clang версии 11.0.0 (Clang -1100.0.33.12

Answer 1

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

Поэтому для сравнения нескольких алгоритмов по времени выполнения рекомендуется запустить сотню раз и взять наименьшее время.

Answer 2

Учитывая очень большую разницу, я предполагаю, что ЦП находится в режиме более низкой производительности, когда вы запускаете первый запуск, но затем при загрузке с первого запуска ОС переключает его в режим более высокой производительности, который вы наблюдаете как уменьшенное время выполнения.

Убедитесь, что ваш ноутбук подключен к источнику питания A C, и что все опции энергосбережения отключены, если вы хотите избежать эффекта.

В любом случае будет все еще остаются эффекты кэширования (например, содержимое исполняемого файла может быть кэшировано в памяти). Но я думаю, что они не должны быть порядка 100 мс.

В общем, когда вы тестируете код, вы всегда должны выполнять прогрев, потому что всегда будут такие эффекты в некоторой степени по одной причине или еще один. Как правило, вы хотите выполнить реальные тестовые прогоны, когда, так сказать, среда достигла состояния равновесия.

Answer 3

Когда программа запускается несколько раз, когда ОС в первый раз загружает файл в память, в следующий раз он, вероятно, уже будет присутствовать (хотя в некоторых случаях может потребоваться перемещение в зависимости от настроек компилятора / компоновщика, а именно, от положения независимый код генерируется). Ответ о расположении филиала будет гораздо более вероятным, если вы выполняли один и тот же код много раз в рамках одного процесса (что является хорошей идеей при сборе данных о производительности - поместите код синхронизации в свою программу и несколько раз запускайте интересующий код). время каждого l oop вместо запуска всей вашей программы несколько раз и использования внешней программы времени).