¿Cómo funcionan las posibles () y poco probables () macros 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 */ } 

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ánto se puede esperar una disminución de rendimiento / tamaño 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 comstackdor que 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 enjuagarse 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 estas optimizaciones de rendimiento, solo debe hacerlo después de un perfil exhaustivo para garantizar que el código realmente se encuentre en un cuello de botella, y probablemente teniendo en cuenta la naturaleza micro, esté funcionando en un circuito cerrado. En general, los desarrolladores de Linux tienen mucha experiencia, así que me imagino que lo habrían hecho. Realmente no les importa demasiado la portabilidad ya que solo se enfocan en gcc, y tienen una idea muy cercana del ensamblaje que quieren que genere.

Estas son macros que dan pistas al comstackdor sobre la forma en que puede ir una twig. Las macros se expanden a las extensiones específicas de GCC, si están disponibles.

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

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

Entonces puede reestructurar este código para que sea algo así como:

 if (!x) { return x; } dosomething(); return x; 

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

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

Hay una serie de otras estrategias que el comstackdor y el procesador pueden usar en estos escenarios. Puede encontrar más detalles sobre cómo pronosticar twigs en Wikipedia: http://en.wikipedia.org/wiki/Branch_predictor

Vamos a descomstackr 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; } 

Comstack y descomstack con GCC 4.8.2 x86_64 Linux:

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

Salida:

 0000000000000000 
: 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b
7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 75 14 jne 24
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
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
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 printf y luego puts y retq retorno.

Con __builtin_expect

Ahora reemplace if (i) con:

 if (__builtin_expect(i, 0)) 

y obtenemos:

 0000000000000000 
: 0: 48 83 ec 08 sub $0x8,%rsp 4: 31 ff xor %edi,%edi 6: e8 00 00 00 00 callq b
7: R_X86_64_PC32 time-0x4 b: 48 85 c0 test %rax,%rax e: 74 11 je 21
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
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
31: R_X86_64_PC32 __printf_chk-0x4 35: eb d9 jmp 10

El printf (comstackdo en __printf_chk ) se movió al final de la función, después de puts y el retorno para mejorar la predicción de bifurcación como se menciona en otras respuestas.

Por lo tanto, 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 ingenuos bashs están aquí .

Hacen que el comstackdor emita las sugerencias de bifurcación apropiadas donde el hardware las admite. Esto generalmente solo significa mezclar 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 las instrucciones desde la ubicación pronosticada, y purgará la tubería y volverá a comenzar si resulta ser incorrecta cuando se alcanza la bifurcación; en el caso donde la sugerencia es correcta, esto hará que la derivación sea mucho más rápida; con precisión, cuánto más rápido dependerá del hardware; y cuánto afecta esto al rendimiento del código dependerá de qué proporción del tiempo sea correcta.

Por ejemplo, en una CPU PowerPC, una bifurcación sin pintar puede tomar 16 ciclos, una correctamente insinuada una 8 y una incorrectamente insinuada 24. En bucles más internos, una buena alusión 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” para las plataformas que no son compatibles con las sugerencias de la twig estática.

 long __builtin_expect(long EXP, long C); 

Esta construcción le dice al comstackdor que la expresión EXP muy probablemente tendrá el valor C. El valor de retorno es EXP. __builtin_pect está destinado a ser usado 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 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

(comentario general – otras respuestas cubren los detalles)

No hay ninguna razón por la cual deba perder portabilidad usándolos.

Siempre tiene la opción de crear un simple efecto nulo “en línea” o macro que le permitirá comstackr en otras plataformas con otros comstackdores.

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 comstackdor. Lo que ocurra dependerá de la architecture y la versión del comstackdor.

Esta característica particular en Linux es un poco mal utilizada en los controladores. Como señala osgx en la semántica del atributo caliente , cualquier función hot o cold llamada con un bloque puede indicar automáticamente que la condición es probable o no. Por ejemplo, dump_stack() se marca en cold por lo que es redundante,

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

Las versiones futuras de gcc pueden gcc selectivamente una función basada en estas sugerencias. También se han sugerido que no es boolean , sino una puntuación como la más probable , etc. En general, se debería preferir utilizar algún mecanismo alternativo como el cold . No hay ninguna razón para usarlo en ningún lugar excepto en los caminos calientes. Lo que un comstackdor hará en una architecture puede ser completamente diferente en otra.

En muchos lanzamientos de Linux, puede encontrar complier.h en / usr / linux /, puede incluirlo para usarlo de manera simple. Y otra opinión, improbable () es más útil que probable (), porque

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

también se puede optimizar en muchos comstackdores.

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, abre obj.s, puedes encontrar la respuesta.

Indican al comstackdor que genere los prefijos de pistas en las twigs. En x86 / x64, ocupan un byte, por lo que obtendrás como máximo un incremento de un byte para cada twig. En cuanto al rendimiento, depende por completo de la aplicación: en la mayoría de los casos, el predictor de bifurcación en el procesador los ignorará estos días.

Editar: Olvidé un lugar en el que realmente pueden ayudar. Puede permitir al comstackdor reordenar 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 donde está verificando múltiples casos de salida.

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

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