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

Question

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

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

Answer 2

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

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

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

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

Как правило, вы не должны использовать __builtin_expect, если:

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

Answer 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 return.

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

Answer 4

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

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

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

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

Answer 5

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

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

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

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

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

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