Подтвердить что ты не робот

Почему второй раз итерация по большому количеству байтов значительно медленнее? И как это исправить?

Этот код:

#include <memory>
#include <time.h>
#include <chrono>
#include <thread>
#include <stdio.h>
#include <stdlib.h>

void Test( ) {
#define current_milliseconds std::chrono::duration_cast<std::chrono::milliseconds>( std::chrono::system_clock::now( ).time_since_epoch( ) ).count( )
    int *c = ( int* )malloc( 1024 * 1024 * 1024 );
    int result = 0;
    auto millis = -current_milliseconds;
    //clock_t timer = -clock( );
    for ( int i = 0 ; i < 1024 * 1024 * 256 /* 1024 / 4 */; ++i )
        result += c[ i ];
    millis += current_milliseconds;
    printf( "Took: %ldms (JUST PASSING BY: %d)\n", millis, result );
    free( c );
#undef current_milliseconds
}

int main( ) {
    std::this_thread::sleep_for( std::chrono::milliseconds( 1 ) );
    Test( );
    std::this_thread::sleep_for( std::chrono::milliseconds( 1 ) );
    Test( );
    return -1;
}

Я провел 7 тестов и дал последние 6 выходов:

Took: 502ms (JUST PASSING BY: 0)
Took: 607ms (JUST PASSING BY: 0)

Took: 480ms (JUST PASSING BY: 0)
Took: 588ms (JUST PASSING BY: 0)

Took: 492ms (JUST PASSING BY: 0)
Took: 562ms (JUST PASSING BY: 0)

Took: 506ms (JUST PASSING BY: 0)
Took: 558ms (JUST PASSING BY: 0)

Took: 470ms (JUST PASSING BY: 0)
Took: 555ms (JUST PASSING BY: 0)

Took: 510ms (JUST PASSING BY: 0)
Took: 562ms (JUST PASSING BY: 0)

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

Обратите внимание, что диапазон кода таймера находится только в цикле, а не в распределении; то снова возникает вопрос: почему вторая итерация медленнее? Есть ли способ исправить это?

Дополнительная информация:

  • У этого ПК есть процессор Pentium 2.8GHZ @2 ядра (Intel E6300), 4 ГБ оперативной памяти (с оперативной памятью 2,2 ГБ до выполнения тестов) и корпоративный Intel SSD.
  • Кажется, что при выполнении тестов он написал несколько из 100 МБ. Почему это произошло, когда у него было достаточно свободной памяти? (Я освободил 1 ГБ, а затем выделил еще 1 ГБ, он не должен пропускать pre-swapfile).
4b9b3361

Ответ 1

Выход на моей машине:

Взял: 371 мс (ПРОСТО ОТПУСКА: 0)
Взято: 318 мс (ПРОСТО ПРОШЛОГО: 0)

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

int *c = (int*)malloc(1024 * 1024 * 1024);
memset(c, 0, 1024 * 1024 * 1024);          // <== added
// etc..

Что производит на моей машине:

Взято: 104 мс (ТОЛЬКО ПРОХОДА: 0)
Взято: 102 мс (ПРОСТО ПРОШЛОГО: 0)

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

Это поведение оперативной системы виртуальной памяти с запросами по требованию. Как Windows, Linux или OSX. Ваш вызов malloc() никогда не выделял какую-либо память, а просто зарезервировал адресное пространство. Просто номера процессора, по одному на каждые 4096 байт памяти. Вы не оплачиваете стоимость использования памяти до тех пор, пока вы ее не решите. Когда функция воспроизведения с запросом вступает в игру.

Что происходит в вашем выражении result += c[ i ];. В этот момент педаль должна соответствовать металлу, и операционная система вынуждена фактически сделать память доступной. Каждые 4096 байт ваша программа создает ошибку страницы. Операционная система запускает и отображает 4096 байт ОЗУ на страницу виртуальной памяти. Ваша программа генерирует 1 ГБ /4096 = 262,144 этих ошибок страницы. Вы можете сделать вывод, что для работы с ошибкой вашей операционной системы требуется примерно 400 мс /262144 ~ = 1,5 микросекунды. Шахта в два раза быстрее.

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

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

