Pregunta sobre linux, gcc, likely-unlikely, linux-kernel – ¿Cómo funcionan las macros probables / improbables en el kernel de Linux y cuál es su beneficio?

295

He estado cavando a través de 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 están 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).

De acuerdo con laPreguntas frecuentes de kernelnewbies (y la última fuente del kernel 3.11), las definiciones de macros ahora son un poco diferentes: # define probablemente (x) __builtin_expect (!! (x), 1) # define poco probable (x) __builtin_expect (!! (x), 0) I ¿Supongo que esto añade un poco más a la confusión? :) No tengo la necesidad de doble NOT (<code> !! </code>). Mandeep Sandhu
ver tambiénBOOST_LIKELY Ruggero Turra
Esto realmente no es específico del kernel de Linux o de las macros, sino de una optimización del compilador. ¿Se debería volver a etiquetar esto para reflejar eso? Cody Brocious
El papelLo que todo programador debe saber sobre la memoria (p. 57) contiene una explicación en profundidad. Torsten Marek

Tu respuesta

10   la respuesta
5
long __builtin_expect(long EXP, long C);

ente 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

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__builtin_expect(!!(expr),0) en lugar de solo__builtin_expect((expr),0)? Michael Firth
277

ue la predicción de bifurcaciones 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 tomará cero ciclos. Por otro lado, si la predicción es incorrecta, entonces significa que la tubería del procesador debe ser lavada y puede costar varios ciclos. Mientras la predicción sea correcta la mayor parte del tiempo, esto tenderá a ser bueno para el desempeño.

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 se encuentre en un cuello de botella, y probablemente dada la naturaleza micro, de que se está ejecutando en un bucle cerrado. En general, los desarrolladores de Linux tienen bastante experiencia, así que me imagino que lo habrían hecho. Realmente no les importa mucho la portabilidad, ya que solo se enfocan en gcc, y tienen una idea muy cercana del ensamblaje que desean que genere.

@RossRogers: Mi punto principal fue que diseñar el camino rápido con ramas en su mayoría no tomadas es bueno, y es una victoria incluso después de que los predictores de ramas se calientan (por ejemplo, en un circuito cerrado). Peter Cordes
Absolutamente, hay todo tipo de razones relacionadas con la canalización por las que se prefiere el código lineal y no tienen nada que ver con las derivaciones estáticas incrustadas en la instrucción. Las CPU modernas generalmente las ignoran, por lo que todo el razonamiento dado en esta respuesta es obsoleto. @Bryce BeeOnRope
re: prediction: las CPU de Intel de las últimas generaciones literalmente no tienen ninguna predicción de rama estática. En lugar de una nueva sucursal que desaloja / sobrescribe una entrada antigua en el BTB, simplemente la usa con los datos antiguos que había allí antes. Así que una rama fría alias una rama caliente no pierde todo el historial de predicción de la rama caliente (solo la contamina un poco). No hay una predicción estática porque el predictor no puede decir que no ha visto una rama antes.El documento de microarquía de Agner Fog tiene un capítulo inicial sobre la predicción de ramas.. Peter Cordes
@Peter Cordes: entiendo el alias de la tabla de sucursales, por eso escribíthe history table is overwritten by a different branch with the same index into the branching table.  Solo estaba señalando la cosa del lazo apretado. Si ejecuta el bucle una y otra vez, el costo inicial es trivial y el predictor de bifurcaciones toma el control, a menos que obtenga una predicción de bifurcaciones a través de saltos / llamadas dentro del "bucle cerrado". Decirle al compilador que favorezca una rama es una microoptimización en bucles ajustados que se ejecuta muchas veces. Todo muy pedante, sin duda :-) Ross Rogers
66

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 utiliza estos para optimizar para la predicción de 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 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

Además, afecta la huella del icache, al mantener fragmentos de código poco probables fuera de la ruta activa. fche
Más precisamente, puede hacerlo congotos sin repetir elreturn x: stackoverflow.com/a/31133787/895245 Ciro Santilli 新疆改造中心996ICU六四事件
2

CodyEsto 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. Comoosgx señala ensemántica del atributo caliente, algunahot ocold La función llamada con en un bloque puede sugerir automáticamente que la condición es probable o no. Por ejemplo,dump_stack() está marcadocold así que esto es redundante,

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

Futuras versiones degcc puede alinear selectivamente una función basada en estas sugerencias. También ha habido sugerencias de que no esboolean, pero una puntuación como enmás probable, etc. En general, debería preferirse usar algún mecanismo alternativo comocold. 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.

1

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

La forma en que se construyen las instrucciones de bifurcación depende de la arquitectura del procesador.

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

Creo que ustedes dos realmente están de acuerdo el uno con el otro, es solo una frase confusa. (Por lo que parece, el comentario de Andrew dice "puedes usarlos sin perder la portabilidad", pero Sharptoth pensó que dijo "no los uses porque no son portátiles" y se opuso). Miral
No usa la portabilidad, las plataformas que no las admiten solo las definen para expandirse a cadenas vacías. sharptooth
6

Hacen que el compilador emita los consejos de bifurcación adecuados 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 predicha 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 correctamente insinuada una 8 y otra incorrecta. En los bucles más íntimos, una buena insinuación puede hacer una gran diferencia.

La portabilidad no es realmente un problema: es de suponer que 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.

@CodyBrocious: se insinuaron las ramificaciones con P4, pero se abandonaron 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 macrosno hacer hace que gcc emita prefijos de sugerencia de derivación en x86. Lo ayudan a hacer que gcc desarrolle su función con menos ramas tomadas en el camino rápido. Peter Cordes
Dang RISC CPUs - Manténgase alejado de mis instrucciones de 15 bytes;) Cody Brocious
Dang CISC CPUs y sus instrucciones de longitud variable;) moonshadow
Para el registro, x86 toma espacio adicional para las sugerencias de rama. Debe tener un prefijo de un byte en las sucursales para especificar la sugerencia adecuada. Sin embargo, estoy de acuerdo en que insinuar es una buena cosa (TM). Cody Brocious
1

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 aumento 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 mejora marcada en los bucles en los que está verificando múltiples casos de salida.

gcc nunca genera sugerencias de rama x86: al menos todas las CPU de Intel las ignorarían de todos modos. Sin embargo, intentará limitar el tamaño del código en regiones poco probables evitando la alineación y el desenrollado de bucles. alex strange
60

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 instrucción en la memoria no se modificó: primero elprintf y entoncesputs y elretq regreso.

Con__builtin_expect

Ahora reemplazaif (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>

losprintf (compilado para__printf_chk) fue movido al final de la función, después deputs y el retorno para mejorar la predicción de la rama como se menciona en 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 hizo con-O0.

Pero buena suerte al escribir un ejemplo que corre más rápido con__builtin_expect que sinLas CPUs son realmente inteligentes esos días. Mis intentos ingenuosestán aquí.

2

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.

Preguntas relacionadas