Оптимизация кода, чтобы избежать ветвления

Question

Я просто наткнулся на эту статью: Compute the minimum or maximum of two integers without branching

Он начинается с «[о] н некоторых редких машинах, где ветвление дорого ...».

Раньше я думал, что ветвление всегда дорого, поскольку оно часто заставляет процессор очищать и перезапускать конвейер выполнения (например, см. Why is it faster to process a sorted array than an unsorted array?).

Это оставляет меня пару вопросов:

• ли автор статьи получить, что часть не так? Или эта статья может быть написана за раз до того, как возникла проблема ветвления (я не могу найти дату на ней).
• У современных процессоров есть способ завершить минимальные ветви, например, в (x < y) ? x : y без ухудшения производительности?
• Или все современные компиляторы просто реализуют этот хак автоматически? В частности, что делает Java? Тем более, что его Math.min(...) функции только что тройное заявление ...

Answer 1

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

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

Но в некотором смысле автор прав. Большинство процессоров не найдено на наших ПК и серверах, а во встроенных устройствах, где ситуация отличается.

У современных процессоров есть способ завершить минимальные ветви, например, в (x <)? x: y без ухудшения производительности?

Да и нет. AFAIK Math.max всегда переводится как условное перемещение, что означает отсутствие ветвления. Вы владеете max, может или не может его использовать, в зависимости от статистики, собранной JVM.

Нет серебряной пули. С прогнозируемыми результатами ветвление происходит быстрее. Выяснив, какой шаблон распознает процессор, сложно. JVM просто смотрит, как часто получает ветвь и использует магический порог около 18%. См. Мои собственные question and answer.

Или все современные компиляторы просто реализуют этот хак автоматически? В частности, что делает Java? Тем более, что его функция Math.min (...) - это только трехмерное заявление ...

Это на самом деле собственный компилятор. Всякий раз, когда JITc видит этот метод, он обрабатывает его специально. Когда вы копируете метод, он не получает специальных обработок.

В этом случае внутреннее значение не очень полезно, так как это то, что в любом случае сильно оптимизируется.Для таких методов, как Long#numberOfLeadingZeros, неотъемлемая часть важна, так как code довольно длинный и медленный, и современные процессоры получают это за один цикл.