Как долго второй запуск будет зависеть от того, насколько операционная система сможет перерабатывать страницы RAM, если их недостаточно, чтобы сопоставить другой гигабайт. Не так много проблем на моем, у меня 8 ГБ ОЗУ и сейчас используется только 5,6. Они должны быть инициализированы с нулевым уровнем, с низким приоритетом для обычной ОС.

Итак, основной вывод здесь:

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

Ответ 2

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

Попробуйте отключить масштабирование частоты процессора при запуске тестов. В Windows это можно сделать, установив профиль производительности в Power Management на панели управления, который блокирует частоту процессора на самом высоком уровне.


Проверим эту гипотезу.

Вот мои результаты вашего теста на Linux с помощью регулятора powersave по умолчанию, они похожи на ваши по отношению к высокой временной дисперсии:

[[email protected]:~/src/test] $ cpupower frequency-info
analyzing CPU 0:
  driver: intel_pstate
  CPUs which run at the same hardware frequency: 0
  CPUs which need to have their frequency coordinated by software: 0
  maximum transition latency: 0.97 ms.
  hardware limits: 1.20 GHz - 5.70 GHz
  available cpufreq governors: performance, powersave
  current policy: frequency should be within 1.20 GHz and 5.70 GHz.
                  The governor "powersave" may decide which speed to use
                  within this range.
  current CPU frequency is 1.26 GHz.
  boost state support:
    Supported: yes
    Active: yes
    25500 MHz max turbo 4 active cores
    25500 MHz max turbo 3 active cores
    25500 MHz max turbo 2 active cores
    25500 MHz max turbo 1 active cores

[[email protected]:~/src/test] $ for ((i=0; i<10; ++i)); do ./test; echo; done
Took: 698ms (JUST PASSING BY: 0)
Took: 598ms (JUST PASSING BY: 0)

Took: 541ms (JUST PASSING BY: 0)
Took: 570ms (JUST PASSING BY: 0)

Took: 660ms (JUST PASSING BY: 0)
Took: 656ms (JUST PASSING BY: 0)

Took: 673ms (JUST PASSING BY: 0)
Took: 616ms (JUST PASSING BY: 0)

Took: 637ms (JUST PASSING BY: 0)
Took: 650ms (JUST PASSING BY: 0)

Took: 690ms (JUST PASSING BY: 0)
Took: 667ms (JUST PASSING BY: 0)

Took: 671ms (JUST PASSING BY: 0)
Took: 603ms (JUST PASSING BY: 0)

Took: 537ms (JUST PASSING BY: 0)
Took: 544ms (JUST PASSING BY: 0)

Took: 535ms (JUST PASSING BY: 0)
Took: 629ms (JUST PASSING BY: 0)

Took: 660ms (JUST PASSING BY: 0)
Took: 656ms (JUST PASSING BY: 0)

И вот результат с менеджером performance, обратите внимание на то, что на этот раз небольшая дисперсия есть:

[[email protected]:~/src/test] $ sudo cpupower frequency-set --related --governor performance
Setting cpu: 0
Setting cpu: 1
Setting cpu: 2
Setting cpu: 3
Setting cpu: 4
Setting cpu: 5
Setting cpu: 6
Setting cpu: 7

[[email protected]:~/src/test] $ cpupower frequency-info
analyzing CPU 0:
  driver: intel_pstate
  CPUs which run at the same hardware frequency: 0
  CPUs which need to have their frequency coordinated by software: 0
  maximum transition latency: 0.97 ms.
  hardware limits: 1.20 GHz - 5.70 GHz
  available cpufreq governors: performance, powersave
  current policy: frequency should be within 1.20 GHz and 5.70 GHz.
                  The governor "performance" may decide which speed to use
                  within this range.
  current CPU frequency is 4.34 GHz.
  boost state support:
    Supported: yes
    Active: yes
    25500 MHz max turbo 4 active cores
    25500 MHz max turbo 3 active cores
    25500 MHz max turbo 2 active cores
    25500 MHz max turbo 1 active cores

[[email protected]:~/src/test] $ for ((i=0; i<10; ++i)); do ./test; echo; done
Took: 539ms (JUST PASSING BY: 0)
Took: 548ms (JUST PASSING BY: 0)

