Есть ли подсказка компилятора для GCC, чтобы заставить предсказание ветвления всегда идти определенным путем?

118

Для архитектур Intel есть ли способ инструктировать компилятор GCC генерировать код, который всегда вызывает предсказание ветвления определенным образом в моем коде? Поддерживает ли это оборудование Intel? А как насчет других компиляторов или оборудования?

Я бы использовал это в коде C ++, где я знаю случай, когда я хочу работать быстро, и не беспокоюсь о замедлении, когда нужно перейти в другую ветвь, даже если она недавно приняла эту ветку.

for (;;) {
  if (normal) { // How to tell compiler to always branch predict true value?
    doSomethingNormal();
  } else {
    exceptionalCase();
  }
}

В качестве следующего вопроса для Евджана Мустафы, может ли подсказка просто указать подсказку, когда процессор впервые встречает инструкцию, все последующие предсказания ветвления работают нормально?

WilliamKF
источник
также может вызвать исключение, если что-то станет ненормальным (независимо от компилятора)
Шеп

Ответы:

9

Начиная с C ++ 20 вероятные и маловероятные атрибуты должны быть стандартизированы и уже поддерживаются в g ++ 9 . Итак, как обсуждалось здесь , вы можете написать

if (a>b) {
  /* code you expect to run often */
  [[likely]] /* last statement */
}

например, в следующем коде блок else становится встроенным благодаря [[unlikely]]блоку if

int oftendone( int a, int b );
int rarelydone( int a, int b );
int finaltrafo( int );

int divides( int number, int prime ) {
  int almostreturnvalue;
  if ( ( number % prime ) == 0 ) {
    auto k                         = rarelydone( number, prime );
    auto l                         = rarelydone( number, k );
    [[unlikely]] almostreturnvalue = rarelydone( k, l );
  } else {
    auto a            = oftendone( number, prime );
    almostreturnvalue = oftendone( a, a );
  }
  return finaltrafo( almostreturnvalue );
}

ссылка Godbolt для сравнения наличия / отсутствия атрибута

pseyfert
источник
Зачем использовать [[unlikely]]в ifvs [[likely]]в else?
WilliamKF
без причины, просто попал в это созвездие после попытки определить, куда должен перейти атрибут.
Псейферт
Довольно круто. Жаль, что этот метод не применим к более старым версиям C ++.
Максим Егорушкин
Фантастическая ссылка на Godbolt
Льюис Келси
87

GCC поддерживает функцию, __builtin_expect(long exp, long c)обеспечивающую такую ​​возможность. Вы можете проверить документацию здесь .

Где expиспользуется условие, а где c- ожидаемое значение. Например, в вашем случае вы хотите

if (__builtin_expect(normal, 1))

Из-за неудобного синтаксиса это обычно используется путем определения двух настраиваемых макросов, например

#define likely(x)    __builtin_expect (!!(x), 1)
#define unlikely(x)  __builtin_expect (!!(x), 0)

просто чтобы облегчить задачу.

Имейте в виду, что:

  1. это нестандартно
  2. предсказатель ветвления компилятора / процессора, вероятно, более квалифицирован, чем вы, в принятии таких решений, поэтому это может быть преждевременной микрооптимизацией
разъем
источник
3
Есть ли причина, по которой вы показываете макрос, а не constexprфункцию?
Коломбо
22
@Columbo: я не думаю, что constexprфункция может заменить этот макрос. ifЯ считаю, что это должно быть прямо в заявлении. По той же причине assertникогда не могло быть constexprфункцией.
Mooing Duck
1
@MooingDuck Я согласен, хотя есть и другие причины для утверждения .
Шафик Ягмур
7
@Columbo - одна из причин использовать макрос, потому что это одно из немногих мест в C или C ++, где макрос семантически более корректен, чем функция. Функция появляется только на работу из - за оптимизации (это является оптимизация: constexprговорит только о стоимости семантике, а не встраивание в конкретной реализации сборки); прямая интерпретация (без встроенного кода) бессмысленна. Нет никаких причин использовать для этого функцию.
Леушенко
2
@Leushenko Считайте, что это __builtin_expectсамо по себе подсказка по оптимизации, поэтому утверждение, что метод, упрощающий его использование, зависит от оптимизации ... неубедительно. Кроме того, я добавил constexprспецификатор не для того, чтобы он работал в первую очередь, а для того, чтобы он работал в постоянных выражениях. И да, есть причины использовать функцию. Например, я бы не хотел засорять все свое пространство имен милым маленьким именем, например likely. Я бы использовал, например LIKELY, чтобы подчеркнуть, что это макрос, и избежать коллизий, но это просто уродливо.
Коломбо
46

gcc имеет long __builtin_expect (long exp, long c) ( выделено мной ):

