Можно ли сказать предиктору ветки, насколько вероятно следовать за веткой?
Просто чтобы прояснить, я не собираюсь здесь переносить что-либо, поэтому любые решения, которые привязывают меня к определенному блоку, подойдут.
По сути, у меня есть оператор if, который в 99% случаев оценивается как true, и я пытаюсь использовать все последние часы производительности, могу ли я выполнить какую-то команду компилятора (используя GCC 4.1.2 и ISA x86, если это имеет значение), чтобы сказать предиктору ветви, что он должен кэшировать для этой ветви?
7 ответов
Да. 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, и даже тогда они не делают ничего измеримого.
В архитектуре Netburst введен код операции "подсказка ветвления", представленный Intel, и статическое прогнозирование ветвления по умолчанию для "холодных" переходов (прогнозирование в обратном направлении выполнено, прогнозирование в прямом направлении не принято) в некоторых старых архитектурах. GCC реализует это с __builtin_expect (x, prediction)где прогноз обычно равен 0 или 1. Код операции, генерируемый компилятором, игнорируется на всех более новых архитектурах процессора (>= Core 2). Небольшой угловой случай, когда это действительно что-то делает, - это случай холодного прыжка на старой архитектуре Netburst. Корпорация Intel рекомендует не использовать статические подсказки ветвления, вероятно, потому, что они считают увеличение размера кода более вредным, чем возможное предельное ускорение.
Помимо бесполезной подсказки ветви для предиктора, __builtin_expect Если его использовать, компилятор может изменить порядок кода, чтобы улучшить использование кэша или сэкономить память.
Есть несколько причин, по которым он не работает, как ожидалось.
- Процессор может отлично предсказывать небольшие циклы (n<64).
- Процессор может предсказать небольшие повторяющиеся шаблоны (n~7) отлично.
- Сам процессор может оценить вероятность перехода во время выполнения лучше, чем компилятор / программист во время компиляции.
- Предсказуемость (= вероятность того, что ветвь будет правильно предсказана) ветвления гораздо важнее, чем вероятность того, что ветвь взята. К сожалению, это сильно зависит от архитектуры, и предсказать предсказуемость ветвления очень сложно.
Подробнее о внутренних работах по прогнозированию ветвей читайте в руководствах Agner Fogs. Смотрите также список рассылки gcc.
Pentium 4 (он же микроархитектура Netburst) имел подсказки-предикторы ветвей в качестве префиксов к инструкциям jcc, но только P4 когда-либо с ними что-то делал. См. http://ref.x86asm.net/geek32.html. И раздел 3.5 превосходного руководства Агнера Фога от http://www.agner.org/optimize/. У него также есть руководство по оптимизации в C++.
Ранее и позже процессоры x86 молча игнорировали эти префиксные байты. Есть ли результаты теста производительности для использования вероятных / маловероятных подсказок? упоминает, что PowerPC имеет некоторые инструкции перехода, которые имеют подсказку предсказания ветвления как часть кодирования. Это довольно редкая архитектурная особенность. Статическое прогнозирование ветвей во время компиляции очень сложно сделать точно, поэтому обычно лучше оставить это аппаратному обеспечению, чтобы выяснить это.
Официально опубликовано немного о том, как именно работают предсказатели ветвления и целевые буферы ветвления в самых последних процессорах Intel и AMD. Руководства по оптимизации (их легко найти на сайтах AMD и Intel) дают некоторые советы, но не документируют конкретное поведение. Некоторые люди запускают тесты, чтобы попытаться угадать реализацию, например, сколько записей BTB есть в Core2... В любом случае, идея явного намека на предиктор была отброшена (на данный момент).
Документировано, например, что у Core2 есть буфер истории ветвлений, который может избежать неправильного прогнозирования выхода из цикла, если цикл всегда выполняет постоянное короткое число итераций, < 8 или 16 IIRC. Но не спешите развертывать, потому что цикл, который умещается в 64 байта (или 19 мегапикселей на Penryn), не будет иметь узких мест при извлечении инструкций, потому что он воспроизводит из буфера... читайте pdf-файлы Agner Fog, они превосходны.
См. Также Почему 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. (Skylake-AVX512). Каждый тест получил по крайней мере небольшое ускорение, а некоторые выиграли примерно на 10%. (Большая часть этого, вероятно, происходит из-за развертывания циклов в горячих циклах, но, вероятно, из-за лучшего расположения веток и других эффектов.)
Я предлагаю вместо того, чтобы беспокоиться о прогнозировании ветвей, профилируйте код и оптимизируйте код, чтобы уменьшить количество ветвей. Один пример - развертывание цикла, а другой - использование методов логического программирования, а не использование if заявления.
Большинство процессоров любят предварительно выбирать операторы. Обычно оператор ветвления генерирует ошибку в процессоре, заставляя его сбрасывать очередь предварительной выборки. Это где самый большой штраф. Чтобы уменьшить это время штрафа, перепишите (и спроектируйте) код так, чтобы было доступно меньше ветвей. Кроме того, некоторые процессоры могут условно выполнять инструкции без необходимости ветвления.
Я оптимизировал программу с 1 часа времени выполнения до 2 минут, используя развертывание цикла и большие буферы ввода / вывода. Прогнозирование ветвления в этом случае не принесло бы большой экономии времени.
SUN C Studio имеет несколько прагм, определенных для этого случая.
#pragma rarely_called ()
Это работает, если одна часть условного выражения является вызовом функции или начинается с вызова функции.
Но нет способа пометить универсальный оператор if/while
Это звучит для меня как излишнее - этот тип оптимизации сэкономит крошечное количество времени. Например, использование более современной версии gcc окажет гораздо большее влияние на оптимизацию. Кроме того, попробуйте включить и отключить все различные флаги оптимизации; они не все улучшают производительность.
По сути, кажется невероятным, что это будет иметь какое-то существенное значение по сравнению со многими другими плодотворными путями.
РЕДАКТИРОВАТЬ: спасибо за комментарии. Я сделал это сообщество вики, но оставил его, чтобы другие могли видеть комментарии.
Нет, потому что нет команды ассемблера, чтобы сообщить предиктору ветвления. Не беспокойтесь об этом, предсказатель ветвления довольно умен.
Также обязателен комментарий о преждевременной оптимизации и о том, как это плохо.
РЕДАКТИРОВАТЬ: Drakosha упомянул некоторые макросы для GCC. Тем не менее, я считаю, что это оптимизация кода и на самом деле не имеет ничего общего с предсказанием ветвлений.