¿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 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 probablemente perder la portabilidad) al menos en el código de cuello de botella (en el espacio de usuario, por supuesto).

Son una sugerencia para que el compilador emita instrucciones que harán que la predicción de bifurcación 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 debe vaciarse y puede costar varios ciclos. Siempre que 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 de este tipo, solo debe hacerlo después de un perfilado exhaustivo para asegurarse de que el código realmente se encuentre en un cuello de botella, y probablemente dada la naturaleza micro, que se está ejecutando en un ciclo 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 apuntan a gcc, y tienen una idea muy cercana del ensamblado que quieren 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;
}

Compilar y descompilar con GCC 4.8.2 x86_64 Linux:

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

Producción:

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 printf y luego puts y el retq devolver.

Con __builtin_expect

Ahora reemplaza 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 para __printf_chk) se movió al final de la función, después de puts y el retorno para mejorar la predicción de sucursales 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 hizo con -O0.

Pero buena suerte al escribir un ejemplo que se ejecute más rápido con __builtin_expect que 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 esos elementos integrados de C ++: cómo usar el atributo probable/improbable de C ++ 20 en la declaración if-else Es probable (¡un juego de palabras!) que hagan lo mismo.

Estas son macros que dan pistas al compilador sobre el camino que puede tomar 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 bifurcaciones. Por ejemplo, si tienes 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 bifurcación por primera vez, hay una sobrecarga significativa, porque puede haber estado cargando y ejecutando código especulativamente más adelante. Cuando determina que tomará la rama, entonces tiene que 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 ha pasado por la bifurcación antes, y la bifurcación todavía está en el caché de predicción de bifurcación.

Hay una serie de 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

Hacen que el compilador emita las sugerencias de rama apropiadas donde el hardware las admite. Por lo general, esto solo significa cambiar 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, vaciará la tubería y comenzará de nuevo si eso resulta ser incorrecto cuando se alcanza la rama; en el caso de que la sugerencia 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 afecta esto al rendimiento del código dependerá de la proporción de la sugerencia de tiempo que sea correcta.

Por ejemplo, en una CPU PowerPC, una rama no sugerida puede tomar 16 ciclos, una sugerida correctamente 8 y una sugerida incorrectamente 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 se encuentra 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 devuelto es EXP.
__builtin_expect está destinado a ser utilizado en una expresión condicional. En casi todos los casos se usará 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

(comentario general – otras respuestas cubren los detalles)

No hay ninguna razón por la que deba perder la portabilidad al usarlos.

Siempre tiene la opción de crear un simple “en línea” o macro de efecto nulo 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 suceda dependerá de la arquitectura y la versión del compilador.

Esta característica particular en Linux se usa un poco mal en los controladores. Como señala osgx en la semántica del atributo caliente, cualquier hot o cold La función llamada dentro de un bloque puede insinuar automáticamente que la condición es probable o no. Por ejemplo, dump_stack() está marcado cold así que esto es redundante,

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

Futuras versiones de gcc puede alinear selectivamente una función basada en estas sugerencias. También ha habido sugerencias de que no es booleanpero una puntuación como en más probableetc. En general, se debe preferir utilizar algún mecanismo alternativo como cold. No hay 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.