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

348

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

término
fuente
77
Esto realmente no es específico del kernel de Linux o de las macros, sino una optimización del compilador. ¿Debería volverse a etiquetar para reflejar eso?
Cody Brocious
11
El documento Lo que todo programador debe saber sobre la memoria (p. 57) contiene una explicación detallada.
Torsten Marek
2
ver tambiénBOOST_LIKELY
Ruggero Turra
44
Relacionado: un punto de referencia sobre el uso de__builtin_expect otra pregunta.
YSC
13
No hay problema de portabilidad. Puede hacer cosas triviales como #define likely(x) (x)y #define unlikely(x) (x)en plataformas que no admiten este tipo de sugerencias.
David Schwartz

Respuestas:

329

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.

1800 INFORMACIÓN
fuente
3
Estas macros se utilizaron principalmente para la comprobación de errores. Porque el error deja menos probablemente que el funcionamiento normal. Algunas personas hacen perfiles o cálculos para decidir la hoja más utilizada ...
gavenkoa
51
Con respecto al fragmento "[...]that it is being run in a tight loop", muchas CPU tienen un predictor de bifurcación , por lo que el uso de estas macros solo ayuda la primera vez que se ejecuta el código o cuando la tabla de historial se sobrescribe con una bifurcación diferente con el mismo índice en la tabla de bifurcación. En un ciclo cerrado, y suponiendo que una rama vaya en una dirección la mayor parte del tiempo, el predictor de ramas probablemente comenzará a adivinar la rama correcta muy rápidamente. - Tu amigo en pedantería.
Ross Rogers
8
@RossRogers: Lo que realmente sucede es que el compilador organiza las ramas para que el caso común sea el no tomado. Esto es más rápido incluso cuando la predicción de rama funciona. Las ramas tomadas son problemáticas para la obtención de instrucciones y la decodificación, incluso cuando se predicen perfectamente. Algunas CPU predicen estáticamente ramas que no están en su tabla de historial, por lo general, suponiendo que no se toman para ramas hacia adelante. Las CPU Intel no funcionan de esa manera: no intentan verificar que la entrada de la tabla de predicción sea para esta rama, solo la usan de todos modos. Una rama caliente y una rama fría podrían alias la misma entrada ...
Peter Cordes
12
Esta respuesta es en su mayoría obsoleta, ya que la afirmación principal es que ayuda a la predicción de bifurcación, y como señala @PeterCordes, en la mayoría del hardware moderno no hay predicción de bifurcación estática implícita o explícita. De hecho, el compilador utiliza la sugerencia para optimizar el código, ya sea que implique sugerencias de rama estática o cualquier otro tipo de optimización. Para la mayoría de las arquitecturas actuales, lo que importa es "cualquier otra optimización", por ejemplo, hacer que las rutas calientes sean contiguas, programar mejor la ruta caliente, minimizar el tamaño de la ruta lenta, vectorizar solo la ruta esperada, etc., etc.
BeeOnRope
3
@BeeOnRope debido a la captación previa de caché y el tamaño de palabra, todavía hay una ventaja de ejecutar un programa linealmente. La siguiente ubicación de memoria ya se buscará y en caché, el destino de la rama tal vez o no. Con una CPU de 64 bits, obtienes al menos 64 bits a la vez. Dependiendo de la intercalación DRAM, puede ser 2x 3x o más bits que se agarran.
Bryce
88

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.

Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
fuente
71

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

dvorak
fuente
3
Además, afecta la huella de icache, al mantener fragmentos de código improbables fuera de la ruta activa.
fche
2
Más precisamente, puede hacerlo con gotos sin repetir el return x: stackoverflow.com/a/31133787/895245
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
7

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.

sombra de Luna
fuente
3
Para el registro, x86 ocupa espacio adicional para sugerencias de rama. Debe tener un prefijo de un byte en las ramas para especificar la sugerencia adecuada. Sin embargo, acordó que insinuar es algo bueno (TM).
Cody Brocious
2
Dang CISC CPUs y sus instrucciones de longitud variable;)
moonshadow
3
CPUs Dang RISC - Manténgase alejado de mis instrucciones de 15 bytes;)
Cody Brocious
77
@CodyBrocious: la sugerencia de rama se introdujo con P4, pero se abandonó junto con P4. Todas las demás CPU x86 simplemente ignoran esos prefijos (porque los prefijos siempre se ignoran en contextos donde no tienen sentido). Estas macros no hacen que gcc emita prefijos de sugerencia de ramificación en x86. Lo ayudan a obtener gcc para diseñar su función con menos ramas tomadas en la ruta rápida.
Peter Cordes
5
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

Ashish Maurya
fuente
1
Como se preguntó en un comentario a otra respuesta: ¿cuál es la razón de la doble inversión en las macros (es decir, ¿por qué usar en __builtin_expect(!!(expr),0)lugar de solo __builtin_expect((expr),0)?)
Michael Firth
1
@MichaelFirth "doble inversión" !!es equivalente a lanzar algo a un bool. A algunas personas les gusta escribirlo de esta manera.
Ben XO
2

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

Andrew Edgecombe
fuente
1
No utiliza la portabilidad: las plataformas que no las admiten solo las definen para expandirse a cadenas vacías.
Sharptooth
2
Creo que ustedes dos realmente están de acuerdo entre sí, es solo una frase confusa. (Por lo que parece, el comentario de Andrew dice "puedes usarlos sin perder portabilidad", pero Sharptooth pensó que dijo "no los uses, ya que no son portátiles" y se opuso.)
Miral
2

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.

ruido sin arte
fuente
2

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.

Finaldie
fuente
1

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.

Cody Brocious
fuente
10
gcc nunca genera sugerencias de ramificación x86: al menos todas las CPU Intel las ignorarían de todos modos. Sin embargo, intentará limitar el tamaño del código en regiones poco probables evitando la inserción y el desenrollado de bucles.
alex extraño
1

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.

dcgibbons
fuente