Qual é a vantagem do __builtin_expect do GCC nas declarações if else?

Me deparei com um #define em que eles usam __builtin_expect.

A documentação diz:

Função interna: long __builtin_expect (long exp, long c)

Você pode usar __builtin_expectpara fornecer ao compilador informações de previsão de ramificação. Em geral, você deve preferir usar o feedback real do perfil para isso (-fprofile-arcs ), pois os programadores são notoriamente ruins em prever o desempenho de seus programas. No entanto, existem aplicativos em que esses dados são difíceis de coletar.

O valor de retorno é o valor de exp, que deve ser uma expressão integral. A semântica do built-in é que é esperado isso exp == c. Por exemplo:

      if (__builtin_expect (x, 0))
        foo ();

indicaria que não esperamos ligar foo, pois esperamos xser zero.

Então, por que não usar diretamente:

if (x)
    foo ();

em vez da sintaxe complicada com __builtin_expect?

Imagine o código do assembly que seria gerado a partir de:

if (__builtin_expect(x, 0)) {
    foo();
    ...
} else {
    bar();
    ...
}

Eu acho que deveria ser algo como:

  cmp   $x, 0
  jne   _foo
_bar:
  call  bar
  ...
  jmp   after_if
_foo:
  call  foo
  ...
after_if:

Você pode ver que as instruções estão dispostas em uma ordem que o barcaso precede ofoo caso (em oposição ao código C). Isso pode utilizar melhor o pipeline da CPU, pois um salto frustra as instruções já obtidas.

Antes do salto ser executado, as instruções abaixo (o barcaso) são enviadas ao pipeline. Como o foocaso é improvável, saltar também é improvável; portanto, é improvável que tropeçar no pipeline.

Vamos descompilar para ver o que o GCC 4.8 faz com ele

Blagovest mencionou a inversão de ramificação para melhorar o pipeline, mas os compiladores atuais realmente o fazem? Vamos descobrir!

Sem __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;
}

Compile e descompile com o GCC 4.8.2 x86_64 Linux:

gcc -c -O3 -std=gnu11 main.c
objdump -dr main.o

Resultado:

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

A ordem das instruções na memória permaneceu inalterada: primeiro o putse depois retqretornamos.

Com __builtin_expect

Agora substitua if (i)por:

if (__builtin_expect(i, 0))

e temos:

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>

O putsfoi movido para o final da função, o retqretorno!

O novo código é basicamente o mesmo que:

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

Essa otimização não foi concluída -O0.

Mas boa sorte em escrever um exemplo que seja mais rápido do __builtin_expectque sem, as CPUs são realmente inteligentes naqueles dias . Minhas tentativas ingênuas estão aqui .

C ++ 20 [[likely]]e[[unlikely]]

O C ++ 20 padronizou os recursos internos do C ++: Como usar o atributo provável / improvável do C ++ 20 na instrução if-else Eles provavelmente (um trocadilho!) Farão a mesma coisa.

A idéia de __builtin_expecté informar ao compilador que você normalmente descobrirá que a expressão é avaliada como c, para que o compilador possa otimizar para esse caso.

Eu acho que alguém pensou que eles estavam sendo espertos e que eles estavam acelerando as coisas fazendo isso.

Infelizmente, a menos que a situação seja muito bem compreendida (é provável que eles não tenham feito isso), pode ter piorado as coisas. A documentação ainda diz:

Em geral, você deve preferir usar o feedback real do perfil para isso ( -fprofile-arcs), pois os programadores são notoriamente ruins em prever o desempenho de seus programas. No entanto, existem aplicativos em que esses dados são difíceis de coletar.

Em geral, você não deve usar a __builtin_expectmenos que:

• Você tem um problema de desempenho muito real
• Você já otimizou os algoritmos no sistema adequadamente
• Você tem dados de desempenho para fazer backup de sua afirmação de que um caso específico é o mais provável

Bem, como diz a descrição, a primeira versão adiciona um elemento preditivo à construção, dizendo ao compilador que o x == 0 ramo é o mais provável - ou seja, é o ramo que será utilizado com mais frequência pelo seu programa.

Com isso em mente, o compilador pode otimizar o condicional para que exija a menor quantidade de trabalho quando a condição esperada for mantida, às custas de talvez ter que fazer mais trabalho em caso de condição inesperada.

Veja como os condicionais são implementados durante a fase de compilação e também no assembly resultante, para ver como um ramo pode ser menos trabalhoso que o outro.

No entanto, eu esperaria que essa otimização tivesse um efeito perceptível se o condicional em questão fizer parte de um loop interno apertado que é chamado muito , pois a diferença no código resultante é relativamente pequena. E se você otimizá-lo da maneira errada, poderá diminuir seu desempenho.

Não vejo nenhuma das respostas abordando a pergunta que acho que você estava fazendo, parafraseada:

Existe uma maneira mais portátil de sugerir a previsão de ramificação para o compilador.

O título da sua pergunta me fez pensar dessa maneira:

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

Se o compilador assumir que 'true' é mais provável, ele poderá otimizar para não chamar foo().

O problema aqui é que, em geral, você não sabe o que o compilador assumirá - portanto, qualquer código que use esse tipo de técnica precisará ser cuidadosamente medido (e possivelmente monitorado ao longo do tempo, se o contexto mudar).

Eu testo no Mac de acordo com @Blagovest Buyukliev e @Ciro. As assembléias parecem claras e eu adiciono comentários;

Os comandos são gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Quando eu uso -O3, parece o mesmo, independentemente de o __builtin_expect (i, 0) existir ou não.

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

Ao compilar com -O2, parece diferente com e sem __builtin_expect (i, 0)

Primeiro sem

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

Agora com __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

Para resumir, __builtin_expect funciona no último caso.