Вы можете использовать __builtin_expect, чтобы предоставить компилятору информацию о предсказании ветвления. В общем, вы должны предпочесть использовать для этого фактическую обратную связь с профилем (-fprofile-arcs), так как программисты, как известно, плохо предсказывают, как их программы на самом деле работают . Однако есть приложения, в которых сложно собрать эти данные.

Возвращаемое значение - это значение exp, которое должно быть интегральным выражением. Семантика встроенного такова, что ожидается, что exp == c. Например:

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

указывает, что мы не ожидаем вызова foo, поскольку ожидаем, что x будет равно нулю. Поскольку вы ограничены интегральными выражениями для exp, вам следует использовать такие конструкции, как

if (__builtin_expect (ptr != NULL, 1))
   foo (*ptr);

при тестировании указателей или значений с плавающей запятой.

Как отмечается в документации, вы должны предпочесть использовать фактическую обратную связь с профилем, и в этой статье показан практический пример этого и то, как в их случае, по крайней мере, в конечном итоге становится лучше, чем использование __builtin_expect. Также см. Как использовать оптимизацию под руководством профиля в g ++? ,

Мы также можем найти статью для новичков в ядре Linux о макросах ядра вероятно () и маловероятно (), которые используют эту функцию:

#define likely(x)       __builtin_expect(!!(x), 1)
#define unlikely(x)     __builtin_expect(!!(x), 0)

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

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

Обратите внимание: хотя встроенные команды не переносятся, clang также поддерживает __builtin_expect .

Также на некоторых архитектурах это может не иметь значения .

Шафик Ягмур
источник
То, что достаточно хорошо для ядра Linux, недостаточно для C ++ 11.
Максим Егорушкин
Примечание @MaximEgorushkin, я на самом деле не рекомендую его использовать, на самом деле документация gcc, которую я цитирую, которая является моей первой цитатой, даже не использует эту технику. Я бы сказал, что основная цель моего ответа - внимательно рассмотреть альтернативы, прежде чем идти по этому пути.
Шафик Ягмур
44

Нет, нет. (По крайней мере, на современных процессорах x86.)

__builtin_expectупомянутые в других ответах влияют на то, как gcc упорядочивает код сборки. Он не влияет напрямую на предсказатель ветвления ЦП. Конечно, переупорядочение кода окажет косвенное влияние на предсказание ветвлений. Но на современных процессорах x86 нет инструкции, которая говорит ЦП «предположить, что эта ветвь занята / не занята».

См. Этот вопрос для более подробной информации: Intel x86 0x2E / 0x3E Prefix Branch Prediction действительно используется?

Чтобы быть ясным, __builtin_expectи / или использование -fprofile-arcs может улучшить производительность вашего кода, как путем предоставления подсказок для предсказателя ветвления через макет кода (см. Оптимизация производительности сборки x86-64 - Выравнивание и прогнозирование ветвления ), так и за счет улучшения поведения кеша за счет отделения «маловероятного» кода от «вероятного».

Artelius
источник
9
Это неверно. Во всех современных версиях x86 алгоритм прогнозирования по умолчанию предполагает, что прямые переходы не выполняются, а обратные переходы выполняются (см. Software.intel.com/en-us/articles/… ). Таким образом, изменяя код, вы можете эффективно дать подсказку процессору. Это именно то, что делает GCC при использовании __builtin_expect.
Nemo
6
@Nemo, ты прочитал первое предложение моего ответа? Все, что вы сказали, покрыто моим ответом или приведенными ссылками. Был задан вопрос, можно ли «заставить предсказание ветвления всегда идти определенным путем», на который был дан ответ «нет», и я не чувствовал, что другие ответы достаточно ясны по этому поводу.
Artelius
4
Хорошо, мне следовало читать внимательнее. Мне кажется, что этот ответ технически правильный, но бесполезный, поскольку спрашивающий явно ищет __builtin_expect. Так что это должен быть просто комментарий. Но это не ложь, поэтому я снял свой голос против.
Nemo
ИМО, это не бесполезно; это полезное разъяснение того, как на самом деле работают процессоры и компиляторы, что может иметь отношение к анализу производительности с этими параметрами или без них. например, вы обычно не можете использовать __builtin_expectтривиально для создания тестового примера, который вы можете измерить, perf statкоторый будет иметь очень высокую частоту ошибочного предсказания ветвления. Это просто влияет на расположение веток . И, кстати, Intel с Sandybridge или, по крайней мере, Haswell не использует статическое предсказание много / вообще; В BHT всегда есть какое-то предсказание, будь то устаревший псевдоним или нет. xania.org/201602/bpu-part-two
Питер Кордес
24

Правильный способ определения вероятных / маловероятных макросов в C ++ 11 следующий:

