¿Cómo funcionan las macros probables/improbables en el kernel de Linux y cuál es su beneficio?
https://stackoverflow.com/questions/109710
-
02-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
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 */
}
Encontré 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 molestarse (y probablemente perder la portabilidad) al menos en el código de cuello de botella (en el espacio de usuario, por supuesto)?
Solución
Son una pista 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 ganancia, si la predicción es correcta significa que la instrucción de salto es básicamente gratuita y no tomará ningún ciclo.Por otro lado, si la predicción es incorrecta, significa que es necesario vaciar la tubería del procesador y esto puede costar varios ciclos.Siempre que la predicción sea correcta la mayor parte del tiempo, esto tenderá a ser bueno para el rendimiento.
Como todas las optimizaciones de rendimiento de este tipo, solo debe hacerlo después de una elaboración de perfiles exhaustiva para garantizar que el código realmente se encuentre en un cuello de botella y, probablemente, dada la micronaturaleza, que se esté ejecutando en un circuito cerrado.Generalmente 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 ensamblaje que quieren que genere.
Otros consejos
Estas son macros que 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 ramas.Por ejemplo, si tiene algo como lo siguiente
if (unlikely(x)) {
dosomething();
}
return x;
Luego puede reestructurar este código para que sea algo más parecido a:
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 de manera especulativa más adelante.Cuando determina que tomará la rama, debe invalidarla y comenzar en el objetivo 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 ya has pasado por la rama antes y la rama todavía está en el caché de predicción de rama.
Hay otras estrategias que el compilador y el procesador pueden utilizar en estos escenarios.Puede encontrar más detalles sobre cómo funcionan los predictores de ramas en Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor
Descompilemos 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
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 se modificó: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 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 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 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í.
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 prevista, limpiará la tubería y comenzará de nuevo si eso resulta incorrecto cuando se alcance la rama;en el caso de que la sugerencia sea correcta, esto hará que la rama sea mucho más rápida; exactamente 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 sin sugerencias puede tardar 16 ciclos, una con sugerencias correctas 8 y una con sugerencias incorrectas 24.En los bucles más internos, unas buenas sugerencias pueden marcar 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" como nada para plataformas que no admiten sugerencias de rama estáticas.
long __builtin_expect(long EXP, long C);
Este constructo le dice al compilador que la expresión exp Es muy probable que tenga el valor C.El valor de retorno es EXP.__integrado_esperar está destinado a usarse 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 utilizar como en
if (likely(a > 1))
Referencia: https://www.akkadia.org/drepper/cpumemory.pdf
(comentario general: otras respuestas cubren los detalles)
No hay ninguna razón por la que debas perder la portabilidad al usarlos.
Siempre tienes la opción de crear una macro o "en línea" simple de efecto nulo que te permitirá compilar en otras plataformas con otros compiladores.
Simplemente no obtendrás el beneficio de la optimización si estás 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 algo mal en los controladores.Como osgx señala en semántica del atributo caliente, cualquier hot o cold La función llamada en un bloque puede insinuar automáticamente que la condición es probable o no.Por ejemplo, dump_stack() está marcado cold entonces esto es redundante,
if(unlikely(err)) {
printk("Driver error found. %d\n", err);
dump_stack();
}
Versiones futuras de gcc puede incorporar selectivamente una función basándose en estas sugerencias.También ha habido sugerencias de que no es boolean, pero una puntuación como en más probable, etc.Generalmente, debería preferirse utilizar algún mecanismo alternativo como cold.No hay razón para usarlo en ningún lugar excepto en caminos calurosos.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 simplemente lo siguiente:
gcc -c test.c objdump -d test.o> obj.s
Luego, abra obj.s, podrá encontrar la respuesta.
Son sugerencias para que el compilador genere prefijos de sugerencias en las ramas.En x86/x64, ocupan un byte, por lo que obtendrás como máximo un aumento de un byte 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 la cantidad de ramas tomadas para la ruta "probable".Esto puede tener una marcada mejora en los bucles en los que se verifican 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 bifurcación más probable en una expresión determinada.Esto permite al compilador crear las instrucciones de rama de modo que el caso más común requiera la menor cantidad de instrucciones para ejecutarse.
La forma en que se construyen las instrucciones de bifurcación depende de la arquitectura del procesador.
