В чем преимущество __builtin_expect от GCC в операторах if else?

Я наткнулся на #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?

Источник

5 ответов

Решение

Представьте код сборки, который будет сгенерирован из:

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

Источник

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

Источник

Идея __builtin_expect это сказать компилятору, что вы обычно обнаружите, что выражение оценивается как c, так что компилятор может оптимизировать для этого случая.

Я предполагаю, что кто-то думал, что они были умны и что они ускоряли вещи, делая это.

К сожалению, если ситуация не очень хорошо понята (вероятно, они не сделали ничего подобного), это, возможно, усугубило ситуацию. В документации даже сказано:

В целом, вы должны предпочесть использовать реальный профиль обратной связи для этого (-fprofile-arcs), поскольку программисты, как известно, плохо предсказывают, как на самом деле работают их программы. Однако есть приложения, в которых эти данные трудно собрать.

В общем, вы не должны использовать __builtin_expect если:

  • У вас очень реальная проблема с производительностью
  • Вы уже оптимизировали алгоритмы в системе соответствующим образом
  • У вас есть данные о производительности для подтверждения вашего утверждения о том, что конкретный случай является наиболее вероятным
Источник

Ну, как говорится в описании, первая версия добавляет элемент предсказания в конструкцию, сообщая компилятору, что x == 0 вероятнее всего, это ветвь, то есть ваша ветвь будет чаще использоваться ветвью.

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

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

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

Источник

Я не вижу ни одного ответа на вопрос, который, по-моему, вы задавали, перефразируя:

Есть ли более переносимый способ подсказки ветвления для компилятора.

Название вашего вопроса заставило меня задуматься о том, чтобы сделать это следующим образом:

if ( !x ) {} else foo();

Если компилятор предполагает, что "true" более вероятно, он может оптимизировать, чтобы не вызывать foo(),

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

Источник

Я тестирую его на 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 работает в последнем случае.

Источник

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

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

Источник
Другие вопросы по тегам