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

Я только что наткнулся на эту статью: вычислите минимум или максимум двух целых чисел без ветвления

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

Раньше я думал, что ветвление всегда дорого, поскольку оно часто заставляет процессор очищать и перезапускать конвейер выполнения (например, см. Почему сортированный массив обрабатывается быстрее, чем несортированный массив?).

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

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

1 ответ:

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

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

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

Есть ли у современных процессоров способ завершить минимальные ветви, подобные той, что находится в (x

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

[4] здесь нет серебряной пули. С предсказуемые результаты, ветвление происходит быстрее. Выяснить точно, какой паттерн распознает процессор, сложно. JVM просто смотрит на то, как часто ветка получает дубли и использует магический порог около 18%. Смотрите мои собственныевопрос и ответ для получения подробной информации.

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

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

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

6