Вопрос по linux-kernel, gcc, likely-unlikely, linux – Как работают вероятные / маловероятные макросы в ядре Linux и в чем их выгода?

295

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

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

Связанный: эталон использования__builtin_expect по другому вопросу. YSC
Нет проблем с мобильностью. Вы можете тривиально сделать такие вещи, как#define likely(x) (x) а также#define unlikely(x) (x) на платформах, которые не поддерживают подобные подсказки. David Schwartz
смотрите такжеBOOST_LIKELY Ruggero Turra
Это на самом деле не специфично для ядра Linux или макросов, а для оптимизации компилятора. Должно ли это быть изменено, чтобы отразить это? Cody Brocious
Бумага Что каждый программист должен знать о памяти (стр. 57) содержит подробное объяснение. Torsten Marek

Ваш Ответ

10   ответов
277

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

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

Эти макросы в основном использовались для проверки ошибок. Потому что ошибка оставляет меньше вероятности, чем нормальная работа. Несколько человек делают профилирование или расчет, чтобы выбрать наиболее используемый лист ... gavenkoa
Что касается фрагмента"[...]that it is being run in a tight loop", у многих процессоров есть предсказатель ветки, таким образом, использование этих макросов помогает только при первом выполнении временного кода или когда таблица истории перезаписывается другой ветвью с тем же индексом в таблицу ветвления. В тесном цикле, и, предполагая, что ветвь идет одним путем большую часть времени, предиктор ветвления, скорее всего, начнет угадывать правильную ветвь очень быстро. - твой друг из педантизма. Ross Rogers
@ RossRogers: Что действительно происходит, так это то, что компилятор размещает ветки, поэтому общий случай - это неисполнение. Это быстрее, даже когда предсказание ветвлений работает. Взятые ветви проблематичны для извлечения и декодирования инструкций, даже когда они предсказаны идеально. Некоторые ЦП статически предсказывают ветви, которых нет в их таблице истории, обычно с предположением, что они не приняты для прямых ветвей. Процессоры Intel не работают таким образом: они не пытаются проверить, что запись в таблице предикторов предназначена дляэт ветка, они просто используют это в любом случае. Горячая ветвь и холодная ветвь могут иметь одно и то же имя ... Peter Cordes
Этот ответ в основном устарел, поскольку основное утверждение состоит в том, что он помогает прогнозировать ветвления, и, как указывает @PeterCordes, в большинстве современных аппаратных средств нет неявного или явного статического предсказания ветвлений. Фактически подсказка используется компилятором для оптимизации кода, будь то статические подсказки ветвления или любой другой тип оптимизации. Для большинства современных архитектур важна «любая другая оптимизация», например, создание непрерывных горячих путей, улучшение планирования горячего пути, минимизация размера медленного пути, векторизация только ожидаемого пути и т. Д. И т. Д. BeeOnRope
@ BeeOnRope из-за предварительной выборки в кэш-памяти и размера слова все еще есть преимущество линейного запуска программы. Следующая ячейка памяти будет уже извлечена и помещена в кеш, цель ветвления может быть, а может и нет. С 64-битным процессором вы получаете как минимум 64 бита за раз. В зависимости от чередования DRAM, может быть получено 2x 3x или более битов. Bryce
66

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

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

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

return x;

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

if (!x) {
  return x;
}

dosomething();
return x;

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

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

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

Кроме того, это влияет на использование кода icache - за счет исключения маловероятных фрагментов кода в «горячем пути». fche
Более точно, он может сделать это сgoto без повторенияreturn x: Stackoverflow.com / а / 31133787/895245 Ciro Santilli 新疆改造中心 六四事件 法轮功
60

Давайте декомпилируем, чтобы узнать, что с ним делает 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>

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

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

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

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

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

6

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

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

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

Для записи, x86 требует дополнительного места для подсказок веток. Вы должны иметь однобайтовый префикс для веток, чтобы указать соответствующую подсказку. Согласился, что намеки это хорошая вещь (ТМ), хотя. Cody Brocious
Dang CISC CPU и их инструкции переменной длины;) moonshadow
Dang RISC CPU - держитесь подальше от моих 15-байтовых инструкций;) Cody Brocious
@ CodyBrocious: подсказка ветки была введена с P4, но была оставлена вместе с P4. Все остальные процессоры x86 просто игнорируют эти префиксы (потому что префиксы всегда игнорируются в тех случаях, когда они бессмысленны). Эти макросы Не заставляет gcc на самом деле выдавать префиксы подсказок веток в x86. Они помогают вам заставить gcc выложить свою функцию с меньшим количеством взятых веток на ускоренном пути. Peter Cordes
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.pd

Как спросили в комментарии к другому ответу - в чем причина двойной инверсии в макросах (т.е. зачем использовать__builtin_expect(!!(expr),0) вместо просто__builtin_expect((expr),0)? Michael Firth
2

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

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

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

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

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

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

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

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

2

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

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

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

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

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

Тогда открой obj.s, найди ответ.

1

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

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

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

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

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

Похожие вопросы