¿Cuál es la ventaja de __builtin_expect de GCC en las declaraciones if else?

Me encontré con una #defineen la que usan __builtin_expect.

La documentación dice:

Función incorporada: long __builtin_expect (long exp, long c)

Puede usar __builtin_expectpara proporcionar al compilador información de predicción de rama. En general, debe preferir usar comentarios de perfil reales para esto ( -fprofile-arcs), ya que los programadores son notoriamente malos para predecir cómo funcionan realmente sus programas. Sin embargo, hay aplicaciones en las que estos datos son difíciles de recopilar.

El valor de retorno es el valor de exp, que debería ser una expresión integral. La semántica del incorporado es que se espera que eso sea así exp == c. Por ejemplo:

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

indicaría que no esperamos llamar foo, ya que esperamos xser cero.

Entonces, ¿por qué no usar directamente:

if (x)
    foo ();

en lugar de la sintaxis complicada con __builtin_expect?

Imagine el código de ensamblaje que se generaría a partir de:

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

Supongo que debería ser algo como:

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

Puede ver que las instrucciones están organizadas en un orden tal que el barcaso precede al foocaso (a diferencia del código C). Esto puede utilizar mejor la canalización de la CPU, ya que un salto agita las instrucciones ya obtenidas.

Antes de ejecutar el salto, las instrucciones a continuación (el barcaso) se envían a la tubería. Dado que el foocaso es improbable, el salto también es improbable, por lo tanto, es poco probable que golpee la tubería.

Vamos a descompilar para ver qué hace GCC 4.8 con él

Blagovest mencionó la inversión de ramas para mejorar la tubería, pero ¿los compiladores actuales realmente lo hacen? ¡Vamos a averiguar!

Sin __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 y descompile con GCC 4.8.2 x86_64 Linux:

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

Salida:

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

El orden de las instrucciones en la memoria no cambió: primero el putsy luego el retqretorno.

Con __builtin_expect

Ahora reemplace if (i)con:

if (__builtin_expect(i, 0))

y obtenemos:

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>

Se putsmovió al final de la función, ¡el retqregreso!

El nuevo código es básicamente el mismo que:

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

Esta optimización no se realizó con -O0.

Pero buena suerte al escribir un ejemplo que funciona más rápido con __builtin_expectque sin, las CPU son realmente inteligentes en esos días . Mis ingenuos intentos están aquí .

C ++ 20 [[likely]]y[[unlikely]]

C ++ 20 ha estandarizado esas funciones integradas de C ++: Cómo usar el atributo probable / improbable de C ++ 20 en la declaración if-else Probablemente (¡un juego de palabras!) Harán lo mismo.

La idea __builtin_expectes decirle al compilador que generalmente encontrará que la expresión se evalúa como c, para que el compilador pueda optimizar para ese caso.

Supongo que alguien pensó que estaban siendo inteligentes y que estaban acelerando las cosas al hacer esto.

Desafortunadamente, a menos que la situación se entienda muy bien (es probable que no hayan hecho tal cosa), puede haber empeorado las cosas. La documentación incluso dice:

En general, debería preferir usar comentarios de perfil reales para esto ( -fprofile-arcs), ya que los programadores son notoriamente malos para predecir cómo funcionan realmente sus programas. Sin embargo, hay aplicaciones en las que estos datos son difíciles de recopilar.

En general, no debe usar a __builtin_expectmenos que:

• Tienes un problema de rendimiento muy real
• Ya ha optimizado los algoritmos en el sistema adecuadamente
• Tienes datos de rendimiento para respaldar tu afirmación de que un caso particular es el más probable

Bueno, como dice en la descripción, la primera versión agrega un elemento predictivo a la construcción, diciéndole al compilador que la x == 0rama es la más probable, es decir, es la rama que su programa tomará con más frecuencia.

Con eso en mente, el compilador puede optimizar el condicional para que requiera la menor cantidad de trabajo cuando se cumple la condición esperada, a expensas de tal vez tener que hacer más trabajo en caso de una condición inesperada.

Eche un vistazo a cómo se implementan los condicionales durante la fase de compilación, y también en el ensamblaje resultante, para ver cómo una rama puede tener menos trabajo que la otra.

Sin embargo, solo esperaría que esta optimización tenga un efecto notable si el condicional en cuestión es parte de un ciclo interno ajustado que se llama mucho , ya que la diferencia en el código resultante es relativamente pequeña. Y si lo optimiza al revés, bien puede disminuir su rendimiento.

No veo ninguna de las respuestas que aborden la pregunta que creo que estaban haciendo, parafraseada:

¿Hay alguna forma más portátil de insinuar la predicción de ramificación para el compilador?

El título de su pregunta me hizo pensar en hacerlo de esta manera:

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

Si el compilador supone que 'verdadero' es más probable, podría optimizar para no llamar foo().

El problema aquí es que, en general, no sabes lo que asumirá el compilador, por lo que cualquier código que use este tipo de técnica debería medirse cuidadosamente (y posiblemente monitorearse con el tiempo si el contexto cambia).

Lo pruebo en Mac según @Blagovest Buyukliev y @Ciro. Las asambleas se ven claras y agrego comentarios;

Los comandos son gcc -c -O3 -std=gnu11 testOpt.c; otool -tVI testOpt.o

Cuando uso -O3, se ve igual sin importar que el __builtin_expect (i, 0) exista o no.

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

Cuando se compila con -O2, se ve diferente con y sin __builtin_expect (i, 0)

Primero sin

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

Ahora con __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 en el último caso.