Можно ли сказать предсказателю ветвления, насколько вероятно, что он последует за ветвью?

StackOverflow https://stackoverflow.com/questions/1851299

Вопрос

Просто чтобы было ясно, я не стремлюсь к какой-либо переносимости здесь, поэтому любые решения, которые привяжут меня к определенному блоку, подойдут.

В принципе, у меня есть оператор if, который в 99% случаев принимает значение true, и я пытаюсь увеличить производительность до последнего такта, могу ли я выдать какую-нибудь команду компилятора (используя GCC 4.1.2 и x86 ISA, если это имеет значение), чтобы сообщить предсказателю ветвления, что он должен кэшировать для этой ветви?

Это было полезно?

Решение

ДА. http://kerneltrap.org/node/4705

В __builtin_expect это метод, который gcc (версии >= 2.96) предлагает для программистов указывать ветвление информацию о прогнозировании для компилятора.Возвращаемое значение __builtin_expect является первым аргументом (который может быть только целым числом) передается ему.

if (__builtin_expect (x, 0))
                foo ();

     [This] would indicate that we do not expect to call `foo', since we
     expect `x' to be zero.

Другие советы

Да, но это будет иметь НЕТ эффект.Исключения составляют более старые (устаревшие) архитектуры, существовавшие до Netburst, и даже тогда они не делают ничего измеримого.

Существует код операции "подсказка о ветвлении", введенный Intel с архитектурой Netburst, и статическое предсказание ветвления по умолчанию для холодных переходов (с обратным прогнозом принято, с прямым прогнозом не принято) на некоторых старых архитектурах.GCC реализует это с помощью __builtin_expect (x, prediction), где прогноз обычно равен 0 или 1.Код операции , выдаваемый компилятором, является проигнорированный на всех более новых архитектурах процессоров (>= Core 2).Небольшой угловой случай, когда это действительно что-то дает, - это случай холодного перехода к старой архитектуре Netburst.Intel рекомендует теперь не использовать подсказки статического перехода, вероятно, потому, что они считают увеличение размера кода более вредным, чем возможное предельное ускорение.

Помимо бесполезной подсказки о ветвлении для предсказателя, __builtin_expect при его использовании компилятор может изменить порядок кода, чтобы улучшить использование кэша или сэкономить память.

Есть несколько причин, по которым это работает не так, как ожидалось.

  • Процессор может предсказать небольшие циклы (n<64) прекрасно.
  • Процессор может идеально предсказывать небольшие повторяющиеся паттерны (n ~ 7).
  • Сам процессор может оценить вероятность ветвления во время выполнения лучше, чем компилятор / программист во время компиляции.
  • В предсказуемость (= вероятность того, что ответвление будет предсказано правильно) для ответвления гораздо важнее, чем вероятность того, что ответвление будет принято.К сожалению, это сильно зависит от архитектуры, и предсказать предсказуемость перехода, как известно, очень сложно.

Подробнее о внутренней работе предсказания ветвей читайте у Агнера Фогса руководства.Смотрите также gcc список рассылки.

Pentium 4 (он же микроархитектура Netburst) имел подсказки для предсказания ветвлений в качестве префиксов к инструкциям jcc, но только P4 когда-либо что-либо делал с ними.Видишь http://ref.x86asm.net/geek32.html.И Раздел 3.5 превосходного руководства Агнера Фога по выбору asm, из http://www.agner.org/optimize/.У него тоже есть руководство по оптимизации на C ++.

Более ранние и более поздние процессоры x86 молча игнорируют эти байты префикса. Существуют ли какие-либо результаты тестирования производительности для использования вероятных / маловероятных подсказок? упоминает, что PowerPC имеет некоторые инструкции перехода, которые содержат подсказку о предсказании ветвления как часть кодирования.Это довольно редкая архитектурная особенность.Статическое прогнозирование ветвей во время компиляции очень сложно выполнить точно, поэтому обычно лучше оставить это на усмотрение оборудования, чтобы разобраться с этим.

Официально опубликовано не так много информации о том, как именно работают предикторы ветвления и буферы ветвления-цели в самых последних процессорах Intel и AMD.Руководства по оптимизации (их легко найти на веб-сайтах AMD и Intel) дают некоторые советы, но не документируют конкретное поведение.Некоторые люди запускали тесты, чтобы попытаться предугадать реализацию, напримерсколько записей BTB в Core2...В любом случае, идея явного указания предиктора была оставлена (на данный момент).

Что документировано, так это, например, то, что Core2 имеет буфер истории ветвлений, который может избежать неправильного прогнозирования завершения цикла, если цикл всегда выполняет постоянное короткое число итераций, < 8 или 16 IIRC.Но не торопитесь разворачивать, потому что цикл, который умещается в 64 байта (или 19 операций в секунду на Penryn), не будет иметь узких мест для извлечения инструкций, поскольку он воспроизводится из буфера...иди почитай PDF-файлы Агнера Фога, они превосходно.

