What is likely in linux

What is the difference between likely and unlikely calls in Kernel?

What is the between likely and unlikely calls in Kernel. While searching through the kernel source i found these statements.

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

2 Answers 2

They are compiler hints for GCC. They’re used in conditionals to tell the compiler if a branch is likely to be taken or not. It can help the compiler laying down the code in such a way that’s optimal for the most frequent outcome.

if (likely(some_condition)) < // the compiler will try and make the code layout optimal for the case // where some_condition is true, i.e. where this block is run most_likely_action(); >else < // this block is less frequently used corner_case(); >

It should be used with great care (i.e. based on actual branch profiling results). A wrong hint can degrade performance (obviously).

Some examples of how the code can be optimized are easily found by searching for GCC __builtin_expect . This blog post gcc optimisation: __builtin_expect for example details a disassembly with it.

The kind of optimizations that can be done is very processor-specific. The general idea is that often, processors will run code faster if it does not branch/jump all over the place. The more linear it is, and the more predictable the branches are, the faster it will run. (This is especially true for processors with deep pipelines for example.)

So the compiler will emit the code such that the most likely branch will not involve a jump if that’s what the target CPU prefers, for instance.

Could you please elaborate on the compiler will try and make the code layout optimal for the case? I would like to know how it does that.

added a bit of information on that. there is no general way of optimizing code, it’s all very processor dependent.

Let’s decompile to see what GCC 4.8 does with it

Without 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; >

Compile and decompile with GCC 4.8.2 x86_64 Linux:

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

0000000000000000 : 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b 7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 75 14 jne 24 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 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 2a: R_X86_64_PC32 puts-0x4 2e: 31 c0 xor %eax,%eax 30: 48 83 c4 08 add $0x8,%rsp 34: c3 retq 

The instruction order in memory was unchanged: first the printf and then puts and the retq return.

With expect

0000000000000000 : 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b 7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 74 11 je 21 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 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 31: R_X86_64_PC32 __printf_chk-0x4 35: eb d9 jmp 10

The printf (compiled to __printf_chk ) was moved to the very end of the function, after puts and the return to improve branch prediction as mentioned by other answers.

So it is basically the same as:

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

This optimization was not done with -O0 .

But good luck on writing an example that runs faster with __builtin_expect than without, CPUs are really smart those days. My naive attempts are here.

C++20 [[likely]] and [[unlikely]]

Источник

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

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

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

Всё, разобрался. Код оптимальнее становится. Соответственно, быстрее выполнится.

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

2alexru: спасибо, уже сообразил:)

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

>Соответственно, быстрее выполнится.

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

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

i386 «предсказывает» переходы вполне определённым образом, именно на это и рассчитаны likely/unlikely. Если произойдёт редкий (unlikely) случай, то придётся сбрасывать весь конвейер, а это дорого (особенно на p4). Поэтому как раз эти макросы важны. Не стоит о них так плохо отзываться

А угадывание «частоты результатов» в 96% случаев тривиально, т к в unlikely обычно попадают проверки ошибок

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

>i386 «предсказывает» переходы вполне определённым образом, именно на
>это и рассчитаны likely/unlikely. Если произойдёт редкий (unlikely)
>случай, то придётся сбрасывать весь конвейер, а это дорого (особенно на
> p4). Поэтому как раз эти макросы важны. Не стоит о них так плохо
>отзываться

Во-первых, бывают процессоры не x86(шок!:))
во-вторых, P6 предсказывают ветвления действительно «определенным» образом и этот самый образ не документирован, хотя есть попытки reverse engineering(типа битовых форм).
в-третьих, на Pentium 4(который вы почему-то умудрился обозвать P4, хотя на самом деле он P7) как раз все просто, поскольку на нем действительно есть hint префиксы для ветвления и там использование builtin_expect — достаточно прямолинейно(в теории).
ну а в-четвертых, истории о том, что неправильное предсказание ветвлений — это так уж ужасно и прочие слова про очередь предвыборки или спекулятивное исполнение. ну так возьмите и отпрофилируйте свой код. если он у вас не счетный, то вряд ли вы заметите разницу в 1%, а вот засранный код — это некрасиво.

Это я вам говорю как практик, а не теоретик. 🙂

Re: kernel: чем выгоднее макросы likely/unlikely по сравнению с обычным if?

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

Источник

Как работают макросы likely/unlikely в ядре Linux и в чем их преимущество

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

if (unlikely(fd < 0))

/* некоторый код */

>

Или:

if (likely(!err))

/* некоторый код */

>

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

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

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

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

Ответ 1

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

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

Ответ 2

Давайте проведем декомпиляцию, чтобы посмотреть, что с этим делает GCC 4.8.

Без __builtin_expect

#include «stdio.h»

#include «time.h»

int main()

/* Используйте время, чтобы предотвратить его оптимизацию. */

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 :

0: 48 83 ec 08 sub $0x8,%rsp

4: 31 ff xor %edi,%edi

6: e8 00 00 00 00 callq b

7: R_X86_64_PC32 time-0x4

b: 48 85 c0 test %rax,%rax

e: 75 14 jne 24

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

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

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 :

0: 48 83 ec 08 sub $0x8,%rsp

4: 31 ff xor %edi,%edi

6: e8 00 00 00 00 callq b

7: R_X86_64_PC32 time-0x4

b: 48 85 c0 test %rax,%rax

e: 74 11 je 21

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

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

31: R_X86_64_PC32 __printf_chk-0x4

35: eb d9 jmp 10

Printf (скомпилированный в __printf_chk) был перемещен в самый конец функции, после puts и return, чтобы улучшить предсказание ветвлений, как упоминалось в других ответах. Таким образом, по сути это то же самое, что и:

int main()

int i = !time(NULL);

if (i)

goto printf;

puts:

puts(«a»);

return 0;

printf:

printf(«%d\n», i);

goto puts;

>

Ответ 3

Это макросы, которые дают компилятору подсказки о том, в какую сторону может пойти ветвление. Макросы расширяются до специфических для GCC расширений, если они доступны. GCC использует их для оптимизации предсказания ветвлений. Например, если у вас есть что-то вроде следующего:

if (unlikely(x))

dosomething();

>

return x;

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

if (!x)

return x;

>

dosomething();

return x;

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

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

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

Ответ 4

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

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

Мы будем очень благодарны

если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.

Источник