¿Cómo funcionan las macros probables/improbables en el kernel de Linux y cuál es su beneficio?

Estas son macros que dan pistas al compilador sobre qué camino puede tomar una rama. Las macros se expanden a extensiones específicas de GCC, si están disponibles.

GCC utiliza estos para optimizar la predicción de ramas. Por ejemplo, si tiene algo como lo siguiente

if (unlikely(x)) {
  dosomething();
}

return x;

Entonces puede reestructurar este código para que sea algo más como:

if (!x) {
  return x;
}

dosomething();
return x;

El beneficio de esto es que cuando el procesador toma una rama la primera vez, hay una sobrecarga significativa, porque puede haber sido especulativamente cargando y ejecutando código más adelante. Cuando determina que tomará la rama, entonces tiene que invalidar eso, y comenzar en el destino de la rama.

La mayoría de los procesadores modernos ahora tienen algún tipo de predicción de rama, pero eso solo ayuda cuando has pasado por la rama antes, y la rama todavía está en la caché de predicción de rama.

Hay una serie de otras estrategias que el compilador y el procesador pueden usar en estos escenarios. Puedes encuentra más detalles sobre cómo predictores de rama en Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

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

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)
        printf("%d\n", i);
    puts("a");
    return 0;
}

Compilar y descompilar 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 14                   jne    24 <main+0x24>
  10:       ba 01 00 00 00          mov    $0x1,%edx
  15:       be 00 00 00 00          mov    $0x0,%esi
                    16: R_X86_64_32 .rodata.str1.1
  1a:       bf 01 00 00 00          mov    $0x1,%edi
  1f:       e8 00 00 00 00          callq  24 <main+0x24>
                    20: R_X86_64_PC32       __printf_chk-0x4
  24:       bf 00 00 00 00          mov    $0x0,%edi
                    25: R_X86_64_32 .rodata.str1.1+0x4
  29:       e8 00 00 00 00          callq  2e <main+0x2e>
                    2a: R_X86_64_PC32       puts-0x4
  2e:       31 c0                   xor    %eax,%eax
  30:       48 83 c4 08             add    $0x8,%rsp
  34:       c3                      retq

El orden de instrucción en la memoria no cambió: primero el printf y luego el puts y el retq.

Con __builtin_expect

Ahora sustitúyase if (i) por:

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 11                   je     21 <main+0x21>
  10:       bf 00 00 00 00          mov    $0x0,%edi
                    11: R_X86_64_32 .rodata.str1.1+0x4
  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
  21:       ba 01 00 00 00          mov    $0x1,%edx
  26:       be 00 00 00 00          mov    $0x0,%esi
                    27: R_X86_64_32 .rodata.str1.1
  2b:       bf 01 00 00 00          mov    $0x1,%edi
  30:       e8 00 00 00 00          callq  35 <main+0x35>
                    31: R_X86_64_PC32       __printf_chk-0x4
  35:       eb d9                   jmp    10 <main+0x10>

El printf (compilado a __printf_chk) se trasladó a el final de la función, después de puts y el retorno para mejorar la predicción de ramas como se menciona en otras respuestas.

Así que es básicamente lo mismo que:

int i = !time(NULL);
if (i)
    goto printf;
puts:
puts("a");
return 0;
printf:
printf("%d\n", i);
goto puts;

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

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

Hacen que el compilador emita las sugerencias de rama apropiadas donde el hardware las soporta. Esto generalmente solo significa girar unos pocos bits en el opcode de instrucción, por lo que el tamaño del código no cambiará. La CPU comenzará a buscar instrucciones desde la ubicación prevista, y limpiará la canalización y comenzará de nuevo si eso resulta ser incorrecto cuando se alcance la rama; en el caso en que la sugerencia sea correcta, esto hará que la rama sea mucho más rápida-precisamente, cuánto más rápido dependerá de la hardware; y cuánto esto afecta el rendimiento del código dependerá de qué proporción de la pista de tiempo es correcta.

