Я наткнулся на то, #defineв котором их используют __builtin_expect.
В документации говорится:
Встроенная функция:
long __builtin_expect (long exp, long c)Вы можете использовать,
__builtin_expectчтобы предоставить компилятору информацию о предсказании ветвления. В общем, вы должны предпочесть использовать для этого фактическую обратную связь профиля (-fprofile-arcs), поскольку программисты, как известно, плохо предсказывают, как их программы на самом деле работают. Однако есть приложения, в которых сложно собрать эти данные.Возвращаемое значение - это значение
exp, которое должно быть интегральным выражением. Семантика встроенного такова, что это ожидаетсяexp == c. Например:if (__builtin_expect (x, 0)) foo ();будет означать, что мы не ожидаем ответа
foo, поскольку ожидаемxнулевого значения.
Так почему бы не использовать напрямую:
if (x)
foo ();
вместо сложного синтаксиса с __builtin_expect?
if ( x == 0) {} else foo();... или простоif ( x != 0 ) foo();эквивалентным коду из документации GCC.Ответы:
Представьте ассемблерный код, который будет сгенерирован из:
if (__builtin_expect(x, 0)) { foo(); ... } else { bar(); ... }Я думаю, это должно быть что-то вроде:
cmp $x, 0 jne _foo _bar: call bar ... jmp after_if _foo: call foo ... after_if:Вы можете видеть, что инструкции расположены в таком порядке, что
barрегистр предшествуетfoo(в отличие от кода C). Это может лучше использовать конвейер ЦП, так как при переходе выполняются уже выбранные инструкции.Перед выполнением перехода инструкции под ним (
barслучай) передаются в конвейер. Так какfooслучай маловероятен, прыжок тоже маловероятен, следовательно, перебивание конвейера маловероятно.источник
x = 0что столбец дается первым. И foo определяется позже, поскольку его шансы (скорее, вероятность использования) меньше, верно?Давайте декомпилируем, чтобы посмотреть, что с ним делает 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) 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 0a jne 1a <main+0x1a> 10: bf 00 00 00 00 mov $0x0,%edi 11: R_X86_64_32 .rodata.str1.1 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Порядок команд в памяти не изменился: сначала -,
putsа потом -retqreturn.С участием
__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 07 je 17 <main+0x17> 10: 31 c0 xor %eax,%eax 12: 48 83 c4 08 add $0x8,%rsp 16: c3 retq 17: bf 00 00 00 00 mov $0x0,%edi 18: R_X86_64_32 .rodata.str1.1 1c: e8 00 00 00 00 callq 21 <main+0x21> 1d: R_X86_64_PC32 puts-0x4 21: eb ed jmp 10 <main+0x10>В
putsБыл перенесен на самый конец функции, вretqответ!Новый код в основном такой же, как:
int i = !time(NULL); if (i) goto puts; ret: return 0; puts: puts("a"); goto ret;Эта оптимизация не выполнялась с
-O0.Но удачи в написании примера, который работает быстрее,
__builtin_expectчем без него, процессоры в те дни действительно умны . Мои наивные попытки здесь .C ++ 20
[[likely]]и[[unlikely]]C ++ 20 стандартизировал эти встроенные модули C ++: как использовать атрибут «вероятно / маловероятно» в C ++ 20 в выражении if-else. Они, вероятно, (каламбур!) Будут делать то же самое.
источник
Идея
__builtin_expectсостоит в том, чтобы сообщить компилятору, что вы обычно обнаружите, что выражение оценивается как c, чтобы компилятор мог оптимизировать для этого случая.Я предполагаю, что кто-то подумал, что они сообразительны, и этим они ускорили процесс.
К сожалению, если ситуация не будет хорошо изучена (вероятно, они не сделали ничего подобного), это вполне могло усугубить ситуацию. В документации даже сказано:
В общем, вы не должны использовать
__builtin_expectесли:источник
__builtin_expectили нет . С другой стороны, компилятор может выполнять множество оптимизаций на основе вероятности ветвления, таких как организация кода таким образом, чтобы горячий путь был непрерывным, перемещение кода, которое вряд ли будет оптимизировано дальше, или уменьшение его размера, принятие решений о том, какие ветви векторизовать лучше спланировать горячий путь и так далее.Что ж, как говорится в описании, первая версия добавляет в конструкцию прогностический элемент, сообщая компилятору, что
x == 0ветвь является более вероятной, то есть это ветвь, которая будет чаще использоваться вашей программой.Имея это в виду, компилятор может оптимизировать условное выражение так, чтобы он требовал наименьшего объема работы, когда ожидаемое условие выполняется, за счет того, что, возможно, придется выполнять больше работы в случае непредвиденного условия.
Посмотрите, как условные операторы реализуются на этапе компиляции, а также в итоговой сборке, чтобы увидеть, как одна ветвь может быть менее трудоемкой, чем другая.
Тем не менее, я хотел бы только ожидать , что это оптимизация иметь заметный эффект , если условный вопрос является частью жесткой внутренней петли , который получает называется много , так как разница в получаемом коде является относительно небольшой. И если вы оптимизируете его неправильно, вы вполне можете снизить производительность.
источник
compiler design - Aho, Ullmann, Sethi:-)x != 0отрасль является более вероятным один» , я думаю , чтоx==0отрасль, скорее всего , один, потому что он говоритif (__builtin_expect(x, 0)) foo();.. то есть , еслиfoo()будет выполняться только тогда , когдаxэто не0. что означает, чтоifэтоx!=0ветвь is , а неявная ветвьelseisx==0, которая с большей вероятностью будет выполнена, какxожидается0. Обратите внимание, что__builtin_expectвозвращает первый переданный ему аргумент.Я не вижу ответов на вопрос, который, я думаю, вы задавали, перефразируя:
Заголовок вашего вопроса заставил меня задуматься о том, чтобы сделать это так:
if ( !x ) {} else foo();Если компилятор предполагает, что «истина» более вероятна, он может оптимизировать, чтобы не вызывать
foo().Проблема здесь просто в том, что вы, как правило, не знаете, что предположит компилятор, поэтому любой код, использующий такую технику, должен быть тщательно измерен (и, возможно, отслежен с течением времени, если контекст изменится).
источник
elseбыло исключено из текста сообщения.Я тестирую его на Mac согласно @Blagovest Buyukliev и @Ciro. Сборки выглядят четкими, и я добавляю комментарии;
Команды
gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.oКогда я использую -O3 ，, он выглядит одинаково независимо от того, существует __builtin_expect (i, 0) или нет.
testOpt.o: (__TEXT,__text) section _main: 0000000000000000 pushq %rbp 0000000000000001 movq %rsp, %rbp // open function stack 0000000000000004 xorl %edi, %edi // set time args 0 (NULL) 0000000000000006 callq _time // call time(NULL) 000000000000000b testq %rax, %rax // check time(NULL) result 000000000000000e je 0x14 // jump 0x14 if testq result = 0， namely jump to puts 0000000000000010 xorl %eax, %eax // return 0 , return appear first 0000000000000012 popq %rbp // return 0 0000000000000013 retq // return 0 0000000000000014 leaq 0x9(%rip), %rdi ## literal pool for: "a" // puts part, afterwards 000000000000001b callq _puts 0000000000000020 xorl %eax, %eax 0000000000000022 popq %rbp 0000000000000023 retqПри компиляции с -O2 ， он выглядит по-другому с __builtin_expect (i, 0) и без него.
Сначала без
testOpt.o: (__TEXT,__text) section _main: 0000000000000000 pushq %rbp 0000000000000001 movq %rsp, %rbp 0000000000000004 xorl %edi, %edi 0000000000000006 callq _time 000000000000000b testq %rax, %rax 000000000000000e jne 0x1c // jump to 0x1c if not zero, then return 0000000000000010 leaq 0x9(%rip), %rdi ## literal pool for: "a" // put part appear first , following jne 0x1c 0000000000000017 callq _puts 000000000000001c xorl %eax, %eax // return part appear afterwards 000000000000001e popq %rbp 000000000000001f retqТеперь с __builtin_expect (i, 0)
testOpt.o: (__TEXT,__text) section _main: 0000000000000000 pushq %rbp 0000000000000001 movq %rsp, %rbp 0000000000000004 xorl %edi, %edi 0000000000000006 callq _time 000000000000000b testq %rax, %rax 000000000000000e je 0x14 // jump to 0x14 if zero then put. otherwise return 0000000000000010 xorl %eax, %eax // return appear first 0000000000000012 popq %rbp 0000000000000013 retq 0000000000000014 leaq 0x7(%rip), %rdi ## literal pool for: "a" 000000000000001b callq _puts 0000000000000020 jmp 0x10Подводя итог, __builtin_expect работает в последнем случае.
источник
В большинстве случаев вы должны оставить предсказание ветвления как есть, и вам не нужно об этом беспокоиться.
Один из случаев, когда это выгодно, - это алгоритмы, интенсивно использующие процессор, с большим количеством ветвлений. В некоторых случаях скачки могут привести к превышению текущего кэша программы ЦП, заставляя ЦП ждать запуска следующей части программного обеспечения. Выдвигая маловероятные ветви в конце, вы сохраните свою память близко и прыгаете только в маловероятных случаях.
источник