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

Я копался в некоторых частях ядра 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)

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

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

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

Давайте декомпилируем, чтобы увидеть, что 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 Они, вероятно, будут (каламбур!) Делать то же самое.

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

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

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

return x;

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

if (!x) {
  return x;
}

dosomething();
return x;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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