бенчмаркинг, изменение порядка кода, volatile

Коллега указал, что я должен объявить переменные start и stop как volatile, чтобы избежать переупорядочения кода.

Извините, но ваш коллега не прав.

Компилятор не переупорядочивает вызовы функций, определения которых недоступны во время компиляции. Просто представьте себе веселье, которое возникло бы, если бы компилятор переупорядочил такие вызовы, как fork и exec, или переместил код вокруг них.

Другими словами, любая функция без определения является барьером памяти во время компиляции, то есть компилятор не перемещает последующие операторы перед вызовом или предыдущие операторы после вызова.

В вашем коде вызовы std::clock заканчиваются вызовом функции, определение которой недоступно.

Я не могу рекомендовать достаточно просмотра atomic Weapons: The C++ Memory Model and Modern Hardware, потому что в нем обсуждаются неверные представления о барьерах памяти (во время компиляции) и volatile среди многих других полезных вещей.

Тем не менее, я добавил volatile и обнаружил, что тест не только занимает значительно больше времени, но и крайне непостоянен от запуска к запуску. Без volatile (и если вам повезло убедиться, что код не был переупорядочен), эталонный тест постоянно занимал 600-700 мс. С volatile это часто занимало 1200 мс, а иногда и более 5000 мс.

Не уверен, что здесь виноват volatile.

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

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

Обычный способ предотвратить переупорядочение - это барьер компиляции, т.е. asm volatile ("":::"memory"); (с gcc). Это ассемблерная инструкция, которая ничего не делает, но мы сообщаем компилятору, что она будет засорять память, поэтому не разрешается переупорядочивать код в ней. Стоимость этого - это только фактическая стоимость удаления повторного заказа, что, очевидно, не относится к изменению уровня оптимизации и т. Д., Как предлагается в другом месте.

Я считаю, что _ReadWriteBarrier эквивалентен материалам Microsoft.

Однако, согласно ответу Максима Егорушкина, изменение порядка вряд ли будет причиной ваших проблем.

Связанная проблема: как запретить компилятору поднимать небольшое повторяющееся вычисление из цикла

Я нигде не мог найти это, поэтому добавил свой собственный ответ через 11 лет после того, как вопрос был задан;).

Использование volatile для переменных - это не то, что вам нужно для этого. Это заставит компилятор загружать и сохранять эту переменную из ОЗУ и в ОЗУ каждый раз (при условии, что есть побочный эффект того, что необходимо сохранить: иначе - хорошо для регистров ввода-вывода). Когда вы проводите бенчмаркинг, вас не интересует измерение того, сколько времени требуется, чтобы получить что-то из памяти или записать это туда. Часто вы просто хотите, чтобы ваша переменная находилась в регистрах процессора.

volatile можно использовать, если вы назначаете ему один раз вне цикла, который не оптимизируется (например, суммирование массива), в качестве альтернативы печати результата. (Как и долговременная функция в вопросе). Но не внутри крошечной петли; это представит инструкции сохранения/перезагрузки и задержку переадресации хранилища.

Я думаю, что ЕДИНСТВЕННЫЙ способ заставить ваш компилятор не оптимизировать код теста — это использовать asm. Это позволяет вам обмануть компилятор, заставив его думать, что он ничего не знает о содержимом или использовании ваших переменных, поэтому он должен делать все каждый раз, так часто, как ваш цикл просит его об этом.

Например, если бы я хотел сравнить m & -m, где m — это некоторое uint64_t, я мог бы попробовать:

uint64_t const m = 0x0000080e70100000UL;
for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
}

Компилятор, очевидно, сказал бы: я даже не буду вычислять это; так как вы не используете результат. Ака, на самом деле это было бы так:

for (int i = 0; i < loopsize; ++i)
{
}

Тогда вы можете попробовать:

uint64_t const m = 0x0000080e70100000UL;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = m & -m;
}

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

uint64_t const m = 0x0000080e70100000UL;
uint64_t tmp = m & -m;
static uint64_t volatile result;
for (int i = 0; i < loopsize; ++i)
{
  result = tmp;
}