Смотрите также Почему Intel изменила механизм статического прогнозирования ветвлений за эти годы? :Intel, начиная с Sandybridge, вообще не использует статическое предсказание, насколько мы можем судить по экспериментам с производительностью, в которых предпринимаются попытки реинжиниринга того, что делают процессоры.(Многие старые процессоры имеют статическое предсказание в качестве запасного варианта на случай, если динамическое предсказание не выполняется.Обычное статическое предсказание заключается в том, что прямые ветви не принимаются, а обратные ветви принимаются (потому что обратные ветви часто являются ответвлениями цикла).)

Эффект от likely()/unlikely() макросы, использующие GNU C __builtin_expect (как упоминает ответ Дракоши) делает не непосредственно вставляйте подсказки BP в asm.(Возможно, это могло бы сделать это с gcc -march=pentium4, но не при компиляции для чего-либо другого).

Фактический эффект заключается в том, чтобы расположить код таким образом, чтобы в быстром пути было меньше занятых ветвей и, возможно, всего меньше инструкций.Это поможет предсказанию ветвления в случаях, когда в игру вступает статическое предсказание (напримердинамические предикторы являются холодными на процессорах, которые возвращаются к статическому предсказанию вместо того, чтобы просто позволять ветвям называть друг друга псевдонимами в кэшах предикторов.)

Видишь В чем преимущество __builtin_expect от GCC в операторах if else? для конкретного примера code-gen.

Снятые ветви стоят немного дороже, чем не снятые ветви, даже при идеальном прогнозировании.Когда центральный процессор извлекает код порциями по 16 байт для параллельного декодирования, принятое ответвление означает, что последующие инструкции в этом блоке выборки не являются частью потока команд, подлежащего выполнению.Это создает пузырьки во внешнем интерфейсе, которые могут стать узким местом в высокопроизводительном коде (который не останавливается во внутреннем интерфейсе из-за промахов кэша и имеет высокий параллелизм на уровне команд).

Переключение между различными блоками также потенциально затрагивает больше строк кода в кэше, увеличивая объем кэша L1i и, возможно, вызывая больше пропусков в кэше команд, если он был холодным.(И потенциально занимаемый объем uop-кэша).Так что это еще одно преимущество того, что быстрый путь должен быть коротким и линейным.

Оптимизация, ориентированная на профиль GCC, обычно делает ненужными вероятные / маловероятные макросы.Компилятор собирает данные во время выполнения о том, каким путем пошла каждая ветвь для принятия решений по компоновке кода, и для определения горячих ихолодные блоки / функции.(например,он будет разворачивать циклы в горячих функциях, но не в холодных функциях.) Смотрите -fprofile-generate и -fprofile-use в руководстве GCC. Как использовать оптимизацию, ориентированную на профиль, в g ++?

В противном случае GCC должен угадать, используя различные эвристики, если вы не использовали вероятные / маловероятные макросы и не использовали PGO. -fguess-branch-probability включен по умолчанию в -O1 и выше.

https://www.phoronix.com/scan.php?page=article&item=gcc-82-pgo&num=1 имеет результаты бенчмарка для PGO по сравнениюобычный с gcc8.2 на масштабируемом серверном процессоре Xeon.(Скайлейк-AVX512).Каждый бенчмарк получил по крайней мере небольшое ускорение, а некоторые выиграли ~ на 10%.(Большая часть этого, вероятно, связана с развертыванием цикла в горячих циклах, но некоторые из них, по-видимому, связаны с улучшенным расположением ветвей и другими эффектами.)

Я предлагаю вместо того, чтобы беспокоиться о прогнозировании ветвлений, профилировать код и оптимизировать его, чтобы уменьшить количество ветвей.Одним примером является развертывание цикла, а другим - использование методов логического программирования вместо использования if заявления.

Большинство процессоров любят выполнять предварительную выборку инструкций.Как правило, оператор перехода генерирует неисправность внутри процессора, заставляя его очищать очередь предварительной выборки.Вот где самое большое наказание.Чтобы сократить это штрафное время, перепишите (и разработайте) код таким образом, чтобы было доступно меньше ветвей.Кроме того, некоторые процессоры могут условно выполнять инструкции без необходимости ветвления.

Я оптимизировал время выполнения программы с 1 часа до 2 минут, используя развертывание цикла и большие буферы ввода-вывода.Прогнозирование ветвления в данном случае не дало бы большой экономии времени.

В SUN C Studio есть несколько прагм, определенных для этого случая.

#редко вызываемая прагма ()

Это работает, если одна часть условного выражения является вызовом функции или начинается с вызова функции.

Но нет никакого способа пометить общий оператор if / while

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

Также обязательный комментарий о преждевременной оптимизации и о том, насколько это зло.

Редактировать:Дракоша упомянул некоторые макросы для GCC.Однако я считаю, что это оптимизация кода и на самом деле не имеет ничего общего с предсказанием ветвления.

Мне это кажется излишеством - такой тип оптимизации сэкономит крошечное количество времени.Например, использование более современной версии gcc окажет гораздо большее влияние на оптимизацию.Кроме того, попробуйте включить и отключить все различные флаги оптимизации;не все они повышают производительность.

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

Редактировать:спасибо за комментарии.Я создал эту вики-страницу сообщества, но оставил ее в, чтобы другие могли видеть комментарии.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top