Как работают вероятные / маловероятные макросы в ядре Linux и в чем их выгода?

349

Я копался в некоторых частях ядра Linux и нашел такие вызовы:

if (unlikely(fd < 0))
{
    /* Do something */
}

или

if (likely(!err))
{
    /* Do something */
}

Я нашел их определение:

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

Я знаю, что они для оптимизации, но как они работают? И насколько можно ожидать снижения производительности / размера от их использования? И стоит ли хлопот (и, вероятно, потери переносимости) хотя бы в узких местах (конечно, в пользовательском пространстве).

конечная станция
источник
7
Это действительно не специфично для ядра Linux или макросов, а для оптимизации компилятора. Должно ли это быть изменено, чтобы отразить это?
Коди Брошиус
11
В статье « Что должен знать каждый программист о памяти» (стр. 57) содержится подробное объяснение.
Торстен Марек
2
смотрите такжеBOOST_LIKELY
Ruggero Turra
4
По теме: ориентир по использованию__builtin_expect по другому вопросу.
YSC
13
Там нет проблемы переносимости. Вы можете тривиально делать такие вещи, как #define likely(x) (x)и #define unlikely(x) (x)на платформах, которые не поддерживают такого рода подсказки.
Дэвид Шварц

Ответы:

329

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

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

1800 ИНФОРМАЦИЯ
источник
3
Эти макросы в основном использовались для проверки ошибок. Потому что ошибка оставляет меньше вероятности, чем нормальная работа. Несколько человек делают профилирование или расчет, чтобы выбрать наиболее используемый лист ...
gavenkoa
51
Что касается фрагмента "[...]that it is being run in a tight loop", многие процессоры имеют предиктор ветвления , поэтому использование этих макросов помогает только при первом выполнении временного кода или когда таблица истории перезаписывается другой ветвью с таким же индексом в таблицу ветвления. В тесном цикле, и, предполагая, что ветвь идет одним путем большую часть времени, предиктор ветвления, скорее всего, начнет угадывать правильную ветвь очень быстро. - твой друг в педантичности.
Росс Роджерс
8
@RossRogers: Что действительно происходит, так это то, что компилятор размещает ветки, поэтому общий случай - это неисполнение. Это быстрее, даже когда предсказание ветвлений работает. Взятые ветви проблематичны для извлечения и декодирования инструкций, даже когда они предсказаны идеально. Некоторые процессоры статически предсказывают ветви, которых нет в их таблице истории, обычно с предположением, что они не приняты для прямых ветвей. Процессоры Intel не работают таким образом: они не пытаются проверить, что запись таблицы предикторов предназначена для этой ветви, они просто используют ее в любом случае. Горячая ветвь и холодная ветвь могут иметь одно и то же имя ...
Питер Кордес
12
Этот ответ в основном устарел, поскольку основное утверждение состоит в том, что он помогает прогнозировать ветвления, и, как указывает @PeterCordes, в большинстве современных аппаратных средств нет неявного или явного статического предсказания ветвлений. Фактически подсказка используется компилятором для оптимизации кода, будь то статические подсказки ветвления или любой другой тип оптимизации. Для большинства современных архитектур важна «любая другая оптимизация», например, создание смежных горячих путей, лучшее планирование горячего пути, минимизация размера медленного пути, векторизация только ожидаемого пути и т. Д. И т. Д.
BeeOnRope
3
@BeeOnRope из-за предварительной выборки в кэш и размера слова, все еще есть преимущество в линейном запуске программы. Следующая ячейка памяти уже будет извлечена и помещена в кеш, цель ветвления может быть, а может и нет. С 64-битным процессором вы получаете как минимум 64 бита за раз. В зависимости от чередования DRAM, это может быть 2x 3x или больше битов, которые будут захвачены.
Брайс
88

Давайте декомпилируем, чтобы увидеть, что GCC 4.8 делает с ним

Без __builtin_expect

#include "stdio.h"
#include "time.h"

int main() {
    /* Use time to prevent it from being optimized away. */
    int i = !time(NULL);
    if (i)
        printf("%d\n", i);
    puts("a");
    return 0;
}