Por ejemplo, en una CPU PowerPC una rama no interrumpida puede tomar 16 ciclos, una correctamente insinuada 8 y una incorrectamente insinuada 24. En los bucles más internos, una buena insinuación puede hacer una enorme diferencia.

La portabilidad no es realmente un problema-presumiblemente la definición está en un encabezado por plataforma; simplemente puede definir "probable" e "improbable" a nada para plataformas que no admiten sugerencias de ramas estáticas.

long __builtin_expect(long EXP, long C);

Esta construcción le dice al compilador que la expresión EXP lo más probable es que tenga el valor C. El valor devuelto es EXP. _ _ builtin _ expect está destinado a ser utilizado en un condicional expresion. En casi todos los casos se utilizará en el contexto de las expresiones booleanas en cuyo caso es mucho más conveniente para definir dos macros de ayuda:

#define unlikely(expr) __builtin_expect(!!(expr), 0)
#define likely(expr) __builtin_expect(!!(expr), 1)

Estas macros se pueden usar como en

if (likely(a > 1))

Referencia: https://www.akkadia.org/drepper/cpumemory.pdf

(observación general-otras respuestas abarcan los detalles)

No hay razón para que pierdas la portabilidad al usarlos.

Siempre tiene la opción de crear un simple efecto nil "inline" o macro que le permitirá compilar en otras plataformas con otros compiladores.

Simplemente no obtendrá el beneficio de la optimización si está en otras plataformas.

Según el comentario de Cody, esto no tiene nada que ver con Linux, sino que es una pista para el compilador. Lo que suceda dependerá de la arquitectura y la versión del compilador.

Esta característica particular en Linux es un poco mal utilizada en los controladores. Como osgx señala en la semántica del atributo hot , cualquier función hot o cold llamada con en un bloque puede indicar automáticamente que la condición es probable o no. Por ejemplo, {[3] } está marcado cold así que esto es redundante,

 if(unlikely(err)) {
     printk("Driver error found. %d\n", err);
     dump_stack();
 }

Las futuras versiones de gcc pueden insertar selectivamente una función basada en estas sugerencias. También ha habido sugerencias de que no es boolean, sino una puntuación como en lo más probable, etc. En general, se debe preferir utilizar algún mecanismo alternativo como cold. No hay razón para usarlo en ningún lugar excepto en hot paths. Lo que un compilador hará en una arquitectura puede ser completamente diferente en otra.

En muchas versiones de Linux, puede encontrar complier.h en/usr / linux/, puede incluirlo para usarlo simplemente. Y otra opinión, unlikely() es más útil que likely(), porque

if ( likely( ... ) ) {
     doSomething();
}

También se puede optimizar en muchos compiladores.

Y por cierto, si desea observar el comportamiento detallado del código, puede hacer simplemente lo siguiente:

Prueba Gcc-c.c prueba objdump-d.o > obj.s

Entonces, abra obj.s, puedes encontrar la respuesta.

Son pistas al compilador para generar los prefijos de pistas en las ramas. En x86 / x64, ocupan un byte, por lo que obtendrá como máximo un aumento de un byte para cada rama. En cuanto al rendimiento, depende completamente de la aplicación these en la mayoría de los casos, el predictor de rama en el procesador los ignorará, en estos días.

Editar: Se olvidó de un lugar en el que realmente pueden ayudar. Puede permitir que el compilador reordene el gráfico de control-flujo para reducir el número de ramas tomadas para el camino "probable". Esto puede tener una marcada mejora en los bucles donde está comprobando múltiples casos de salida.

Estas son funciones GCC para que el programador le dé una pista al compilador sobre cuál será la condición de rama más probable en una expresión dada. Esto permite al compilador compilar las instrucciones de la rama para que el caso más común tome el menor número de instrucciones para ejecutar.

La forma en que se construyen las instrucciones de la rama depende de la arquitectura del procesador.