#define LIKELY(condition) __builtin_expect(static_cast<bool>(condition), 1)
#define UNLIKELY(condition) __builtin_expect(static_cast<bool>(condition), 0)

Этот метод, в отличие от него [[likely]], совместим со всеми версиями C ++, но полагается на нестандартное расширение __builtin_expect.


Когда эти макросы определены таким образом:

#define LIKELY(condition) __builtin_expect(!!(condition), 1)

Это может изменить смысл ifоператоров и нарушить код. Рассмотрим следующий код:

#include <iostream>

struct A
{
    explicit operator bool() const { return true; }
    operator int() const { return 0; }
};

#define LIKELY(condition) __builtin_expect((condition), 1)

int main() {
    A a;
    if(a)
        std::cout << "if(a) is true\n";
    if(LIKELY(a))
        std::cout << "if(LIKELY(a)) is true\n";
    else
        std::cout << "if(LIKELY(a)) is false\n";
}

И его вывод:

if(a) is true
if(LIKELY(a)) is false

Как видите, определение LIKELY using !!в качестве приведения boolнарушает семантику if.

Дело здесь не в этом operator int()и operator bool()должно быть связано. Это хорошая практика.

Вместо этого использование !!(x)вместо static_cast<bool>(x)теряет контекст для контекстных преобразований C ++ 11 .

Максим Егорушкин
источник
Обратите внимание, что контекстные преобразования произошли из-за дефекта в 2012 году, и даже в конце 2014 года расхождения в реализации все еще наблюдались. На самом деле похоже, что дело, с которым я связался, все еще не работает для gcc.
Шафик Ягмур,
@ShafikYaghmour Это интересное наблюдение относительно задействованного контекстного преобразования switch, спасибо. Используемое здесь контекстное преобразование частично связано с типом boolи пятью конкретными контекстами, перечисленными там , которые не включают switchконтекст.
Максим Егорушкин
Это влияет только на C ++, верно? Так что нет причин менять существующие проекты C для использования (_Bool)(condition), потому что C не имеет перегрузки операторов.
Питер Кордес
2
В вашем примере вы использовали just (condition), not !!(condition). Оба trueпосле изменения этого (протестировано с g ++ 7.1). Можете ли вы построить пример, который действительно демонстрирует проблему, о которой вы говорите, когда используете !!для логического преобразования?
Питер Кордес
3
Как отметил Питер Кордес, вы говорите: «Когда эти макросы [определены] таким образом:», а затем показываете макрос с помощью символа «!!», «может изменить значение операторов if и нарушить код. Рассмотрим следующий код:» ... а затем вы показываете код, который не использует "!!" вообще - который, как известно, был сломан еще до C ++ 11. Измените ответ, чтобы показать пример, в котором данный макрос (с использованием !!) работает неправильно.
Карло Вуд
18

Поскольку все другие ответы были адекватно предложены, вы можете использовать, __builtin_expectчтобы дать компилятору подсказку о том, как организовать код сборки. Как отмечают официальные документы , в большинстве случаев встроенный в ваш мозг ассемблер будет не так хорош, как ассемблер, созданный командой GCC. Для оптимизации кода всегда лучше использовать фактические данные профиля, а не гадать.

Аналогичным образом, но еще не упомянутым, существует специфичный для GCC способ заставить компилятор генерировать код по «холодному» пути. Это предполагает использование noinlineи coldатрибутов, которые делают именно то , что они звучат , как они делают. Эти атрибуты могут применяться только к функциям, но в C ++ 11 вы можете объявлять встроенные лямбда-функции, и эти два атрибута также могут применяться к лямбда-функциям.

Хотя это все еще попадает в общую категорию микрооптимизации, и поэтому применяется стандартный совет - тестируйте, а не угадайте - я считаю, что в целом он более полезен, чем __builtin_expect. Вряд ли какие-либо поколения процессоров x86 используют подсказки предсказания ветвления ( справочные ), поэтому единственное, на что вы все равно сможете повлиять, - это порядок кода сборки. Поскольку вы знаете, что такое код обработки ошибок или «пограничный» код, вы можете использовать эту аннотацию, чтобы гарантировать, что компилятор никогда не предскажет ответвление для него и свяжет его с «горячим» кодом при оптимизации по размеру.

Пример использования:

void FooTheBar(void* pFoo)
{
    if (pFoo == nullptr)
    {
        // Oh no! A null pointer is an error, but maybe this is a public-facing
        // function, so we have to be prepared for anything. Yet, we don't want
        // the error-handling code to fill up the instruction cache, so we will
        // force it out-of-line and onto a "cold" path.
        [&]() __attribute__((noinline,cold)) {
            HandleError(...);
        }();
    }

    // Do normal stuff
    
}

Более того, GCC автоматически проигнорирует это в пользу обратной связи профиля, когда она доступна (например, при компиляции с -fprofile-use).

