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

[Refridgerator]

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

[Gordon01]

stackoverflow.com/questions/30130930/is-there-a-compiler-hint-for-gcc-to-force-branch-prediction-to-always-go-a-certa

[masai]

В C++20 атрибуты [[likely]] и [[unlikely]] — это часть языка. https://en.cppreference.com/w/cpp/language/attributes/likely

[Fenzales]

Ни эти атрибуты, ни __builtin_expect() не касаются предсказания ветвлений на уровне процессора, это оптимизация только на уровне компилятора, меняющая порядок инструкций.

[Mingun]

И как предсказатель узнает, что ему нужно что-то предсказывать, если он не знает, что перед ним команда ветвления? Адреса для перехода тоже ведь частью команды являются, разве нет?

[tbl]

При branch prediction есть фаза вычисления фактического адреса для прыжка, поэтому рекомендуют использовать addressing modes для операндов вместо вычисления адреса с помощью арифметических операций (включая LEA), тогда затраты на эту фазу будут околонулевые (относительно трат тактов на микрооперации). А сами операции переходов, включая условные и безусловные переходы, CALL и RET, детектятся по маске при извлечении из L1-кэша инструкций (если не найдено в µops decoder cache).

Кстати, рекомендую поиграть в игры и туториалы, связанные с моделированием процессоров, такие, как MHRD, nand2teris, nandgame и подобные, чтобы понять, как работает декодер инструкций (по факту — самая менее затратная часть процессора по количеству элементов), и как группируются разнообразные инструкции в их битовом представлении.

[tumbler]

С одной стороны да, производительность кода — это важно. С другой стороны, приведенные примеры вообще не показательны, поскольку состоят только из проблемного кода. Вот статья "ошибочно предсказанное ветвление снижает производительность Chrome в разы" была бы бомбой, особенно если бы была описана методика поиска таких "ошибочных" мест.

[Amomum]

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

[gasizdat]

Andrey2008, как по мне — хорошая идея для статанализа.

[kosmos89]

как по мне, плохая идея для статанализа.

[mayorovp]

Статанализ проверяет всевозможные ветви исполнения, независимо от их вероятности. Это основное преимущество стататализа.

[gasizdat]

Именно это и является его преимуществом над динамическими анализаторами, тем же valgrind-ом. Ему не нужно подсчитывать статистику посещения каждой ветви. Можно включать эвристику, наподобие такой: если в теле if нет исключений или abort или terminate, а в else — есть, то тело if более вероятное, чем else. Или если в switch инструкции разобраны все случаи перечисления, то ветка default, будет маловероятной и т.п. случаи.

[pvl_1]

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

Мне кажется, автор имел в виду такты процессора.

[kosmos89]

Скорее переводчик. По-английски такт и есть cycle.

[pvl_1]

По-английски такт и есть cycle.

Я знаю, поэтому и написал об этом. То есть автор имел в виду такты, а переводчик использовал термин «цикл».

[4eyes]

Тем временем, свежие версии gcc и clang научились избавляться от ветвления в описанном случае. https://godbolt.org/z/JEVWLX

[kosmos89]

… особенно когда массив arr не используется и компилятор все, связанное с ним полностью выкинул :)

Вот так правильней: godbolt.org/z/P6c-WP — и ветвление вернулось на место.

[4eyes]

Да, я проглядел это. Считать четные оно умеет и без ветвления, а вот обращения в память, если их нельзя выкинуть, то уже не оптимизирует. Ну и не должно, в общем случае.

[pvl_1]

del

[tbl]

Только поаккуратнее с CMOV, он всегда медленнее, чем правильно предсказанное ветвление, т.к. он всегда декодируется в микрооперации (2 микрооперации на intel, и 1 микрооперация + еще 1 такт на amd), и он существенно ограничивает out-of-order исполнение.

Intel® 64 and IA-32 Architectures Optimization Reference Manual

Assembly/Compiler Coding Rule 2. (M impact, ML generality): Use the SETCC and CMOV instructions to eliminate unpredictable conditional branches where possible.

* Do not do this for predictable branches.

* Do not use these instructions to eliminate all unpredictable conditional branches (because using these instructions will incur execution overhead due to the requirement for executing both paths of a conditional branch).

* In addition, converting a conditional branch to SETCC or CMOV trades off control flow dependence for data dependence and restricts the capability of the out-of-order engine.

* When tuning, note that all Intel 64 and IA-32 processors usually have very high branch prediction rates. Consistently mispredicted branches are generally rare. Use these instructions only if the increase in computation time is less than the expected cost of a mispredicted branch.

[aamonster]

И почему отказались от delayed branch (был, например, в hitachi sh3) в пользу branch prediction?