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

144

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?

kingsmasher1
fuente
2
posible duplicado de macros probables () / improbables () en el kernel de Linux: ¿cómo funcionan? ¿Cuál es su beneficio?
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
3
Creo que su código directo debería haber sido if ( x == 0) {} else foo();... o simplemente lo if ( x != 0 ) foo();que es equivalente al código de la documentación de GCC.
Nawaz

Respuestas:

187

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.

Blagovest Buyukliev
fuente
1
¿Realmente funciona así? ¿Por qué la definición foo no puede venir primero? El orden de las definiciones de funciones es irrelevante, siempre que tenga un prototipo, ¿verdad?
kingsmasher1
63
No se trata de definiciones de funciones. Se trata de reordenar el código de la máquina de una manera que causa una menor probabilidad de que la CPU obtenga instrucciones que no se ejecutarán.
Blagovest Buyukliev
44
Ohh lo entiendo Entonces quiere decir que hay una alta probabilidad de x = 0que la barra se dé primero. Y foo, se define más tarde ya que sus posibilidades (más bien usar la probabilidad) son menores, ¿verdad?
kingsmasher1
1
Ahhh ... gracias. Esa es la mejor explicación. El código de ensamblaje realmente hizo el truco :)
kingsmasher1
55
Esto también puede incrustar consejos para la CPU predictor de saltos , la mejora de la canalización
Hasturkun
50

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.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
1
Consulte la función dispatch_once de libdispatch, que utiliza __builtin_expect para una optimización práctica. El camino lento se ejecuta una sola vez y explota __builtin_expect para insinuar al predictor de rama que se debe tomar el camino rápido. ¡El camino rápido se ejecuta sin usar ningún bloqueo! mikeash.com/pyblog/…
Adam Kaplan
No parece hacer ninguna diferencia en GCC 9.2: gcc.godbolt.org/z/GzP6cx (en realidad, ya en 8.1)
Ruslan
40

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
Michael Kohne
fuente
77
@Michael: Esa no es realmente una descripción de la predicción de rama.
Oliver Charlesworth
3
"la mayoría de los programadores son MALOS" o de todos modos no son mejores que el compilador. Cualquier idiota puede decir que en un bucle for, es probable que la condición de continuación sea cierta, pero el compilador también lo sabe, por lo que no hay ningún beneficio en decirlo. Si por alguna razón escribió un bucle que casi siempre se rompería de inmediato, y si no puede proporcionar datos de perfil al compilador para PGO, entonces tal vez el programador sepa algo que el compilador no sabe.
Steve Jessop
15
En algunas situaciones, no importa qué rama es más probable, sino qué rama importa. Si la rama inesperada conduce a abortar (), entonces la probabilidad no importa, y la rama esperada debería tener prioridad de rendimiento al optimizar.
Neowizard
1
El problema con su reclamo es que las optimizaciones que la CPU puede realizar con respecto a la probabilidad de ramificación están bastante limitadas a una: la predicción de ramificación, y esta optimización ocurre ya sea que la use __builtin_expecto no . Por otro lado, el compilador puede realizar muchas optimizaciones basadas en la probabilidad de ramificación, como organizar el código para que la ruta de acceso sea contigua, mover el código sea poco probable que se optimice más lejos o reducir su tamaño, tomando decisiones sobre qué ramificaciones vectorizar, mejor programación del camino caliente, y así sucesivamente.
BeeOnRope
1
... sin información del desarrollador, es ciego y elige una estrategia neutral. Si el desarrollador tiene razón sobre las probabilidades (y en muchos casos es trivial entender que una rama generalmente se toma / no se toma), obtiene estos beneficios. Si no lo eres, obtienes alguna penalización, pero de alguna manera no es mucho más grande que los beneficios, y lo más crítico, nada de esto anula la predicción de la rama de la CPU.
BeeOnRope
13

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.

Kerrek SB
fuente
Pero al final se trata de verificar la condición por el compilador, ¿quiere decir que el compilador siempre asume esta rama y continúa, y más tarde si no hay una coincidencia entonces? ¿Lo que pasa? Creo que hay algo más sobre esta predicción de rama en el diseño del compilador y cómo funciona.
kingsmasher1
2
Esto es realmente una microoptimización. Mire cómo se implementan los condicionales, hay un pequeño sesgo hacia una rama. Como ejemplo hipotético, suponga que un condicional se convierte en una prueba más un salto en el ensamblaje. Entonces la rama de salto es más lenta que la que no salta, por lo que preferiría hacer que la rama esperada sea la que no salta.
Kerrek SB
Gracias, tu y Michael creo que tienen puntos de vista similares, pero poner en palabras diferentes :-) entiendo el funcionamiento interno del compilador exactas acerca de la prueba y ramas no son posibles de explicar aquí :)
kingsmasher1
También son muy fáciles de aprender buscando en Internet :-)
Kerrek SB
Mejor vuelvo a mi libro de la universidad de compiler design - Aho, Ullmann, Sethi:-)
kingsmasher1
1

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).

Brent Bradburn
fuente
Esto puede haber sido, de hecho, exactamente lo que el OP originalmente tenía la intención de escribir (como lo indica el título), pero por alguna razón el uso de elsequedó fuera del cuerpo de la publicación.
Brent Bradburn
1

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.

Victor Choy
fuente