В чем преимущество GCC __builtin_expect в 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?

Ответ 1

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

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

Ответ 2

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

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

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

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

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

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

Ответ 3

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

Новый код в основном такой же, как:

int i = !time(NULL);
if (i)
    goto puts;
ret:
return 0;
puts:
puts("a");
goto ret;

Эта оптимизация не была выполнена с помощью -O0.

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

Ответ 4

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

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

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

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

Ответ 5

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

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

Название вашего вопроса заставило меня подумать об этом так:

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

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

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

Ответ 6

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

Встроенная функция: long __builtin_expect (long exp, long c)