Что заставляет мой цикл работать медленнее во время его первых итераций?

Question

Я написал следующую программу, чтобы немного поиграться с std :: chrono:

#include <iostream>
#include <chrono>

int main(int argc, char** argv) {
    const long iterationCount = 10000;
    long count = 0;
    for(long i = 0; i < iterationCount; i++) {
        auto start = std::chrono::high_resolution_clock::now();
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        count++;count++;count++;count++;count++;count++;count++;count++;count++;count++;
        auto end = std::chrono::high_resolution_clock::now();

        auto timeTaken = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
        std::cout << timeTaken << " " << std::endl;
    }
}

Я скомпилировал это с помощью G ++ без включенной оптимизации компилятора:

g++ chrono.cpp -o chrono

Впоследствии я запустил эту программу несколько раз и получил интересную схему.Для первых 500-1000 итераций программа работает примерно в 7-8 раз медленнее, чем для остальных итераций.

Вот пример выходных данных этой программы: https://pastebin.com/tUQsQEAQ

Что вызываетэто расхождение во время выполнения?Моей первой реакцией был кэш, но не заполнился ли он очень быстро?

В случае, если это имеет значение, моя операционная система - Ubuntu 18.04, а моя версия g ++ - 7.3.0.

Answer 1

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

Реализация Intel называется Turbo Boost .

Если вы отключите масштабирование частоты в своей системе (например, с помощью sudo cpupower frequency-set --governor performance - cpupower входит в пакет cpupowerutils), время каждой итерации будет более или менее одинаковым.

---

Сам цикл очень легко предсказать, вы можете ожидать только несколько неправильных предсказаний, если не один в конце от элемента управления цикла - код внутри библиотеки C ++, вероятно, труднее предсказать, но даже при что BPU не займет столько времени (1000 итераций), чтобы догнать ваш код.
Таким образом, вы можете исключить ошибочное прогнозирование отрасли.

Более или менее то же самое применимо к I-кешу (мало используется D-кеш, если реализация библиотеки C ++ не была слишком интенсивной при использовании переменных).
Код должен быть достаточно маленьким, чтобы поместиться в L1-I, и в основном даже в DSB.
Промахи L1-I не требуют 1000 итераций для разрешения, и если в кэше возникнет серьезный конфликт наборов, который будет отображаться как общее замедление, которое не исчезнет после 1000 итераций.

Вообще говоря, известно, что код выполняется быстрее со второй итерации цепочки зависимостей, переносимых циклами, поскольку первый раз, когда ЦП заполняет кэши (данные, инструкции, TLB).
В конечном итоге он может снова замедлиться, если у ЦП закончились ресурсы, например, если имеется большое давление порта (например, множество идентичных инструкций с ограниченным портом с большой задержкой), RS может заполнить остановку FE или, если есть много загрузки / магазина, заполняющего MOB / SB / LB, или много прыжков, заполняющих BOB.
Однако эти эффекты очень быстро проявляются настолько, что они доминируют во время выполнения кода.
В этом случае замедление происходит очень и очень поздно (во время процессора), что заставляет задуматься о процессе по требованию, таком как Turbo boost.

Answer 2

Как говорят другие, вы почти наверняка испытаете эффект динамического масштабирования частоты процессора.

Я могу воспроизвести ваши результаты на моей машине. Но если я отключу динамическое масштабирование частоты процессора с помощью утилиты cpufreq-set (чтобы процессор работал с постоянной частотой), эффект, который вы видите, исчезнет.

Answer 3

У меня нет физической машины linux для тестирования, но на Windows 10 x64 (i7) я получил такие результаты, как ...

395
16592
395
395
395
790
395
790
395
395
395
790

Что соответствует концу вашего следа. В Windows значение 395 кажется синхронизированным по фазе с счетчиком часов, поэтому длительность равна либо 395, 790, либо действительно большому числу (например, 116592). Действительно большое число выглядело бы как переключение контекста - когда наша программа не запущена.

Ваша программа на моем компьютере с Windows не имела начального замедления.

Однако результаты в целом выглядят очень похоже на результаты в файле pastebin.

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

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

Answer 4

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

Таким образом, обычная картина - видеть медленное время в течение первых нескольких миллисекунд, после чего время выполнения уменьшается (по мере ускорения ЦП) и в конечном итоге стабилизируется.

Answer 5

Я думаю, что причиной может быть разрешение часов. Вы находитесь в диапазоне, который может быть ниже разрешения вашей системы. Считайте эту цитату из документации linux ( жирным шрифтом мной):

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