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

Почему циклы всегда компилируются в стиле "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);

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

4b9b3361

ОТВЕТЫ

Ответ 1

Связанный: основы цикла asm: Циклы while, do while, For для языка ассемблера (emu8086)

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

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

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

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

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

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

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

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

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

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

Необходимые базовые знания для этого статического анализа производительности: Руководство по микроарху Agner Fog (см. раздел "Песчаный мост"). Также прочитайте его руководство по оптимизации сборки, это отлично. (Иногда местами устаревшие.) Смотрите также другие ссылки на производительность x86 в вики-теге x86. См. также Может ли 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.

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

Идиоматически записывая цикл для 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(){} -structured, если память не является узким местом (то есть предполагается, что попадание L1D или, по крайней мере, L2 на самом деле; это только SSE2 16 байт на такт).

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

Но важная часть заключается в том, что давление порта 5 значительно снижено: это нужно только 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 с, так что это будет узким местом цикла при 2 с на итерацию. (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/семейства бульдозеров /Ryzen: нет слияния состояния циклы, но PADDD с операндом памяти равен 1 m-op/uop.

На SnB 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, а также обычную ветвь, взятую в обратном направлении.

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

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