Почему циклы всегда компилируются в стиле "do...while" (прыжок с хвоста)?

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

Очень простой цикл, как это

outside_loop;
while (condition) {
     statements;
}

Часто компилируется в (псевдокод)

    ; outside_loop
    jmp loop_condition    ; unconditional
loop_start:
    loop_statements
loop_condition:
    condition_check
    jmp_if_true loop_start
    ; outside_loop

Однако, если оптимизация не включена, она компилируется в обычно понятный код:

loop_condition:
    condition_check
    jmp_if_false loop_end
    loop_statements
    jmp loop_condition  ; unconditional
loop_end:

Насколько я понимаю, скомпилированный код лучше напоминает это:

goto condition;
do {
    statements;
    condition:
}
while (condition_check);

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

Источник

1 ответ

Решение

Меньше инструкций / мопов внутри цикла = лучше. Структурирование кода вне цикла для достижения этой цели очень часто является хорошей идеей, будь то ветки, чтобы обеспечить лучшую структуру цикла, или частичное очищение первой итерации, чтобы вы могли попасть в цикл в удобной точке и, возможно, сохранить mov инструкция или что-то еще внутри (не уверен, есть ли название для этого; "конвейерная передача программного обеспечения" является чем-то конкретным).

do{}while() является канонической / идиоматической структурой для циклов в asm на всех архитектурах, привыкните к ней. IDK, если есть имя для него; Я бы сказал, что у такого цикла есть структура do while. Если вы хотите имена, вы можете позвонить while() структура "дерьмовый неоптимизированный код" или "написанный новичком".:P Петлевая ветвь внизу универсальна, и даже не стоит упоминать ее как Loop Optimization. Ты всегда так делаешь.

Этот шаблон настолько широко используется, что на процессорах, которые используют статическое предсказание ветвлений для ветвей без записи в кэшах предикторов ветвлений, неизвестные прямые условные ветвления предсказываются не взятыми, неизвестные обратные ветвления предсказываются взятыми (потому что они, вероятно, являются ветвями цикла). См. Статический прогноз ветвления на новых процессорах Intel в блоге Мэтта Годболта и главу Агнера Фога по прогнозированию ветвлений в начале его микроархива в формате PDF.

Этот ответ в конечном итоге использовал примеры x86 для всего, но большая часть этого применима ко всем системам для всех архитектур. Я не удивлюсь, если другие суперскалярные / неупорядоченные реализации (например, ARM или POWER) также имеют ограниченную пропускную способность инструкций ветвления, независимо от того, взяты они или нет. Но меньшее количество инструкций внутри цикла почти универсально, когда все, что у вас есть, это условная ветвь внизу и безусловная ветвь.

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

Кстати, эта статья называет преобразование while() в if(){ do{}while; } "инверсия", но инверсия цикла обычно означает инвертирование вложенного цикла. (например, если исходный цикл перебирает многомерный массив со строкой в ​​неправильном порядке, умный компилятор может измениться for(i) for(j) a[j][i]++; в for(j) for(i) a[j][i]++; если это может доказать, что это правильно.) Но я думаю, вы можете посмотреть на if() как ноль или один итерационный цикл. Интересный факт, что разработчики компиляторов учат своих компиляторов, как инвертировать цикл (чтобы разрешить автоматическую векторизацию) для (очень) конкретного случая, поэтому тест libECantum в SPECint2006 "сломан". Большинство компиляторов не могут инвертировать циклы в общем случае, только те, которые выглядят почти так же, как в SPECint2006...

Вы можете помочь компилятору сделать более компактный ASM (меньше инструкций вне цикла), написав do{}while() циклы в C, когда вы знаете, что вызывающему не разрешено проходить size=0 или что-то еще гарантирует, что цикл запускается хотя бы один раз.

(Фактически 0 или отрицательно для границ цикла со знаком. Счетчики цикла со знаком и без знака - сложная задача оптимизации, особенно если вы выбираете более узкий тип, чем указатели; проверьте вывод asm вашего компилятора, чтобы убедиться, что он не расширяет знак узкого цикла Счетчик внутри цикла очень долго, если вы используете его как индекс массива. Но обратите внимание, что подпись может быть полезна, потому что компилятор может предположить, что i++ <= bound в конечном итоге станет ложным, потому что переполнение со знаком - UB, а без знака - нет. Так что с неподписанным, while(i++ <= bound) бесконечен, если bound = UINT_MAX.) У меня нет общей рекомендации о том, когда использовать подписанный или неподписанный; size_t Тем не менее, часто является хорошим выбором для циклического перемещения по массивам, но если вы хотите избежать префиксов REX x86-64 в служебных данных цикла (для тривиального сохранения размера кода), но убедите компилятор не тратить никакие инструкции на ноль или знак. Продолжая, это может быть сложно.

Я не вижу огромного прироста производительности

Вот пример, где эта оптимизация даст ускорение в 2 раза на процессорах Intel до Haswell, потому что P6 и SnB/IvB могут запускать только ветви на порту 5, включая неиспользуемые условные ветви.

