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




bajo version (9)

He estado cavando en 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 de su uso? 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).


Answers

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

Compila y descompila 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 se modificó: primero se printf y luego se puts y se puts el retq retorno.

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 de los puts y el retorno para mejorar la predicción de la rama como lo mencionaron otras respuestas.

Así que 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 él, las CPU son realmente inteligentes en esos días . Mis intentos ingenuos están aquí .


Según el comentario de Cody , esto no tiene nada que ver con Linux, pero es una sugerencia para el compilador. Lo que suceda dependerá de la arquitectura y la versión del compilador.

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

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

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


Estas son macros que le 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 usa estos para optimizar la predicción de la rama. Por ejemplo, si tienes algo como lo siguiente

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

return x;

Entonces puede reestructurar este código para ser algo más como:

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 especulativamente el código 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 rama, pero eso solo ayuda cuando ya ha pasado por la rama antes, y la rama todavía está en el caché de predicción de rama.

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 los consejos de bifurcación apropiados donde el hardware los admite. Por lo general, esto 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 de la ubicación prevista y vaciará la tubería y volverá a comenzar si eso resulta incorrecto cuando se llega a 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 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 impresa puede tardar 16 ciclos, una correcta 8 y una incorrecta. 24. En los bucles más íntimos, una buena sugerencia puede hacer una gran diferencia.

La portabilidad no es realmente un problema, probablemente la definición está en un encabezado por plataforma; simplemente puede definir "probable" y "improbable" para nada en las plataformas que no admiten sugerencias de derivación 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 utilizar como en

if (likely(a > 1))

Referencia: https://www.akkadia.org/drepper/cpumemory.pdf


En muchas versiones de Linux, puede encontrar complier.h en / usr / linux /, puede incluirlo para su uso simplemente. Y otra opinión, poco probable () es más útil que probable (), porque

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

Se puede optimizar también en muchos compiladores.

Y, por cierto, si desea observar el comportamiento detallado del código, puede hacerlo de la siguiente manera:

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

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


(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 "inline" o macro simple 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.


Son sugerencias al compilador para generar los prefijos de sugerencias en las ramas. En x86 / x64, ocupan un byte, por lo que obtendrá como máximo un incremento de un byte para cada rama. En cuanto al rendimiento, depende totalmente 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 al compilador reordenar el gráfico de control-flujo para reducir el número de ramas tomadas para la ruta "probable". Esto puede tener una marcada mejora en los bucles en los que se están comprobando varios casos de salida.


Había hecho la compilación del kernel de Linux y algunas modificaciones para Android (Marshmallow y Nougat) en las que uso la versión 3. de Linux. Lo compilé en el sistema Linux, depuro los errores manualmente y luego ejecuto su archivo de imagen de arranque en Android y verifico si Estaba entrando en el agujero de bucle o no. Si funciona a la perfección, significa que se compila perfectamente de acuerdo con los requisitos del sistema.
Para la compilación del núcleo de MotoG

NOTA: - El kernel de Linux cambiará de acuerdo con los requisitos que dependen del hardware del sistema





linux gcc linux-kernel compiler-construction likely-unlikely