Тратить много времени на запись в адрес памяти result loopsize раз, как вы и просили.

Наконец, вы также можете сделать m volatile, но в ассемблере результат будет выглядеть так:

507b:   ba e8 03 00 00          mov    $0x3e8,%edx
  # top of loop
5080:   48 8b 05 89 ef 20 00    mov    0x20ef89(%rip),%rax        # 214010 <m_test>
5087:   48 8b 0d 82 ef 20 00    mov    0x20ef82(%rip),%rcx        # 214010 <m_test>
508e:   48 f7 d8                neg    %rax
5091:   48 21 c8                and    %rcx,%rax
5094:   48 89 44 24 28          mov    %rax,0x28(%rsp)
5099:   83 ea 01                sub    $0x1,%edx
509c:   75 e2                   jne    5080 <main+0x120>

Дважды чтение из памяти и один раз запись в нее, помимо запрошенного расчета с регистрами.

Поэтому правильный способ сделать это:

for (int i = 0; i < loopsize; ++i)
{
  uint64_t result = m & -m;
  asm volatile ("" : "+r" (m) : "r" (result));
}

результаты которого в коде сборки (из gcc8.2 в обозревателе компиляторов Godbolt):

 # gcc8.2 -O3 -fverbose-asm
    movabsq $8858102661120, %rax      #, m
    movl    $1000, %ecx     #, ivtmp_9     # induction variable tmp_9
.L2:
    mov     %rax, %rdx      # m, tmp91
    neg     %rdx            # tmp91
    and     %rax, %rdx      # m, result
       # asm statement here,  m=%rax   result=%rdx
    subl    $1, %ecx        #, ivtmp_9
    jne     .L2
    ret     

Выполнение ровно трех запрошенных ассемблерных инструкций внутри цикла, плюс sub и jne для накладных расходов цикла.

Хитрость здесь в том, что используя asm volatile¹ и сообщая компилятору

1. Входной операнд "r": он использует значение result в качестве входных данных, поэтому компилятор должен материализовать его в регистре.
2. "+r" операнд ввода/вывода: m остается в том же регистре, но (потенциально) изменяется.
3. volatile: имеет какой-то таинственный побочный эффект и/или не является чистой функцией входных данных; компилятор должен выполнить его столько же раз, сколько и исходный код. Это заставляет компилятор оставить ваш тестовый фрагмент в покое и внутри цикла. См. раздел руководства gcc по расширенному Asm#Volatile.

сноска 1: здесь требуется volatile, иначе компилятор превратит это в пустой цикл. Энергонезависимый asm (с любыми выходными операндами) считается чистой функцией своих входов, которую можно оптимизировать, если результат не используется. Или CSEd для запуска только один раз, если используется несколько раз с одним и тем же вводом.

Все, что ниже, не мое, и я не обязательно с этим согласен. --Карло Вуд

Если бы вы использовали asm volatile ("" : "=r" (m) : "r" (result)); (с выходом "=r" только для записи), компилятор мог бы выбрать один и тот же регистр для m и result, создав циклическую цепочку зависимостей, которая проверяет задержку, а не пропускную способность расчет.

Из этого вы получите этот asm:

5077:   ba e8 03 00 00          mov    $0x3e8,%edx
507c:   0f 1f 40 00             nopl   0x0(%rax)    # alignment padding
  # top of loop
5080:   48 89 e8                mov    %rbp,%rax    # copy m
5083:   48 f7 d8                neg    %rax         # -m
5086:   48 21 c5                and    %rax,%rbp    # m &= -m   instead of using the tmp as the destination.
5089:   83 ea 01                sub    $0x1,%edx
508c:   75 f2                   jne    5080 <main+0x120>

Это будет выполняться с частотой 1 итерация за 2 или 3 цикла (в зависимости от того, есть ли у вашего ЦП устранение перемещений или нет). Версия без циклической зависимости может выполняться с частотой 1 итерация за такт на Haswell и более поздних версиях, а также на Ryzen. Эти процессоры имеют пропускную способность ALU для выполнения не менее 4 операций за такт.

