Son una sugerencia 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 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 vaciarse 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 las optimizaciones de rendimiento de este tipo, solo debe hacerlo después de un perfilado exhaustivo para asegurarse de que el código realmente se encuentra en un cuello de botella y, probablemente, dada la naturaleza micro, se está ejecutando en un ciclo cerrado. En general, los desarrolladores de Linux tienen bastante experiencia, así que me imagino que lo habrían hecho. En realidad, no les importa demasiado la portabilidad, ya que solo apuntan a gcc y tienen una idea muy cercana del ensamblado que quieren que genere.
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;
}
Compilar y descompilar 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 printf y luego puts y el retq volver.
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 a __printf_chk ) se movió al final de la función, después de 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 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 se ejecute más rápido con __builtin_expect que sin, las CPU son realmente inteligentes en estos días. Mis intentos ingenuos 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 instrucción if-else Es probable que (¡un juego de palabras!) hagan lo mismo.
Estas son macros que 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 los utiliza para optimizar la predicción de bifurcaciones. Por ejemplo, si tiene algo como lo siguiente
if (unlikely(x)) {
dosomething();
}
return x;
Entonces puede reestructurar este código para que sea algo más como:
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 especulativamente más adelante. Cuando determina que tomará la rama, 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 bifurcación, pero eso solo ayuda cuando ha pasado por la bifurcación antes, y la bifurcación todavía está en el caché de predicción de bifurcación.
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 ramas en Wikipedia:http://en.wikipedia.org/wiki/Branch_predictor