Took: 543ms (JUST PASSING BY: 0)
Took: 547ms (JUST PASSING BY: 0)

Took: 542ms (JUST PASSING BY: 0)
Took: 543ms (JUST PASSING BY: 0)

Took: 548ms (JUST PASSING BY: 0)
Took: 539ms (JUST PASSING BY: 0)

Took: 538ms (JUST PASSING BY: 0)
Took: 536ms (JUST PASSING BY: 0)

Took: 536ms (JUST PASSING BY: 0)
Took: 536ms (JUST PASSING BY: 0)

Took: 546ms (JUST PASSING BY: 0)
Took: 547ms (JUST PASSING BY: 0)

Took: 559ms (JUST PASSING BY: 0)
Took: 534ms (JUST PASSING BY: 0)

Took: 537ms (JUST PASSING BY: 0)
Took: 540ms (JUST PASSING BY: 0)

Took: 538ms (JUST PASSING BY: 0)
Took: 534ms (JUST PASSING BY: 0)

Это показывает, что для выполнения обоих циклов требуется одно и то же время, но цикл не работает.

Ответ 3

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

Если ваша ОС отображает вновь выделенное хранилище на страницу с нулями и отображает новоназначенную память на свою собственную страницу при доступе, а не на записи, и не отображает распределение гигабайта на большие 2M-страницы, тогда второй круг через ваш гигабайт, вы будете TLB, потеряв почти каждый 4K. Это может... не дешево.

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

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

Ответ 4

(переписать после комментария)

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

Это решение уже обсуждалось в комментарии. LyingOnTheSky подтвердил, что добавление сна за 3 секунды разрешило тайну: Первый и второй тесты имели ровно то же время (421 мс) для выполнения.

Ответ 5

Took: 682ms (JUST PASSING BY: 0)
Took: 666ms (JUST PASSING BY: 0)

Took: 686ms (JUST PASSING BY: 0)
Took: 680ms (JUST PASSING BY: 0)

Took: 674ms (JUST PASSING BY: 0)
Took: 675ms (JUST PASSING BY: 0)

Took: 694ms (JUST PASSING BY: 0)
Took: 684ms (JUST PASSING BY: 0)

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

 __builtin_prefetch

https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Ответ 6

как уже объяснялось другими людьми, в основном вы испытываете своего рода смещение (стоимость инициализации + OS + другие зависимые от оборудования операции, которые вы не можете контролировать).

Все результаты зависят от рабочей станции (CPU + RAM + OS). Например, мои результаты всегда близки к 1-му и 2-му прогонам (проверены с оптимизацией и без нее, см. Ниже).

Просто любопытство. Вместо вызова Test() всего 2 раза попробуйте назвать его 10 или 15 в коде. Вы должны начать видеть более близкие результаты.

Как последнее, я не знаю, пытаетесь ли вы оценить производительность вашего кода, глядя на время исполнения. Если да, попробуйте использовать более эффективные инструменты, такие как valgrind или gprof. С помощью valgrind вы можете использовать callgrind для получения оценки количества выполненных команд и производительности оборудования (возможны варианты прохода для имитации отсутствия кэша, прогнозирования ветвей, < мощный > предварительный набор аппаратных средств, ecc.):

 valgrind --tool=callgrind --cache-sim=yes --branch-sim=yes YOUR_PROGRAM

Выполнено на Apple MB Pro в конце 2014 года:

Took: 914ms (JUST PASSING BY: 0)
Took: 911ms (JUST PASSING BY: 0)

Took: 917ms (JUST PASSING BY: 0)
Took: 913ms (JUST PASSING BY: 0)
Took: 910ms (JUST PASSING BY: 0)
Took: 916ms (JUST PASSING BY: 0)
Took: 914ms (JUST PASSING BY: 0)
Took: 907ms (JUST PASSING BY: 0)

Took: 387ms (JUST PASSING BY: 0)
Took: 387ms (JUST PASSING BY: 0)

Took: 380ms (JUST PASSING BY: 0)
Took: 387ms (JUST PASSING BY: 0)

Took: 384ms (JUST PASSING BY: 0)
Took: 382ms (JUST PASSING BY: 0)

Took: 380ms (JUST PASSING BY: 0)
Took: 381ms (JUST PASSING BY: 0)