Необходимые базовые знания для этого статического анализа производительности: руководство по микроархам Agner Fog (см. Раздел "Sandybridge"). Также прочитайте его руководство по оптимизации сборки, это отлично. (Иногда местами устаревшие, хотя.) Смотрите также другие ссылки на производительность x86 в вики тега x86. Смотрите также Может ли MOV x86 действительно быть "свободным"? Почему я не могу воспроизвести это вообще? для некоторого статического анализа, подкрепленного экспериментами со счетчиками перфектов, и некоторого объяснения мопсов слитых и не слитых доменов.

Вы также можете использовать программное обеспечение Intel IACA (анализатор архитектуры Intel) для статического анализа этих циклов.

; sum(int []) using SSE2 PADDD (dword elements)
; edi = pointer,  esi = end_pointer.
; scalar cleanup / unaligned handling / horizontal sum of XMM0 not shown.

; NASM syntax
ALIGN 16          ; not required for max performance for tiny loops on most CPUs
.looptop:                 ; while (edi<end_pointer) {
    cmp     edi, esi    ; 32-bit code so this can macro-fuse on Core2
    jae    .done            ; 1 uop, port5 only  (macro-fused with cmp)
    paddd   xmm0, [edi]     ; 1 micro-fused uop, p1/p5 + a load port
    add     edi, 16         ; 1 uop, p015
    jmp    .looptop         ; 1 uop, p5 only

                            ; Sandybridge/Ivybridge ports each uop can use
.done:                    ; }

Это всего 4 мопа слитых доменов ( с макро-слиянием cmp/jae), так что он может выдавать из внешнего интерфейса в ядро ​​не по порядку за одну итерацию за такт. Но в незанятом домене есть 4 ALU мопов, а в Intel pre-Haswell есть только 3 порта ALU.

Что еще более важно, давление порта 5 является узким местом: этот цикл может выполняться только за одну итерацию за 2 цикла, потому что cmp/jae и jmp оба должны работать на порту 5. Другие порты для кражи мопов могут снизить практическую пропускную способность несколько ниже.

Записывая цикл идиоматически для asm, мы получаем:

ALIGN 16
.looptop:                 ; do {
    paddd   xmm0, [edi]     ; 1 micro-fused uop, p1/p5 + a load port
    add     edi, 16         ; 1 uop, p015

    cmp     edi, esi        ; 1 uop, port5 only  (macro-fused with cmp)
    jb    .looptop        ; } while(edi < end_pointer);

Заметьте сразу, независимо от всего остального, что это одна инструкция в цикле. Эта структура цикла, по крайней мере, немного лучше всего: от простого не конвейерного 8086 до классического RISC (например, раннего MIPS), особенно для длительных циклов (при условии, что они не являются узким местом в пропускной способности памяти).

Core2 и более поздние должны запускать это с одной итерацией за такт, в два раза быстрее, чем while(){} -структурированный цикл, если память не является узким местом (т. е. предполагается, что попадание L1D или, по крайней мере, L2 на самом деле; это только SSE2 16 байтов за такт).

Это всего 3 мопа в слитых доменах, так что можно выпускать со скоростью не более одного за такт на любом устройстве, начиная с Core2, или только один за такт, если группы выпуска всегда заканчиваются взятой ветвью.

Но важная часть заключается в том, что давление в port5 значительно снижено: только cmp/jb нужно это Другие мопы, вероятно, будут запланированы на перенос 5 времени и циклов кражи с пропускной способностью ветвления петли, но это будет несколько% вместо коэффициента 2. См. Как точно запланированы мопы x86?,

Большинство процессоров, которые обычно имеют пропускную способность по одному на 2 цикла, все еще могут выполнять крошечные циклы по 1 на такт. Однако есть некоторые исключения. (Я забываю, какие процессоры не могут выполнять узкие циклы по 1 в такт; может быть, семейство Bulldozer? Или, может быть, просто некоторые маломощные процессоры, такие как VIA Nano.) Sandybridge и Core2 определенно могут запускать узкие циклы по одному в такт. У них даже есть буферы петли; Core2 имеет буфер цикла после декодирования длины команды, но до обычного декодирования. Nehalem и более поздние версии перерабатывают мопы в очереди, которая передает этап выпуска / переименования. (За исключением Skylake с обновлениями микрокода; Intel пришлось отключить буфер цикла из-за ошибки слияния с частичным регистром.)

Тем не менее, существует цепочка зависимостей xmm0: Процессоры Intel имеют задержку в 1 цикл paddd так что мы тоже против этого узкого места. add esi, 16 также задержка 1 цикла. В семействе Bulldozer даже целочисленные векторные операции имеют задержку 2 c, так что в цикле 2 c будет повторяться. (AMD, начиная с K8, и Intel, поскольку SnB может запускать две нагрузки за такт, поэтому нам все равно нужно развернуться для максимальной пропускной способности.) С плавающей запятой вам определенно нужно развернуть с несколькими аккумуляторами. Почему Мулсс занимает всего 3 цикла в Haswell, в отличие от таблиц инструкций Агнера?,

