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

Estuve investigando algunas partes del kernel de Linux y encontré llamadas como esta:

if (unlikely(fd < 0))
{
    /* Do something */
}

o

if (likely(!err))
{
    /* Do something */
}

He encontrado la definición de ellos:

#define likely(x)       __builtin_expect((x),1)
#define unlikely(x)     __builtin_expect((x),0)

Sé que son para la optimización, pero ¿cómo funcionan? ¿Y cuánta disminución de rendimiento / tamaño se puede esperar al usarlos? Y vale la pena la molestia (y perder la portabilidad probablemente) al menos en el código de cuello de botella (en el espacio de usuario, por supuesto).

Indican al compilador que emita instrucciones que harán que la predicción de rama favorezca el lado "probable" de una instrucción de salto. Esto puede ser una gran victoria, si la predicción es correcta, significa que la instrucción de salto es básicamente gratuita y tomará cero ciclos. Por otro lado, si la predicción es incorrecta, significa que la tubería del procesador necesita ser vaciada y puede costar varios ciclos. Mientras la predicción sea correcta la mayor parte del tiempo, esto tenderá a ser bueno para el rendimiento.

Al igual que todas las optimizaciones de rendimiento, solo debe hacerlo después de un extenso perfil para asegurarse de que el código realmente esté en un cuello de botella, y probablemente dada la naturaleza micro, de que se está ejecutando en un circuito cerrado. En general, los desarrolladores de Linux tienen bastante experiencia, así que me imagino que lo habrían hecho. Realmente no les importa demasiado la portabilidad, ya que solo se dirigen a gcc, y tienen una idea muy cercana del ensamblaje que desean que genere.

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

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 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 las instrucciones en la memoria no cambió: primero el printfy luego putsy 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 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 movió al final de la función, después putsy al regreso para mejorar la predicción de rama como se menciona en otras respuestas.

Entonces es básicamente lo mismo que:

int main() {
    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 funciona más rápido con __builtin_expectque sin, las CPU son realmente inteligentes en estos 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.

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

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

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

return x;

Entonces puede reestructurar este código para que sea más parecido a:

if (!x) {
  return x;
}

dosomething();
return x;

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

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

Existen otras estrategias que el compilador y el procesador pueden usar en estos escenarios. Puede encontrar más detalles sobre cómo funcionan los predictores de rama en Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Causan que el compilador emita las sugerencias de rama apropiadas donde el hardware las admite. Esto generalmente solo significa girar algunos bits en el código de operación de la instrucción, por lo que el tamaño del código no cambiará. La CPU comenzará a buscar instrucciones desde la ubicación predicha, y enjuagará la tubería y comenzará de nuevo si eso resulta ser incorrecto cuando se alcanza la rama; en el caso de que la pista sea correcta, esto hará que la rama sea mucho más rápida, precisamente cuánto más rápido dependerá del hardware; y cuánto afectará esto al rendimiento del código dependerá de qué proporción de la sugerencia de tiempo sea correcta.

Por ejemplo, en una CPU PowerPC, una rama no sugerida puede tomar 16 ciclos, una pista correcta 8 y una pista incorrecta 24. En los bucles más internos, una buena sugerencia puede marcar una gran 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 las plataformas que no admiten sugerencias de rama estática.

long __builtin_expect(long EXP, long C);

Esta construcción le dice al compilador que la expresión EXP probablemente tendrá el valor C. El valor de retorno es EXP. __builtin_expect está destinado a ser utilizado en una expresión condicional. En casi todos los casos se utilizará en el contexto de expresiones booleanas, en cuyo caso es mucho más conveniente definir dos macros auxiliares:

#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

(comentario general - otras respuestas cubren los detalles)

No hay razón para perder la portabilidad al usarlos.

Siempre tiene la opción de crear una macro "en línea" o macro de efecto nulo simple 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, pero es una pista para el compilador. Lo que ocurra dependerá de la arquitectura y la versión del compilador.

Esta característica particular en Linux es algo mal utilizada en los controladores. Como osgx señala en la semántica del atributo activo , cualquier función hoto coldllamada con un bloque puede indicar automáticamente que la condición es probable o no. Por ejemplo, dump_stack()está marcado coldpor lo que esto es redundante,

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

Las versiones futuras de gccpueden en línea selectivamente una función basada en estos consejos. También ha habido sugerencias de que no lo es boolean, pero una puntuación como es muy probable , etc. En general, debería preferirse utilizar algún mecanismo alternativo como cold. No hay ninguna razón para usarlo en ningún lugar que no sean caminos calientes. Lo que hará un compilador 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, improbable () es más útil que probable (), 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 lo siguiente:

gcc -c test.c objdump -d test.o> obj.s

Luego, abre obj.s, puedes encontrar la respuesta.

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

Editar: Olvidé un lugar en el que realmente pueden ayudar. Puede permitir que el compilador reordene el gráfico de flujo de control para reducir el número de ramificaciones tomadas para la ruta 'probable'. Esto puede tener una mejora notable en los bucles en los que está comprobando múltiples casos de salida.

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

Cómo se construyen las instrucciones de bifurcación depende de la arquitectura del procesador.