Могу ли я улучшить предсказание ветвлений с помощью моего кода?
Это наивный общий вопрос, открытый для любой платформы, языка или компилятора. Хотя меня больше всего интересуют Aarch64, C++, GCC.
При кодировании неизбежного перехода в потоке программы, зависящего от состояния ввода-вывода (компилятор не может предсказать), и я знаю, что одно состояние гораздо более вероятно, чем другое, как мне указать это компилятору?
Это лучше
if(true == get(gpioVal))
unlikelyFunction();
else
likelyFunction();
чем это?
if(true == get(gpioVal))
likelyFunction(); // performance critical, fill prefetch caches from this branch
else
unlikelyFunction(); // missed prediction not consequential on this branch
Помогает ли протокол связи делает более вероятное или критическое значение истинным (высоким) или ложным (низким)?
1 ответ
TL:DR: Да, в C или C++ используйте макрос или C++20, чтобы помочь компилятору улучшить ассемблер. Однако это не влияет на фактическое предсказание ветвления ЦП. Если пишете на ассемблере, выкладывайте свой код так, чтобы свести к минимуму количество веток.
Для большинства ISA в ассемблере нет способа намекнуть процессору, будет ли ветвь принята или нет. (Некоторые исключения включают Pentium 4 (но не более ранние или более поздние версии x86), PowerPC и некоторые MIPS, которые допускают подсказки ветвления как часть ассемблерных инструкций условного перехода.)
Но неиспользованный прямолинейный код дешевле, чем взятый, поэтому подсказка языка высокого уровня для размещения кода с непрерывным быстрым путем не повышает точность прогнозирования ветвлений, но может повысить (или ухудшить) производительность . (Местность I-кэша, пропускная способность внешнего интерфейса: помните, что выборка кода происходит в смежных 16- или 32-байтовых блоках, поэтому взятая ветвь означает, что более поздняя часть этого блока выборки бесполезна. Кроме того, пропускная способность предсказания ветвления ; некоторые ЦП например, Intel Skylake не может обрабатывать предсказанные переходы чаще, чем 1 раз в 2 такта, за исключением циклических переходов, включая безусловные переходы, такие как jmp или ret.)
Взятые ветки твердые; невыполненные переходы держат ЦП в напряжении, но если прогноз точен, это просто обычная инструкция для исполнительного блока (проверка прогноза), ничего особенного для внешнего интерфейса. См. также Современные микропроцессоры. 90-минутное руководство!в котором есть раздел предсказания ветвления. (И вообще отлично.)
- Что именно происходит, когда процессор Skylake неверно предсказывает ветвь?
- Избегайте остановки конвейера, вычисляя условное раннее
- Как предсказатель ветвления узнает, что он неверен?
Многие люди неправильно понимают подсказки ветвления исходного кода как подсказки предсказания ветвления . Это может быть одним из эффектов при компиляции для ЦП, который поддерживает подсказки ветвления в ассемблере, но в большинстве случаев значительный эффект заключается в компоновке и принятии решения о том, следует ли использовать безветвящиеся (
cmov) или нет; условие также означает, что оно должно хорошо предсказывать.
С некоторыми ЦП, особенно старыми, расположение ветвей иногда влияло на предсказание во время выполнения : если ЦП ничего не помнил о ветвях в своих динамических предикторах, стандартная эвристика статического предсказания состоит в том, что прямые условные ветви не выполняются, обратные условные предполагается, что они взяты (потому что обычно это нижняя часть цикла . См. Раздел BTFNT в https://danluu.com/branch-prediction/.
Компилятор может выложить
if(c) x else y;в любом случае, либо сопоставляя источник с
jump over x if !cв качестве открытия или поменять местами блоки if и else и использовать противоположное условие перехода. Или он может поместить один блок вне очереди (например, после
retв конце функции), поэтому быстрый путь не имеет принятых ветвей, условных или иных, в то время как менее вероятный путь должен перейти туда, а затем вернуться назад.
С помощью подсказок ветвления в высокоуровневом исходном коде легко причинить больше вреда, чем пользы, особенно если окружающий код меняется, не обращая на них внимания, поэтому оптимизация на основе профиля — лучший способ для компиляторов узнать о предсказуемости и вероятности ветвления. (например
gcc -O3 -fprofile-generate/ запустить с некоторыми репрезентативными входными данными, которые соответствующим образом реализуют пути кода /
gcc -O3 -fprofile-use)
Но в некоторых языках, таких как C++20 и
[[unlikely]], которые являются портативной версией GNU C
likely()/
unlikely()макросы вокруг.
- https://en.cppreference.com/w/cpp/language/attributes/вероятно С++20
- Как использовать атрибут C++20 «вероятно/маловероятно» в справке по синтаксису оператора if-else
- Есть ли подсказка компилятора для GCC, чтобы заставить предсказание ветвления всегда идти определенным путем?(на буквальный вопрос - нет. На то, что на самом деле нужно, ветвь намекает компилятору, да.)
- Как работают вероятные/невероятные макросы в ядре Linux и в чем их польза?Макросы GNU C, использующие
__builtin_expect, тот же эффект, но другой синтаксис, чем C++20[[likely]] - В чем преимущество GCC __builtin_expect в операторах if else?пример ассемблерного вывода. (Также см. ответы Чиро Сантилли на некоторые другие вопросы, где он приводил примеры.)
- Простой пример, когда [[вероятно]] и [[маловероятно]] влияют на сборку программы?
Я не знаю способов аннотировать ветки для языков, отличных от GNU C/C++ и ISO C++20.
Отсутствуют какие-либо подсказки или данные профиля
Без этого оптимизирующие компиляторы должны использовать эвристику, чтобы угадать, какая сторона ветви более вероятна. Если это ветвь цикла, они обычно предполагают, что цикл будет выполняться несколько раз. На
if, у них есть некоторые эвристики, основанные на фактическом состоянии и, возможно, на том, что находится в контролируемых блоках; IDK Я не изучал, что делают gcc или clang.
Однако я заметил, что GCC заботится об этом состоянии. Это не так наивно, как предположить, что
intзначения равномерно распределены случайным образом, хотя я думаю, что обычно предполагается, что
if (x == 10) foo();несколько маловероятно.
JIT-компиляторы, как и в JVM, имеют здесь преимущество: они потенциально могут инструментировать ветки на ранних стадиях выполнения, чтобы собирать информацию о направлении ветвления перед созданием окончательного оптимизированного ассемблера. OTOH, им нужно быстро компилировать, потому что время компиляции является частью общего времени выполнения, поэтому они не так сильно стараются сделать хороший asm, что является серьезным недостатком с точки зрения качества кода.