См. Официальную документацию здесь: https://gcc.gnu.org/onlinedocs/gcc/Common-Function-Attributes.html#Common-Function-Attributes

Коди Грей
источник
2
Префиксы подсказки предсказания ветвления игнорируются, потому что они не нужны; вы можете добиться того же эффекта, просто переупорядочив свой код. (Алгоритм прогнозирования ветвлений по умолчанию предполагает, что обратные ветки берутся, а прямые - нет.) Таким образом, вы, по сути, можете дать ЦП подсказку, и вот что он __builtin_expectделает. Это совсем не бесполезно. Вы правы в том, что coldатрибут тоже полезен, но __builtin_expectя думаю , вы недооцениваете полезность .
Nemo
Современные процессоры Intel не используют статическое предсказание ветвлений. Алгоритм, который вы описываете, @Nemo, в котором предсказываются обратные ветки, а прямые ветки предсказываются как неиспользованные, использовались в более ранних процессорах, и вплоть до Pentium M или около того, но современные конструкции просто в основном предполагают случайным образом, индексируя в свою ветку таблицы, в которых можно было бы ожидать найти информацию об этой ветке и использовать любую имеющуюся информацию (даже если это может быть по существу мусор). Таким образом, подсказки предсказания ветвления теоретически могут быть полезны, но, возможно, не на практике, поэтому Intel удалила их.
Коди Грей
Чтобы было ясно, реализация предсказания ветвлений чрезвычайно сложна, и ограниченность места в комментариях вынудила меня значительно упростить. Это действительно был бы исчерпывающий ответ сам по себе. В современных микроархитектурах, таких как Haswell, все еще могут быть остатки статического предсказания ветвлений, но это не так просто, как раньше.
Коди Грей
У вас есть ссылка на «современные процессоры Intel не используют статическое предсказание ветвлений»? В собственной статье Intel ( software.intel.com/en-us/articles/… ) говорится иное ... Но это с 2011 года
Nemo
На самом деле нет официальной ссылки, @Nemo. Intel крайне молчаливо относится к алгоритмам прогнозирования ветвлений, используемым в ее чипах, считая их коммерческой тайной. Большинство из того, что известно, было выяснено эмпирическим путем. Как всегда, материалы Агнера Фога - лучшие ресурсы, но даже он говорит: «Предиктор ветвления, похоже, был переработан в Haswell, но очень мало известно о его конструкции». Я не могу вспомнить, где я впервые увидел тесты, демонстрирующие, что статический АД больше не используется, к сожалению.
Коди Грей
5

__builtin_expect можно использовать, чтобы сообщить компилятору, в каком направлении должна идти ветвь. Это может повлиять на то, как генерируется код. Типичные процессоры последовательно запускают код быстрее. Итак, если вы напишете

if (__builtin_expect (x == 0, 0)) ++count;
if (__builtin_expect (y == 0, 0)) ++count;
if (__builtin_expect (z == 0, 0)) ++count;

компилятор сгенерирует код вроде

if (x == 0) goto if1;
back1: if (y == 0) goto if2;
back2: if (z == 0) goto if3;
back3: ;
...
if1: ++count; goto back1;
if2: ++count; goto back2;
if3: ++count; goto back3;

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

В новых процессорах x86 есть инструкции для ветвей, которые, как ожидается, будут выполняться, или для веток, которые, как ожидается, не будут выполняться (есть префикс инструкции; не уверен в деталях). Не уверен, что процессор использует это. Это не очень полезно, потому что с этим отлично справится предсказание ветвления. Поэтому я не думаю, что вы действительно можете повлиять на предсказание ветвления .

gnasher729
источник
2

Что касается OP, нет, в GCC нет способа указать процессору всегда предполагать, что ветвь взята или не занята. У вас есть __builtin_expect, который делает то, что другие говорят. Кроме того, я думаю , вы не хотите сказать , процессор ли берется ветвь или не всегда . Современные процессоры, такие как архитектура Intel, могут распознавать довольно сложные шаблоны и эффективно адаптироваться.

Однако бывают случаи, когда вы хотите взять на себя управление тем, будет ли по умолчанию предсказано, что ветвление выполнено или нет: когда вы знаете, что код будет называться «холодным» в отношении статистики ветвления.

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

Другой пример: вы можете классифицировать свой ввод и перейти к коду, который обрабатывает результат вашей классификации. Если существует много классификаций, процессор может собирать статистику, но терять ее, потому что такая же классификация не происходит достаточно скоро, а ресурсы прогнозирования выделяются для недавно вызванного кода. Я бы хотел, чтобы был примитив, который говорил процессору «пожалуйста, не выделяйте ресурсы прогнозирования для этого кода», как иногда можно сказать «не кэшировать это».

TheCppZoo
источник