Бенчмаркинг, переупорядочение кода, неустойчивость

Ответ 1

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

Извините, но ваш коллега ошибается.

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

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

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

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

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

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

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

Хорошей практикой является измерение времени, необходимого для выполнения функции несколько раз, и отчета min/avg/median/max/stdev/total time numbers. Высокое стандартное отклонение может указывать на то, что вышеуказанные препараты не выполняются. Первый запуск часто является самым длинным, так как кэш процессора может быть холодным, и может потребоваться много промахов в кеше и ошибок страниц, а также разрешить динамические символы из разделяемых библиотек при первом вызове (ленивое разрешение символа - это режим привязки по умолчанию для Linux, например), а последующие вызовы будут выполняться с гораздо меньшими затратами.

Ответ 2

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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);
}

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

Ответ 5

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

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

_ReadWriteBarrier() - полный забор

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

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

ICC включает полный забор __memory_barrier().

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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

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

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

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

Все ниже не mine--, и я не согласен с этим. --Carlo Дерево

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

Из этого вы получите этот асм:

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 циклов (в зависимости от того, есть ли у вашего CPU исключение mov или нет.) Версия без зависимостей переноса цикла может работать с 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, вместо того, чтобы обманывать компилятор при введении новой зависимости.

Ответ 8

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

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

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