likely, unlikely y __builtin_expect

Estaba cotilleando las novedades de GCC, y me he encontrado con lo que llaman __builtin_expect. Esta macro, permite indicar al compilador la probabilidad de una condición, de manera que el predictor de saltos sea capaz de generar un código más eficiente.

Lo habitual es que se usen con una macro más legible llamada likely / unlikely, y que indica una probabilidad alta, y una baja respectivamente.

Imaginemos un fragmento de código que lee un pixel, y en el caso de ser de color negro, retorna cierto, y falso en caso contrario:

if (GetPixel() == BLACK)
{
	return(true);
}
else
{
	return(false);
}

Digamos que el compilador podría traducir este código a x86 de una forma parecida a esta:

call	GetPixel
cmp	eax, BLACK
je	true
false:
	xor	eax, eax
	ret
true:
	mov	eax, 1
	ret

De este modo nos encontramos que a nivel de lenguaje máquina, cuando el píxel sea de color negro, entonces se ejecutará el salto a la etiqueta true: y retornará cierto. Si no lo es, no se ejecuta el salto, y retorna falso.

Si sabemos que lo habitual es que los pixels sean de color negro, estamos haciendo que el microprocesador deba ejecutar casi siempre el salto, esto es bastante más lento, y exige un esfuerzo adicional al predictor de saltos. Así que si usamos GCC, lo puede tener en cuenta, y generar un código más eficiente.

if (likely(GetPixel() == BLACK))
{
	return(true);
}
else
{
	return(false);
}

Que lo que generará será de este estilo:

call	GetPixel
cmp	eax, BLACK
jne	false
true:
	mov	eax, 1
	ret
false:
	xor	eax, eax
	ret

Ya lo tenemos, y ahora la mayoría de casos, es decir, píxels negros se ejecutarán de manera más eficaz. No sería una mejora notable, pero entendida por ejemplo en el contexto de un bucle que se repite más de 2 millones de veces para todos los pixels de la pantalla, puede marcar la diferencia.

Desde luego que yo no habría escrito ese código como un if, y probablemente vosotros tampoco, de todas formas likely y unlikely, puede ser aplicado también en esos casos:

return(likely(GetPixel() == BLACK));

En muchos casos, el optimizador es capaz de detectar automáticamente estos casos, y así generar el mejor código posible sin necesidad de usar likely/unlikely. Bien sea por el análisis estático del código en casos sencillos, bien sea usando PGO. Sin embargo en otros, será incapaz de hacerlo sin nuestra ayuda. Es por eso que el kernel de Linux, utiliza ya estas macros, para así conseguir mejores rendimientos.

Quizás en el futuro, este soporte se extienda a otros compiladores distintos de GCC / G++, pero de hasta que eso no ocurra, lo mejor es aplicar unos define de preprocesador para mantener la portabilidad:

#ifdef __GNUC__
	#define likely(x)	__builtin_expect(!!(x), 1)
	#define unlikely(x)	__builtin_expect(!!(x), 0)
#else
	#define likely(x)	(x)
	#define unlikely(x)	(x)
#endif

6 comentarios en “likely, unlikely y __builtin_expect”

  1. que bien lo explicass, guti, me quedo anonadado en tus posts de programacion (lastima que sean tan pocos :D). Tienes unas dotes didacticas increibles, deberias aprovecharlas para dar clases o algo asi (bueno, sin dejar de escribir posts de esta indole, a ver si te vamos a perder…).
    El likely es un recurso excepcional, y su aportacion para lograr una ejecucion eficiente es valiosisima. Me parece que los lenguajes de alto nivel deberian llevar un «probable» como este. no se si c# tendra algo asi, pero en el resto no recuerdo ninguno que pueda hacer probable una condicion tipica de un if o un case.

  2. Muchas gracias nelbu. La verdad que el tiempo no da para todo en el blog, pero tomo nota de intentar volver a más cosas de programación, que al final es a lo que me dedicaba casi exclusivamente cuando empecé el blog. Ahora con los relojes, el afeitado, la ropa, … todo se va diluyendo.

    Bueno, de la formación, me dediqué, muy efímeramente, todo hay que decirlo, hace algunos años, y el problema es siempre poder enseñar, sobre algo que a ti también te guste. Es decir, enseñar como funciona Chrome, pues como que tiene poca gracia. Pero si es cierto que me dicen que lo explico bien, y tengo bastante paciencia.

    Que yo sepa, C++ es el único que lo tiene, y en realidad, sólo GCC lo implementa. Que C#, u otros lenguajes basados en JIT no lo tengan, tiene sentido, al final, en tiempo de ejecución, se puede reoptimizar el código generado en base al flujo de ejecución, es decir, sobre lo que ha detectado que es más probable. O así debería ser en el ideal.

    Lo que es raro, es que otros lenguajes, nativos, o sea sin JIT, no lo tengan. Personalmente, me sorprendió sobremanera, que ni siquiera Visual C++ 2015 implementara likely unlikely, y todo se tuviera que hacer de forma automatizada usando PGO.

  3. gracias por la respuesta Guti. Tengo que ponerme un dia con C# a ver si consigo hacer algo con él 😀 Aunque a este paso todos acabaremos haciéndoles watchfaces y tonterias con Bionic para los android, jajaja! Aunque tu ahi tienes ventaja, porque con C te mueves como pez en el agua. Sin embargo yo puedo esperar sentado a que saquen algo asi para visual basic… Bueno, igual microsoft hace algo, que esos llegan tarde pero pegan fuerte.

  4. nelbu, no tan rápido que yo sigo siendo un entusiasta del Visual Basic, nada de VB.NET que eso es otra cosa, y para eso ya tenemos C#. Ahora que lo dices, me da que Microsoft está un poco como Casio. Viviendo de su Office (analógicos), y erre que erre con .NET (colorines), cuando muchos, ya se están pasando a OpenOffice o LibreOffice y lo que demanda la gente es más facilidad como con VB.NET o más potencia, como con C++, o sea, Marlins.

  5. que curioso, es verdad, tienes toda la razon. Y lo mas llamativo es que, como Casio, tienen todo el potencial para hacerlo bien y no lo hacen.

Deja un comentario