Как работают вероятные / маловероятные макросы в ядре 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)
Я знаю, что они для оптимизации, но как они работают? И насколько можно ожидать снижения производительности / размера от их использования? И стоит ли хлопот (и, вероятно, потери переносимости) хотя бы в коде узкого места (в пользовательском пространстве, конечно).
11 ответов
Они намекают компилятору на выдачу инструкций, которые приведут к предсказанию ветвлений в пользу "вероятной" стороны инструкции перехода. Это может быть большой победой, если прогноз верен, это означает, что инструкция перехода в основном свободна и займет ноль циклов. С другой стороны, если прогноз неверен, то это означает, что конвейер процессора должен быть очищен, и это может стоить несколько циклов. Пока прогноз в большинстве случаев верен, это будет иметь тенденцию быть хорошим для производительности.
Как и во всех подобных оптимизациях производительности, вы должны делать это только после обширного профилирования, чтобы убедиться, что код действительно находится в узком месте, и, возможно, с учетом микро-природы, что он выполняется в узком цикле. Как правило, разработчики 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 i = !time(NULL);
if (i)
goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;
Эта оптимизация не была сделана с -O0,
Но удачи в написании примера, который работает быстрее с __builtin_expect чем без, процессоры действительно умные в те дни. Мои наивные попытки здесь.
Это макросы, которые дают подсказки компилятору о том, каким образом может идти ветвь. Макросы расширяются до определенных расширений 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))
(общий комментарий - другие ответы охватывают детали)
Нет причин, по которым вы должны потерять мобильность, используя их.
У вас всегда есть возможность создания простого "встроенного" макроса с нулевым эффектом, который позволит вам компилировать на других платформах с другими компиляторами.
Вы просто не получите выгоду от оптимизации, если вы находитесь на других платформах.
Во многих выпусках linux вы можете найти complier.h в /usr/linux/, вы можете просто включить его для использования. И другое мнение, вряд ли () является более полезным, чем вероятным (), потому что
if ( likely( ... ) ) {
doSomething();
}
это может быть оптимизировано также во многих компиляторах.
И, кстати, если вы хотите наблюдать за поведением кода в деталях, вы можете сделать следующее:
gcc -c test.c objdump -d test.o> obj.s
Затем откройте obj.s, вы можете найти ответ.
Согласно комментарию Cody Brocious, это не имеет ничего общего с Linux, но является подсказкой для компилятора. Что произойдет, будет зависеть от архитектуры и версии компилятора.
Эта особенность в Linux несколько неправильно используется в драйверах. Как указывает osgx в семантике горячего атрибута, любой hot или же cold Функция, вызываемая в блоке, может автоматически намекать, что условие вероятно или нет. Например, dump_stack() отмечен cold так что это избыточно,
if(unlikely(err)) {
printk("Driver error found. %d\n", err);
dump_stack();
}
Будущие версии gcc может выборочно встроить функцию на основе этих советов. Также были предположения, что это не boolean, но оценка, как в наиболее вероятном и т. д. Как правило, предпочтительнее использовать какой-либо альтернативный механизм, например cold, Нет причин использовать его в любом месте, кроме горячих путей. То, что будет делать компилятор на одной архитектуре, может совершенно отличаться от другой.
Это подсказки компилятору для генерации префиксов подсказок в ветвях. На x86/x64 они занимают один байт, поэтому вы получите не более одного байта для каждой ветви. Что касается производительности, то она полностью зависит от приложения - в большинстве случаев предсказатель ветвления на процессоре в наши дни их игнорирует.
Изменить: Забыл об одном месте, с которым они действительно могут помочь. Это может позволить компилятору переупорядочить граф потока управления, чтобы уменьшить количество ветвей, взятых для "вероятного" пути. Это может иметь заметное улучшение в циклах, где вы проверяете несколько вариантов выхода.
Это функции GCC для программиста, которые дают подсказку компилятору о том, какое наиболее вероятное условие ветвления будет в данном выражении. Это позволяет компилятору строить инструкции ветвления так, чтобы в наиболее распространенном случае выполнялось наименьшее количество команд.
То, как создаются команды ветвления, зависит от архитектуры процессора.
Мне интересно, почему это не определено так:
#define likely(x) __builtin_expect(((x) != 0),1)
#define unlikely(x) __builtin_expect((x),0)
Я имею в виду, что в документах __builtin_expect говорится, что компилятор ожидает, что первый параметр будет иметь значение второго (и возвращается первый параметр), но изначальный способ определения макроса выше затрудняет его использование для вещей, которые могут возвращать не- нулевые значения как «истинные» значения (вместо значения 1).
Это может быть ошибкой, но из моего кода вы понимаете, какое направление я имею в виду.