Если бы я использовал режим индексированной адресации, как paddd xmm0, [edi + eax] Я мог бы использовать sub eax, 16 / jnc в состоянии цикла. SUB/JNC может макро-предохранитель на семействе Sandybridge, но индексированная нагрузка не будет ламинировать на SnB/IvB (но останется слитой на Haswell и позже, если вы не используете форму AVX).

    ; index relative to the end of the array, with an index counting up towards zero
    add   rdi, rsi          ; edi = end_pointer
    xor   eax, eax
    sub   eax, esi          ; eax = -length, so [rdi+rax] = first element

 .looptop:                  ; do {
    paddd   xmm0, [rdi + rax]
    add     eax, 16
    jl    .looptop          ; } while(idx+=16 < 0);  // or JNC still works

(Обычно лучше развернуть некоторые из них, чтобы скрыть издержки приращения указателя, вместо использования индексированных режимов адресации, особенно для хранилищ, отчасти потому, что индексированные хранилища не могут использовать AGU хранилища port7 на Haswell+.)

На Core2/Nehalem add/jl не используйте макрос-слияние, так что это 3 мопа слитых доменов даже в 64-битном режиме, без зависимости от макроплавления. То же самое для AMD K8/K10/ семейства Bulldozer /Ryzen: нет слияния состояния петли, но PADDD с операндом памяти равен 1 m-op / uop.

На СнБ, paddd не ламинирует от нагрузки, но добавляет /jl macro-fuse, так что опять 3 мопа слитых доменов. (Но в неиспользованном домене только 2 ALU uops + 1 загрузка, поэтому, вероятно, меньше конфликтов ресурсов, уменьшающих пропускную способность цикла.)

В HSW и более поздних версиях это 2 мопа слитых доменов, поскольку индексированная нагрузка может оставаться микрослитой с PADDD, и add/jl макро-предохранители. (Полученные по прогнозу ветки выполняются на порту 6, поэтому никогда не возникает конфликтов ресурсов.)

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

Но все эти петли не были развернуты

Да, это преувеличивает эффект накладных расходов цикла. Но gcc по умолчанию не разворачивается даже при -O3 (если только он не решит полностью развернуть). Он разворачивается только с оптимизацией по профилю, чтобы узнать, какие циклы горячие. (-fprofile-use). Вы можете включить -funroll-all-loops, но я бы порекомендовал делать это только для каждого файла для модуля компиляции, который, как вы знаете, имеет один из ваших горячих циклов, который нуждается в этом. Или, может быть, даже для каждой функции с __attribute__, если есть один для вариантов оптимизации, как это.

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

Преимущества с очень низким количеством итераций:

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

  • За do{}while Выполнение - это прямая линия без взятых ветвей и одной не взятой ветви внизу. Это отлично.

  • Для if() { do{}while; } это может запустить цикл ноль раз, это две неиспользованные ветви. Это все еще очень хорошо. (Не взятые немного дешевле для внешнего интерфейса, чем взятые, когда оба правильно предсказаны).

  • Для jmp-to-the-bottom jmp; do{}while(), это одна взятая безусловная ветвь, одна взятая условие цикла, а затем ветвь цикла не берется. Это немного неуклюже, но современные предсказатели отрасли очень хороши...

  • Для while(){} структура, это один не взятый цикл выхода, один взятый jmp внизу, затем одна взятая петля-выходная ветвь вверху.

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

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

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

Условно перепрыгивая через do{}while Цикл избегает всего этого: вы переходите только к тому коду, который еще не был запущен в тех случаях, когда код, по которому вы перепрыгиваете, вообще не должен запускаться. Он часто очень хорошо предсказывает, потому что большая часть кода никогда не выполняет 0 циклов. (то есть это могло быть do{}while компилятору просто не удалось это доказать.)

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

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

Петли с несколькими условиями выхода:

Рассмотрим memchr петля или strchr цикл: они должны останавливаться в конце буфера (на основе счетчика) или в конце строки неявной длины (0 байт). Но они также должны break из цикла, если они находят совпадение до конца.

Таким образом, вы часто будете видеть такую ​​структуру, как

do {
    if () break;

    blah blah;
} while(condition);

Или только два условия в нижней части. В идеале вы можете проверить несколько логических условий с помощью одной и той же действующей инструкции (например, 5 < x && x < 25 с помощью sub eax, 5 / cmp eax, 20 / ja .outside_range, беззнаковый трюк сравнения для проверки диапазона, или объедините это с OR проверить алфавитные символы в любом из случаев в 4 инструкциях), но иногда вы не можете и просто должны использовать if()break стиль loop-exit branch и обычная ветвь, взятая в обратном направлении.

Дальнейшее чтение:

Вроде не по теме:

Источник
Другие вопросы по тегам