Этот ассемблер соответствует C++, который выглядит так:

for (int i = 0; i < loopsize; ++i)
{
  m = m & -m;
}

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

Вы можете захотеть провести микротестирование задержки, чтобы было легче определить преимущества компиляции с -mbmi или -march=haswell, чтобы позволить компилятору использовать blsi %rax, %rax и вычислить m &= -m; в одной инструкции. Но легче отслеживать, что вы делаете, если исходный код C++ имеет ту же зависимость, что и asm, вместо того, чтобы обманывать компилятор, вводя новую зависимость.

Вы можете создать два файла C: SlowCalculation, скомпилированный с g++ -O3 (высокий уровень оптимизации), и тестовый, скомпилированный с g++ -O1 (более низкий уровень, все еще оптимизированный - этого может быть достаточно для этой части бенчмаркинга).

Согласно справочной странице, изменение порядка кода происходит на уровнях оптимизации -O2 и -O3.

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

Предполагая, что вы используете g++, но в другом компиляторе должно быть что-то эквивалентное.

Правильный способ сделать это в C++ — использовать класс, например. что-то типа

class Timer
{
    std::clock_t startTime;
    std::clock_t* targetTime;

public:
    Timer(std::clock_t* target) : targetTime(target) { startTime = std::clock(); }
    ~Timer() { *target = std::clock() - startTime; }
};

и используйте его так:

std::clock_t slowTime;
{
    Timer timer(&slowTime);
    int answer = SlowCalculation(42);
}

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

Volatile гарантирует одно и только одно: чтение из volatile переменной будет считываться из памяти каждый раз — компилятор не будет предполагать, что значение может быть кэшировано в регистре. Точно так же записи будут записываться в память. Компилятор не будет хранить его в регистре «некоторое время, прежде чем записать его в память».

Чтобы предотвратить переупорядочивание компилятора, вы можете использовать так называемые заборы компилятора. MSVC включает в себя 3 ограждения компилятора:

_ReadWriteBarrier() - полное ограждение

_ReadBarrier() - двустороннее ограждение для грузов

_WriteBarrier() - двухсторонний забор для магазинов

ICC включает полное ограждение __memory_barrier().

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

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

Предложит прочитать http://preshing.com/20120625/memory-ordering-at-compile-time, чтобы увидеть потенциальные проблемы, с которыми мы можем столкнуться при переупорядочивании компилятора и т. д.

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

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

Другая возможность состоит в том, чтобы сделать функцию SlowCalculation(42); функцией extern (определить эту функцию в отдельном файле .c/.cpp и связать файл с вашей основной программой) и объявить start и stop глобальными переменными. Я не знаю, какие оптимизации предлагает оптимизатор времени компоновки/межпроцедурный вашего компилятора.

Кроме того, если вы компилируете в O1 или O0, компилятор, скорее всего, не будет переупорядочивать инструкции. Ваш вопрос несколько связан с (временными барьерами компиляции - переупорядочением кода компилятора - gcc и pthreads)

Переупорядочивание, описанное вашим коллегой, просто ломает 1.9/13

Последовательность перед представляет собой асимметричное, транзитивное, попарное отношение между оценками, выполняемыми одним потоком (1.10), что приводит к частичному порядку среди этих оценок. При любых двух оценках A и B, если A упорядочивается до B, то выполнение A должно предшествовать выполнению B. Если A не упорядочивается до B, а B не упорядочивается до A, то A и B не упорядочиваются. [Примечание: выполнение непоследовательных оценок может перекрываться. —конец примечания] Оценки A и B расположены в неопределенной последовательности, когда либо A упорядочивается до B, либо B упорядочивается до A, но не указано, что именно. [Примечание: неопределенная последовательность оценок не может перекрываться, но любая из них может выполняться первой. -конец примечания]

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