Компилировать и декомпилировать с GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Вывод:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       75 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

Порядок инструкций в памяти не изменился: сначала и, printfа затем putsи retqвозврат.

С участием __builtin_expect

Теперь замените if (i)на:

if (__builtin_expect(i, 0))

и мы получаем:

0000000000000000 <main>:
   0:       48 83 ec 08             sub    $0x8,%rsp
   4:       31 ff                   xor    %edi,%edi
   6:       e8 00 00 00 00          callq  b <main+0xb>
                    7: R_X86_64_PC32        time-0x4
   b:       48 85 c0                test   %rax,%rax
   e:       74 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  15:       e8 00 00 00 00          callq  1a <main+0x1a>
                    16: R_X86_64_PC32       puts-0x4
  1a:       31 c0                   xor    %eax,%eax
  1c:       48 83 c4 08             add    $0x8,%rsp
  20:       c3                      retq
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

printf(Компилируется __printf_chk) был перенесен в самом конце функции, после того, как putsи возвращение , чтобы улучшить предсказание ветвлений , как упоминалось другими ответами.

Так что это в основном так же, как:

int main() {
    int i = !time(NULL);
    if (i)
        goto printf;
puts:
    puts("a");
    return 0;
printf:
    printf("%d\n", i);
    goto puts;
}

Эта оптимизация не была сделана с -O0.

Но удачи в написании примера, который работает быстрее, __builtin_expectчем без, процессоры действительно умны в наши дни . Мои наивные попытки здесь .

С ++ 20 [[likely]]и[[unlikely]]

C ++ 20 стандартизировал эти встроенные функции C ++: как использовать вероятный / маловероятный атрибут C ++ 20 в операторе if-else Они, вероятно, будут (каламбур!) Делать то же самое.

Сиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
источник
71

Это макросы, которые дают подсказки компилятору о том, каким образом может идти ветвь. Макросы расширяются до определенных расширений GCC, если они доступны.

GCC использует их для оптимизации прогнозирования ветвлений. Например, если у вас есть что-то вроде следующего

if (unlikely(x)) {
  dosomething();
}

return x;

Тогда он может реструктурировать этот код так, чтобы он выглядел примерно так:

if (!x) {
  return x;
}

dosomething();
return x;

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

Большинство современных процессоров теперь имеют своего рода предсказание ветвления, но это помогает только тогда, когда вы уже проходили ветвь, а ветвь все еще находится в кеше предсказания ветвления.

Существует ряд других стратегий, которые компилятор и процессор могут использовать в этих сценариях. Вы можете найти более подробную информацию о том, как предсказатели веток работают в Википедии: http://en.wikipedia.org/wiki/Branch_predictor

Dvorak
источник
3
Кроме того, это влияет на объем использования icache - за счет того, что маловероятно, что фрагменты кода будут недоступны.
2015 г.
2
Точнее, он может сделать это с помощью gotos без повторения return x: stackoverflow.com/a/31133787/895245
Чиро Сантилли 郝海东 冠状 病 六四 事件 法轮功
7

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

Например, на процессоре PowerPC неинтифицированная ветвь может занять 16 циклов, правильно намекаемый 8 и неправильно намекаемый 24. В самых внутренних циклах хороший хинтинг может иметь огромное значение.

Портативность на самом деле не проблема - вероятно, определение находится в заголовке для каждой платформы; Вы можете просто определить «вероятный» и «маловероятный» для платформ, которые не поддерживают статические подсказки ветвления.

Лунная тень
источник
3
Для записи, x86 требует дополнительного места для подсказок ветвления. Вы должны иметь однобайтовый префикс для веток, чтобы указать соответствующую подсказку. Согласился, что намеки это хорошая вещь (ТМ), хотя.
Коди Брошиус
2
Dang CISC процессоры и их инструкции переменной длины;)
moonshadow
3
Dang RISC CPU - держитесь подальше от моих 15-байтовых инструкций;)
Cody Brocious
7
@CodyBrocious: подсказка ветки была введена с P4, но была оставлена ​​вместе с P4. Все остальные процессоры x86 просто игнорируют эти префиксы (потому что префиксы всегда игнорируются в тех случаях, когда они бессмысленны). Эти макросы не приводят к тому, что gcc на самом деле генерирует префиксы с подсказками веток в x86. Они помогают вам заставить gcc выложить свою функцию с меньшим количеством занятых веток на ускоренном пути.
Питер Кордес
5
long __builtin_expect(long EXP, long C);

