Есть ли у компиляторов определенная эвристика оптимизации для поддержки прогнозирования ветвлений? Если нет, то почему нет?
Этот вопрос в основном является продолжением после прочтения Эта статья Aater Suleman по улучшению прогнозирования ветвлений со стороны программного обеспечения. Автор предоставляет способ «развернуть» условные операторы, чтобы увеличить вероятность предсказания перехода, взятого в случае 2-битной схемы с насыщенным счетчиком. Вот выдержка:
Позвольте мне объяснить на примере. Предположим, что X является случайной величиной от 0 до 99. Я хочу запустить следующий код:
если (X> 5 && Икс < 95) // ветка берется 90% времени
сделай что-нибудь();Однако, если я напишу код как:
if (X> 5) // ветвь берется 95% времени
если (X < 95) // ветка берется 95% времени
сделай что-нибудь();Предсказатель ветвления лучше подходит для более точного прогнозирования обеих этих ветвей, что может привести к повышению производительности, поскольку счетчики, назначенные обеим этим ветвям, с большей вероятностью останутся насыщенными при взятии (так как два непроизведенных менее вероятны).
В общем, всякий раз, когда вы выполняете условия ANDing / ORing в операторе if, вам следует подумать, будет ли комбинация более предвзятой или менее предвзятой, и выбрать версию, которая является более предвзятой.
Мой вопрос: все ли компиляторы следуют этой эвристике все время? Будет ли у компилятора хотя бы юрисдикция делать что-то подобное, поскольку компиляторы существуют в области ISA, а архитектуры и схемы прогнозирования ветвей существуют в области процессоров и более конкретных аппаратных реализаций?
Моя интуиция заключается в том, что такое расширение контрольных операторов не повредит производительности, но в то же время я не смог найти никаких доказательств того, что компиляторы делают такие оптимизации. Если это так, то почему бы и нет? Чего мне не хватает в моих рассуждениях, и может ли кто-нибудь привести пример, когда такая оптимизация может нанести ущерб определенной архитектуре или схеме прогнозирования?
Благодарю.
Решение
Кажется, что Сулеман не знает, что
if (X > 5 && X < 95)
do_something();
а также
if(X > 5)
if(X < 95)
do_something();
семантически эквивалентны в C и C ++. Последний стандарт C
(6.5.13 / 4):
В отличие от побитового двоичного & оператор, && операторские гарантии
оценка слева направо; если второй операнд вычислен, есть
точка последовательности между оценками первого и второго
операнды. Если первый операнд сравнивается равным 0, второй операнд
не оценивается.
Компилятор может генерировать или не генерировать один и тот же код для обоих примеров кода. Переписывание вашей программы для использования той или иной формы для повышения производительности не является хорошей идеей. Результаты будут сильно зависеть от версии компилятора, ISA и, возможно, большего количества переменных. Оставьте этот тип оптимизации компилятору, но предоставьте компилятору необходимую информацию.
Некоторые компиляторы, такие как GCC и LLVM, позволяют вам давать явные подсказки, подобные этой:
if (__builtin_expect(X > 5, 1)) {
// This block is likely to be taken.
}
if (__builtin_expect(X <= 5, 0)) {
// This block is unlikely to be taken.
}
Другой способ заключается в использовании профильной оптимизации. Первый шаг требует одного или нескольких тестовых прогонов вашей программы для создания базы данных со статистической информацией об инструкциях ветвления. На втором этапе компилятор может использовать эту базу данных для оптимизации вашей программы. Смотрите руководство вашего компилятора для более подробной информации.
Другие решения
Вы можете избежать двух ветвей, заменив этот код на
if (((unsigned int) X) - 6 < 88)
do_something ();
__Builtin_expect, очевидно, не может изменить, является ли условие истинным или ложным. В основном это используется для процессоров, где взятая ветвь медленнее, чем ветвь, которая не взята. Таким образом, компилятор будет компилировать
if (__builtin_expect (condition, 0))
statement;
morestuff ();
к этому:
if (condition) goto elsewhere;
backhere: morestuff ();
....
elsewhere: statement; goto backhere;
так что обычно ветка не берется вместо обычной
if (! condition) goto nextstatement;
statement;
nextstatement: morestuff ();
Но в этом вопросе вещи не работают таким образом. если (cond1 && cond2) не будет генерировать одну ветвь (только в особых случаях с очень умным компилятором), поэтому сравнение недопустимо. И если бы это было так, две ветви с правильным прогнозом 95% не лучше, чем одна ветка с 90%, потому что количество неправильных прогнозов будет одинаковым.