Noté por primera vez en 2009 que GCC (al menos en mis proyectos y en mis máquinas) tienen la tendencia a generar un código notablemente más rápido si optimizo el tamaño ( -Os) en lugar de la velocidad ( -O2o -O3), y me he estado preguntando desde entonces por qué.
He logrado crear un código (bastante tonto) que muestra este comportamiento sorprendente y es lo suficientemente pequeño como para publicarlo aquí.
const int LOOP_BOUND = 200000000;
__attribute__((noinline))
static int add(const int& x, const int& y) {
return x + y;
}
__attribute__((noinline))
static int work(int xval, int yval) {
int sum(0);
for (int i=0; i<LOOP_BOUND; ++i) {
int x(xval+sum);
int y(yval+sum);
int z = add(x, y);
sum += z;
}
return sum;
}
int main(int , char* argv[]) {
int result = work(*argv[1], *argv[2]);
return result;
}
Si lo compilo -Os, se necesitan 0,38 s para ejecutar este programa y 0,44 s si se compila con -O2o -O3. Estos tiempos se obtienen de manera consistente y prácticamente sin ruido (gcc 4.7.2, x86_64 GNU / Linux, Intel Core i5-3320M).
(Actualización: moví todo el código de ensamblaje a GitHub : hicieron que la publicación se hinchara y aparentemente agregan muy poco valor a las preguntas ya que las fno-align-*banderas tienen el mismo efecto).
Aquí está el ensamblado generado con -Osy -O2.
Desafortunadamente, mi comprensión del ensamblaje es muy limitada, por lo que no tengo idea de si lo que hice después fue correcto: agarré el ensamblaje -O2y fusioné todas sus diferencias en el ensamblaje, -Os excepto las .p2alignlíneas, resultado aquí . Este código todavía se ejecuta en 0.38s y la única diferencia es el .p2align material.
Si adivino correctamente, estos son rellenos para la alineación de la pila. De acuerdo con ¿Por qué el pad GCC funciona con NOP? se hace con la esperanza de que el código se ejecute más rápido, pero aparentemente esta optimización fue contraproducente en mi caso.
¿Es el relleno el culpable en este caso? ¿Porque y como?
El ruido que hace prácticamente imposibilita las micro optimizaciones de temporización.
¿Cómo puedo asegurarme de que tales alineaciones accidentales afortunadas / desafortunadas no interfieran cuando hago micro optimizaciones (no relacionadas con la alineación de la pila) en el código fuente C o C ++?
ACTUALIZAR:
Siguiendo la respuesta de Pascal Cuoq, jugué un poco con las alineaciones. Al pasar -O2 -fno-align-functions -fno-align-loopsa gcc, todos .p2alignse han ido del ensamblado y el ejecutable generado se ejecuta en 0.38s. De acuerdo con la documentación de gcc :
-Os habilita todas las optimizaciones de -O2 [pero] -Os deshabilita los siguientes indicadores de optimización:
-falign-functions -falign-jumps -falign-loops -falign-labels -freorder-blocks -freorder-blocks-and-partition -fprefetch-loop-arrays
Entonces, parece un problema de (mal) alineamiento.
Todavía soy escéptico sobre -march=nativelo sugerido en la respuesta de Marat Dukhan . No estoy convencido de que no solo interfiera con este (mal) problema de alineación; No tiene absolutamente ningún efecto en mi máquina. (Sin embargo, voté por su respuesta).
ACTUALIZACIÓN 2:
Podemos sacar -Osde la foto. Los siguientes tiempos se obtienen compilando con
-O2 -fno-omit-frame-pointer0.37s-O2 -fno-align-functions -fno-align-loops0.37s-S -O2luego mover manualmente el ensamblajeadd()después dework()0.37s-O20.44s
Me parece que la distancia add()desde el sitio de la llamada es muy importante. Lo he intentado perf, pero la salida de perf staty perf reporttiene muy poco sentido para mí. Sin embargo, solo pude obtener un resultado consistente:
-O2:
602,312,864 stalled-cycles-frontend # 0.00% frontend cycles idle
3,318 cache-misses
0.432703993 seconds time elapsed
[...]
81.23% a.out a.out [.] work(int, int)
18.50% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
100.00 ¦ lea (%rdi,%rsi,1),%eax
¦ }
¦ ? retq
[...]
¦ int z = add(x, y);
1.93 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
79.79 ¦ add %eax,%ebx
Para fno-align-*:
604,072,552 stalled-cycles-frontend # 0.00% frontend cycles idle
9,508 cache-misses
0.375681928 seconds time elapsed
[...]
82.58% a.out a.out [.] work(int, int)
16.83% a.out a.out [.] add(int const&, int const&) [clone .isra.0]
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ return x + y;
51.59 ¦ lea (%rdi,%rsi,1),%eax
¦ }
[...]
¦ __attribute__((noinline))
¦ static int work(int xval, int yval) {
¦ int sum(0);
¦ for (int i=0; i<LOOP_BOUND; ++i) {
¦ int x(xval+sum);
8.20 ¦ lea 0x0(%r13,%rbx,1),%edi
¦ int y(yval+sum);
¦ int z = add(x, y);
35.34 ¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
39.48 ¦ add %eax,%ebx
¦ }
Para -fno-omit-frame-pointer:
404,625,639 stalled-cycles-frontend # 0.00% frontend cycles idle
10,514 cache-misses
0.375445137 seconds time elapsed
[...]
75.35% a.out a.out [.] add(int const&, int const&) [clone .isra.0] ¦
24.46% a.out a.out [.] work(int, int)
[...]
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
18.67 ¦ push %rbp
¦ return x + y;
18.49 ¦ lea (%rdi,%rsi,1),%eax
¦ const int LOOP_BOUND = 200000000;
¦
¦ __attribute__((noinline))
¦ static int add(const int& x, const int& y) {
¦ mov %rsp,%rbp
¦ return x + y;
¦ }
12.71 ¦ pop %rbp
¦ ? retq
[...]
¦ int z = add(x, y);
¦ ? callq add(int const&, int const&) [clone .isra.0]
¦ sum += z;
29.83 ¦ add %eax,%ebx
Parece que estamos demorando la llamada add()en el caso lento.
He examinado todo lo que perf -epuede escupir en mi máquina; no solo las estadísticas que se dan arriba.
Para el mismo ejecutable, stalled-cycles-frontendmuestra una correlación lineal con el tiempo de ejecución; No noté nada más que pudiera correlacionarse tan claramente. (Comparar stalled-cycles-frontendpara diferentes ejecutables no tiene sentido para mí).
Incluí los errores de caché, ya que surgió como el primer comentario. Examiné todos los errores de caché que se pueden medir en mi máquina perf, no solo los que se dan arriba. Los errores de caché son muy muy ruidosos y muestran poca o ninguna correlación con los tiempos de ejecución.
Respuestas:
Por defecto, los compiladores optimizan para el procesador "promedio". Dado que los diferentes procesadores favorecen diferentes secuencias de instrucciones, las optimizaciones del compilador habilitadas por
-O2podrían beneficiar al procesador promedio, pero disminuyen el rendimiento en su procesador particular (y lo mismo se aplica a-Os). Si prueba el mismo ejemplo en diferentes procesadores, encontrará que algunos de ellos se benefician-O2mientras que otros son más favorables para las-Osoptimizaciones.Estos son los resultados de
time ./test 0 0varios procesadores (tiempo del usuario informado):En algunos casos, puede aliviar el efecto de optimizaciones desfavorables pidiendo
gccoptimizar para su procesador particular (usando opciones-mtune=nativeo-march=native):Actualización: en Core i3 basado en Ivy Bridge, tres versiones de
gcc(4.6.4,4.7.3y4.8.1) producen binarios con un rendimiento significativamente diferente, pero el código de ensamblaje solo tiene variaciones sutiles. Hasta ahora, no tengo explicación de este hecho.Ensamblado desde
gcc-4.6.4 -Os(se ejecuta en 0.709 segundos):Ensamblado desde
gcc-4.7.3 -Os(se ejecuta en 0.822 segundos):Ensamblado desde
gcc-4.8.1 -Os(se ejecuta en 0.994 segundos):fuente
-O2 -fno-align-functions -fno-align-loopsreduce el tiempo0.340s, por lo que podría explicarse por la alineación. Sin embargo, la alineación óptima depende del procesador: algunos procesadores prefieren bucles y funciones alineados.Mi colega me ayudó a encontrar una respuesta plausible a mi pregunta. Se dio cuenta de la importancia del límite de 256 bytes. Él no está registrado aquí y me animó a publicar la respuesta yo mismo (y tomar toda la fama).
Respuesta corta:
Todo se reduce a la alineación. Las alineaciones pueden tener un impacto significativo en el rendimiento, es por eso que tenemos las
-falign-*banderas en primer lugar.He enviado un informe de error (¿falso?) A los desarrolladores de gcc . Resulta que el comportamiento predeterminado es "alineamos los bucles a 8 bytes de forma predeterminada, pero intentamos alinearlo a 16 bytes si no necesitamos completar más de 10 bytes". Aparentemente, este valor predeterminado no es la mejor opción en este caso particular y en mi máquina. Clang 3.4 (troncal) con
-O3la alineación adecuada y el código generado no muestra este comportamiento extraño.Por supuesto, si se realiza una alineación inapropiada, empeora las cosas. Una alineación innecesaria / incorrecta solo consume bytes sin razón y potencialmente aumenta la pérdida de caché, etc.
Simplemente diciéndole a gcc que haga la alineación correcta:
g++ -O2 -falign-functions=16 -falign-loops=16Respuesta larga:
El código se ejecutará más lentamente si:
Un
XXlímite de bytes se cortaadd()en el medio (XXdependiendo de la máquina).si la llamada a
add()tiene que saltar sobre unXXlímite de bytes y el objetivo no está alineado.si
add()no está alineadoSi el bucle no está alineado.
Los primeros 2 son muy visibles en los códigos y resultados que Marat Dukhan publicó amablemente . En este caso,
gcc-4.8.1 -Os(se ejecuta en 0.994 segundos):un límite de 256 bytes corta
add()justo en el medio yadd()ni el bucle ni el otro están alineados. ¡Sorpresa, sorpresa, este es el caso más lento!En el caso
gcc-4.7.3 -Os(se ejecuta en 0.822 segundos), el límite de 256 bytes solo corta en una sección fría (pero ni el bucle ni eladd()corte):Nada está alineado, y la llamada a
add()tiene que saltar sobre el límite de 256 bytes. Este código es el segundo más lento.En el caso
gcc-4.6.4 -Os(se ejecuta en 0.709 segundos), aunque nada está alineado, la llamada aadd()no tiene que saltar sobre el límite de 256 bytes y el objetivo está exactamente a 32 bytes:Este es el más rápido de los tres. Por qué el límite de 256 bytes es especial en su máquina, dejaré que él lo resuelva. No tengo ese procesador.
Ahora, en mi máquina no obtengo este efecto de límite de 256 bytes. Solo la función y la alineación del bucle se activan en mi máquina. Si apruebo
g++ -O2 -falign-functions=16 -falign-loops=16, todo vuelve a la normalidad: siempre obtengo el caso más rápido y el tiempo ya no es sensible a la-fno-omit-frame-pointerbandera. Puedo pasarg++ -O2 -falign-functions=32 -falign-loops=32o cualquier múltiplo de 16, el código tampoco es sensible a eso.Una explicación probable es que tenía puntos de acceso que eran sensibles a la alineación, al igual que en este ejemplo. Al jugar con las banderas (pasando en
-Oslugar de-O2), esos puntos de acceso se alinearon de manera afortunada por accidente y el código se hizo más rápido. No tenía nada que ver con la optimización del tamaño: estos fueron por puro accidente que los puntos calientes se alinearon mejor. A partir de ahora, comprobaré los efectos de la alineación en mis proyectos.Ah, y una cosa más. ¿Cómo pueden surgir esos puntos críticos, como el que se muestra en el ejemplo? ¿Cómo puede
add()fallar la inserción de una función tan pequeña como esta ?Considera esto:
y en un archivo separado:
y compilado como:
g++ -O2 add.cpp main.cpp.¡gcc no estará en línea
add()!Eso es todo, es así de fácil crear involuntariamente zonas interactivas como la del OP. Por supuesto, es en parte mi culpa: gcc es un excelente compilador. Si compilo lo anterior como:
g++ -O2 -flto add.cpp main.cppes decir, si realizo la optimización del tiempo de enlace, ¡el código se ejecuta en 0.19s!(La alineación está deshabilitada artificialmente en el OP, por lo tanto, el código en el OP fue 2 veces más lento).
fuente
inlinedefinición de función + en el encabezado. No estoy seguro de cuán maduro es lto en gcc. Mi experiencia con él al menos en mingw es impredecible.-flto. es bastante revolucionario si nunca lo has usado antes, hablando por experiencia :)Estoy agregando este post-accept para señalar que se han estudiado los efectos de la alineación en el rendimiento general de los programas, incluidos los grandes. Por ejemplo, este artículo (y creo que una versión de esto también apareció en CACM) muestra cómo los cambios en el orden del enlace y el tamaño del entorno del sistema operativo fueron suficientes para cambiar el rendimiento de manera significativa. Atribuyen esto a la alineación de los "hot loops".
Este documento, titulado "¡Producir datos incorrectos sin hacer nada obviamente incorrecto!" dice que el sesgo experimental inadvertido debido a diferencias casi incontrolables en los entornos de ejecución de programas probablemente deja sin sentido muchos resultados de referencia.
Creo que te encuentras con un ángulo diferente en la misma observación.
Para el código de rendimiento crítico, este es un argumento bastante bueno para los sistemas que evalúan el entorno en el momento de la instalación o el tiempo de ejecución y eligen el mejor local entre las versiones de rutinas clave optimizadas de manera diferente.
fuente
Creo que puedes obtener el mismo resultado que lo que hiciste:
... mediante el uso
-O2 -falign-functions=1 -falign-jumps=1 -falign-loops=1 -falign-labels=1. He estado compilando todo con estas opciones, que fueron más rápidas de lo normal-O2cada vez que me molesté en medir, durante 15 años.Además, para un contexto completamente diferente (incluido un compilador diferente), noté que la situación es similar : la opción que se supone que "optimiza el tamaño del código en lugar de la velocidad" optimiza el tamaño y la velocidad del código.
No, esto no tiene nada que ver con la pila, los NOP que se generan por defecto y que las opciones -falign - * = 1 prevent son para la alineación del código.
Es muy probable que el relleno sea el culpable. La razón por la que se considera que el relleno es necesario y es útil en algunos casos es que el código generalmente se obtiene en líneas de 16 bytes (consulte los recursos de optimización de Agner Fog para obtener detalles, que varían según el modelo de procesador). Alinear una función, un bucle o una etiqueta en un límite de 16 bytes significa que las posibilidades aumentan estadísticamente de que se necesitarán unas líneas menos para contener la función o el bucle. Obviamente, es contraproducente porque estos NOP reducen la densidad del código y, por lo tanto, la eficiencia de la memoria caché. En el caso de los bucles y la etiqueta, los NOP incluso pueden necesitar ejecutarse una vez (cuando la ejecución llega al bucle / etiqueta normalmente, a diferencia de un salto).
fuente
-O2 -fno-omit-frame-pointeres tan bueno como-Os. Por favor revise la pregunta actualizada.Si su programa está limitado por el caché CODE L1, la optimización para el tamaño de repente comienza a pagar.
Cuando lo revisé por última vez, el compilador no es lo suficientemente inteligente como para resolver esto en todos los casos.
En su caso, -O3 probablemente genera código suficiente para dos líneas de caché, pero -Os cabe en una línea de caché.
fuente
-falign-*=16banderas, todo vuelve a la normalidad, todo se comporta de manera consistente. En lo que a mí respecta, esta pregunta está resuelta.De ninguna manera soy un experto en esta área, pero parece recordar que los procesadores modernos son bastante sensibles cuando se trata de predicción de ramificaciones . Los algoritmos utilizados para predecir las ramas se basan (o al menos en los días que escribí el código de ensamblador) en varias propiedades del código, incluida la distancia de un objetivo y la dirección.
El escenario que viene a la mente es pequeños bucles. Cuando la rama iba hacia atrás y la distancia no estaba demasiado lejos, la predicción de la rama se estaba optimizando para este caso ya que todos los bucles pequeños se hacen de esta manera. Las mismas reglas pueden entrar en juego cuando intercambias la ubicación de
addyworken el código generado o cuando la posición de ambos cambia ligeramente.Dicho esto, no tengo idea de cómo verificar eso y solo quería hacerle saber que esto podría ser algo que desee analizar.
fuente
add()ywork()si-O2se pasa. En todos los demás casos, el código se vuelve significativamente más lento al intercambiar. Durante el fin de semana, también analicé las estadísticas de predicción de rama / predicción erróneaperfy no noté nada que pudiera explicar este comportamiento extraño. El único resultado consistente es que en el caso lentoperfinforma 100.0 inadd()y un gran valor en la línea justo después de la llamada aladd()bucle. Parece que nos estamos estancando por alguna razónadd()en el caso lento pero no en las carreras rápidas.perfadmite solo un número limitado de cosas, quizás las cosas de Intel son un poco más útiles en su propio procesador.