Эта конструкция сообщает компилятору, что выражение EXP, скорее всего, будет иметь значение C. Возвращаемое значение - EXP. __builtin_expect предназначен для использования в условном выражении. Почти во всех случаях он будет использоваться в контексте логических выражений, в этом случае гораздо удобнее определить два вспомогательных макроса:

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

Эти макросы могут быть использованы как в

if (likely(a > 1))

Ссылка: https://www.akkadia.org/drepper/cpumemory.pdf

Ашиш Маурья
источник
1
Как спросили в комментарии к другому ответу - в чем причина двойной инверсии в макросах (т.е. зачем использовать __builtin_expect(!!(expr),0)вместо просто __builtin_expect((expr),0)?
Майкл Ферт
1
@MichaelFirth "двойная инверсия" !!эквивалентна приведению чего-либо к a bool. Некоторые люди любят писать это так.
Бен XO
2

(общий комментарий - другие ответы охватывают детали)

Нет причин, по которым вы должны потерять мобильность, используя их.

У вас всегда есть возможность создания простого «встроенного» макроса с нулевым эффектом, который позволит вам компилировать на других платформах с другими компиляторами.

Вы просто не получите выгоду от оптимизации, если вы находитесь на других платформах.

Эндрю Эджкомб
источник
1
Вы не используете переносимость - платформы, которые их не поддерживают, просто определяют их для расширения до пустых строк.
Sharp
2
Я думаю, что вы на самом деле согласны друг с другом - это просто сбивает с толку. (Судя по всему, комментарий Эндрю гласит: «Вы можете использовать их, не теряя мобильности», но острый зуб подумал, что он сказал: «Не используйте их, поскольку они не переносимы») и возразил.)
Мирал
2

Согласно комментарию Коди , это не имеет ничего общего с Linux, но является подсказкой для компилятора. Что произойдет, будет зависеть от архитектуры и версии компилятора.

Эта особенность в Linux несколько неправильно используется в драйверах. Как указывает osgx в семантике «горячего» атрибута , любая функция hotили coldфункция, вызываемая в блоке, может автоматически намекнуть, что условие является вероятным или нет. Например, dump_stack()помечен, coldтак что это избыточно,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Будущие версии gccмогут выборочно включать функцию, основанную на этих подсказках. Также были предположения, что это не так boolean, но оценка, как в наиболее вероятной и т. Д. Как правило, следует предпочесть использовать какой-то альтернативный механизм, например cold. Нет причин использовать его в любом месте, кроме горячих путей. То, что будет делать компилятор на одной архитектуре, может совершенно отличаться от другой.

бесшумный шум
источник
2

Во многих выпусках Linux вы можете найти complier.h в / usr / linux /, вы можете просто включить его для использования. И другое мнение, вряд ли () является более полезным, чем вероятным (), потому что

if ( likely( ... ) ) {
     doSomething();
}

это может быть оптимизировано также во многих компиляторах.

И, кстати, если вы хотите наблюдать за поведением кода, вы можете сделать следующее:

gcc -c test.c objdump -d test.o> obj.s

Затем откройте obj.s, вы можете найти ответ.

Finaldie
источник
1

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

Изменить: Забыл об одном месте, с которым они действительно могут помочь. Это может позволить компилятору переупорядочить граф потока управления, чтобы уменьшить количество ветвей, взятых для «вероятного» пути. Это может иметь заметное улучшение в циклах, где вы проверяете несколько вариантов выхода.

Коди Броусиус
источник
10
gcc никогда не генерирует подсказки веток x86 - по крайней мере все процессоры Intel будут игнорировать их в любом случае. Тем не менее, он попытается ограничить размер кода в самых неожиданных регионах, избегая встраивания и развертывания цикла.
Алекс странно
1

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

То, как создаются команды ветвления, зависит от архитектуры процессора.

dcgibbons
источник