El bucle vacío es más lento que uno no vacío en C

13 minutos de lectura

avatar de usuario
celerio

Mientras intentaba saber cuánto tiempo solía ejecutarse una línea de código C, noté algo extraño:

int main (char argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<(1<<31)-1; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

Que cuando se ejecuta muestra:

5.873425
4.826874

¿Por qué el ciclo vacío usa más tiempo que el segundo que tiene una instrucción dentro? Por supuesto, he probado muchas variantes, pero cada vez, un ciclo vacío lleva más tiempo que uno con una sola instrucción dentro.

Tenga en cuenta que he intentado intercambiar el orden de los bucles y agregar un código de calentamiento y no cambió mi problema en absoluto.

Estoy usando bloques de código como IDE con el compilador GNU gcc, linux ubuntu 14.04 y tengo un quadcore intel i5 a 2.3GHz (he intentado ejecutar el programa en un solo núcleo, esto no cambia el resultado).

  • ¿Cuáles son sus opciones de compilador y qué tiene que decir el ensamblado al respecto?

    – chris

    31 de julio de 2014 a las 20:08

  • ¿Cuántos compiladores de C cree que dedican mucho esfuerzo a optimizar los bucles vacíos?

    – Lame caliente

    31 de julio de 2014 a las 20:09

  • Si está interesado en el rendimiento de su código, abandone clock() y convertir un genuino perfilador suelto en bits optimizados en modo de liberación.

    – WhozCraig

    31 de julio de 2014 a las 20:12

  • Dado que el valor de A nunca se usa, es probable que el compilador también haya dejado vacío el segundo bucle, en cuyo caso la pregunta es por qué los dos bucles no son idénticos. ¿Qué sucede con los tiempos si imprime el valor de A después del segundo bucle?

    – Chepner

    31 de julio de 2014 a las 20:14


  • Es un caso irreal, de “juguete”, mal medido. No se puede derivar nada significativo.

    – Lame caliente

    31/07/2014 a las 20:15

avatar de usuario
Bill Lynch

Suponiendo que su código usa un número entero de 32 bits int type (lo que probablemente hace su sistema), entonces no se puede determinar nada a partir de su código. En cambio, exhibe un comportamiento indefinido.

foo.c:5:5: error: first parameter of 'main' (argument count) must be of type 'int'
int main (char argc, char * argv[]) {
    ^
foo.c:13:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++);
                         ^
foo.c:19:26: warning: overflow in expression; result is 2147483647 with type 'int' [-Winteger-overflow]
    for (i = 0; i<(1<<31)-1; i++) {
                         ^

Intentemos arreglar eso:

#include <stdint.h>
#include <stdio.h>
#include <time.h>
#include <limits.h>

int main (int argc, char * argv[]) {
    time_t begin, end;
    uint64_t i;
    double total_time, free_time;
    int A = 1;
    int B = 1;

    begin = clock();
    for (i = 0; i<INT_MAX; i++);
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    begin = clock();
    for (i = 0; i<INT_MAX; i++) {
        A += B%2;
    }
    end = clock();
    free_time = (double)(end-begin)/CLOCKS_PER_SEC;
    printf("%f\n", free_time);

    return(0);
}

Ahora, veamos el resultado del ensamblado de este código. Personalmente, encuentro que el ensamblaje interno de LLVM es muy legible, así que lo mostraré. Lo produciré ejecutando:

clang -O3 foo.c -S -emit-llvm -std=gnu99

Aquí está la parte relevante de la salida (la función principal):

define i32 @main(i32 %argc, i8** nocapture readnone %argv) #0 {
  %1 = tail call i64 @"\01_clock"() #3
  %2 = tail call i64 @"\01_clock"() #3
  %3 = sub nsw i64 %2, %1
  %4 = sitofp i64 %3 to double
  %5 = fdiv double %4, 1.000000e+06
  %6 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %5) #3
  %7 = tail call i64 @"\01_clock"() #3
  %8 = tail call i64 @"\01_clock"() #3
  %9 = sub nsw i64 %8, %7
  %10 = sitofp i64 %9 to double
  %11 = fdiv double %10, 1.000000e+06
  %12 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds ([4 x i8]* @.str, i64 0, i64 0), double %11) #3
  ret i32 0
}

Tenga en cuenta que hay no operaciones entre las llamadas a clock() por cualquier caso. Así que ambos están compilados en el exactamente lo mismo.

  • No tengo idea de quién fue lo suficientemente ignorante como para rechazarlo por señalar un comportamiento indefinido; sin embargo, esta respuesta podría mejorarse mostrando el código y la línea de comando del compilador que generó eso, en lugar de ambiguo “Si solucionamos estos problemas”

    – Ben Voigt

    31 de julio de 2014 a las 20:22

  • Al menos cuenta lo que hiciste para “arreglar” la UB. Usaste INT_MAX ? 0x7FFFFFFF ? Y las opciones de compilación.

    – Ben Voigt

    31 de julio de 2014 a las 20:24


  • -1: Todavía no sé por qué el bucle vacío es más lento. Además, modificó el código, usó -O3 y un compilador diferente. Y como resulta de esta otra respuesta, el comportamiento indefinido es no responsable de la diferencia de rendimiento.

    – jmiserez

    01/08/2014 a las 22:11


  • @jmiserez: Por supuesto que usó -O3. La pregunta no decía lo contrario, y habilitar la optimización es lo más sensato cuando se mide el rendimiento. (Podemos debatir si -O3 o -O2 o -Os es lo mejor, pero el nivel “correcto” para explicar lo que observó el OP es lo que usó el OP, y la pregunta no reveló eso)

    – Ben Voigt

    4 de agosto de 2014 a las 16:19

  • @jmiserez: De sus puntos, el único que puedo tomar en serio es que usé un compilador diferente. Así que acabo de hacer una prueba con gcc 4.8.2 y gcc 4.9.0, y aparte de informar otro pieza de comportamiento indefinido que me perdí, también optimiza el bucle en un nop.

    – Bill Lynch

    4 de agosto de 2014 a las 17:16


avatar de usuario
gnasher729

El hecho es que los procesadores modernos son complicados. Todas las instrucciones ejecutadas interactuarán entre sí de formas complicadas e interesantes. Gracias por “ese otro tipo” por publicar el código.

Tanto OP como “ese otro tipo” aparentemente encontraron que el ciclo corto toma 11 ciclos, mientras que el largo toma 9 ciclos. Para el bucle largo, 9 ciclos es mucho tiempo, aunque hay muchas operaciones. Para el bucle corto, debe haber algún bloqueo causado por ser tan corto y simplemente agregar un nop hace que el bucle sea lo suficientemente largo para evitar la pérdida.

Una cosa que sucede si miramos el código:

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

Leemos i y escríbelo de nuevo (addq). Lo leemos inmediatamente de nuevo y lo comparamos (cmpq). Y luego hacemos un bucle. Pero el ciclo usa predicción de bifurcación. Así que en el momento en que el addq se ejecuta, el procesador no está realmente seguro de que se le permita escribir en i (porque la predicción de bifurcación podría ser incorrecta).

Luego comparamos con i. El procesador intentará evitar leer i de memoria, porque leerlo lleva mucho tiempo. En su lugar, un poco de hardware recordará que acabamos de escribir a i añadiéndole, y en lugar de leer ila cmpq instrucción obtiene los datos de la instrucción de almacenamiento. Desafortunadamente, no estamos seguros en este momento si escribir a i realmente sucedió o no! Entonces eso podría introducir un puesto aquí.

El problema aquí es que el salto condicional, el addq que conduce a un almacén condicional, y el cmpq que no está seguro de dónde obtener los datos, están todos muy, muy juntos. Están inusualmente juntos. Puede ser que estén tan cerca el uno del otro que el procesador no pueda determinar en este momento si tomar i de la instrucción de almacenamiento o para leerlo de la memoria. Y lo lee de memoria, que es más lento porque tiene que esperar a que termine la tienda. Y agregando solo uno nop le da al procesador suficiente tiempo.

Por lo general, piensas que hay RAM y caché. En un procesador Intel moderno, la memoria de lectura puede leer (de la más lenta a la más rápida):

  1. Memoria (RAM)
  2. Caché L3 (opcional)
  3. caché L2
  4. caché L1
  5. Instrucción de almacenamiento anterior que aún no se ha escrito en la memoria caché L1.

Entonces, lo que hace el procesador internamente en el ciclo corto y lento:

  1. Leer i de caché L1
  2. Añadir 1 a i
  3. Escribe i a la caché L1
  4. Esperar hasta i se escribe en la memoria caché L1
  5. Leer i de caché L1
  6. Comparar i con INT_MAX
  7. Rama a (1) si es menor.

En el bucle largo y rápido, el procesador hace lo siguiente:

  1. Un montón de cosas
  2. Leer i de caché L1
  3. Añadir 1 a i
  4. Haga una instrucción de “almacenamiento” que escribirá i a la caché L1
  5. Leer i directamente desde la instrucción “almacenar” sin tocar el caché L1
  6. Comparar i con INT_MAX
  7. Rama a (1) si es menor.

  • Gracias por esta respuesta tan completa. Como nunca hice ningún código ensamblador, este nivel de detalles realmente ayuda. Deberías poner un enlace de tu respuesta a OP y “ese otro tipo” responde 🙂

    – Celerio

    1 de agosto de 2014 a las 10:27

  • Las respuestas a continuación parecen invalidar esta. Además, el punto principal de esta respuesta es solo adivinar “Podría ser eso”.

    – BartoszKP

    2 de agosto de 2014 a las 11:42

  • Dado que “arriba” y “abajo” son bastante relativos, explique cómo se invalida esta respuesta.

    – gnasher729

    02/08/2014 a las 15:35

  • intel.com/content/dam/www/public/us/en/documents/manuals/… explica varios tipos de paradas en las que puede incurrir y cómo evitarlas. Básicamente, el NOP evita que un recurso se detenga al darle tiempo al procesador para confirmar los cambios en el registro. El caché no es necesariamente relevante aquí, pero los puestos son reales; escribir en un registro sigue siendo escribir en algún tipo de memoria que todavía tiene una velocidad de escritura finita y provocará bloqueos cuando la CPU se dé cuenta de que una instrucción necesita un registro que ya está en uso.

    – sfdcfox

    02/08/2014 a las 18:17

  • ¿Es el optimizador lo suficientemente inteligente como para obtener una buena programación? La conclusión que el OP derivó de este efecto no está justificada a menos que el optimizador genere un código que lo padezca.

    – Ben Voigt

    04/08/2014 a las 16:20

avatar de usuario
ben voigt

Esta respuesta asume que ya entendió y abordó los puntos excelentes con respecto al comportamiento indefinido que Sharth hace en su respuesta. También señala trucos que el compilador puede jugar con su código. Debe tomar medidas para asegurarse de que el compilador no reconozca todo el bucle como inútil. Por ejemplo, cambiar la declaración del iterador a volatile uint64_t i; prevendrá la remoción del lazo, y volatile int A; asegurará que el segundo bucle realmente haga más trabajo que el primero. Pero incluso si haces todo eso, es posible que descubras que:

El código posterior en un programa puede ejecutarse más rápidamente que el código anterior.

los clock() la función de la biblioteca podría haber causado una falla de icache después de leer el temporizador y antes de regresar. Esto causaría algo de tiempo extra en el primer intervalo medido. (Para llamadas posteriores, el código ya está en caché). Sin embargo, este efecto será minúsculo, ciertamente demasiado pequeño para clock() para medir, incluso si fue una falla de página hasta el disco. Los cambios de contexto aleatorios pueden agregarse a cualquier intervalo de tiempo.

Más importante aún, tiene una CPU i5, que tiene reloj dinámico. Cuando su programa comienza a ejecutarse, la velocidad del reloj probablemente sea baja, porque la CPU ha estado inactiva. Simplemente ejecutar el programa hace que la CPU ya no esté inactiva, por lo que después de un breve retraso, la velocidad del reloj aumentará. La relación entre la frecuencia de reloj de la CPU inactiva y TurboBoosted puede ser significativa. (En el Haswell i5-4200U de mi ultrabook, el multiplicador anterior es 8 y el segundo es 26, ¡lo que hace que el código de inicio se ejecute menos del 30% tan rápido como el código posterior! Los bucles “calibrados” para implementar retrasos son una idea terrible en las computadoras modernas. )

¡Incluir una fase de calentamiento (ejecutar un punto de referencia repetidamente y descartar el primer resultado) para una sincronización más precisa no es solo para marcos administrados con compiladores JIT!

  • Ya había intentado agregar alguna fase de calentamiento, o incluso cambiar las posiciones de los bucles sin éxito. Debería haber puesto esto en mi respuesta, lo editaré.

    – Celerio

    1 de agosto de 2014 a las 10:33

  • En realidad, no creo que sea justo dar tiempo de calentamiento a los marcos administrados y los compiladores JIT;) a menos que nunca vean un reinicio y una aceleración muy rápida. Al igual que no es justo darles tiempo de carga de VM gratis, etc. porque esos pueden ser retrasos no despreciables. Reinicio diario, comportamiento no almacenado en caché muy lento, almacenamiento en caché lento, muchas cosas pueden hacer que el estado “calentado” no sea realista.

    – Morga.

    2 de agosto de 2014 a las 10:11

  • @Morg .: No se trata de ser “justo” con las diferencias entre marcos, se trata de probar qué variación en el código para un lenguaje/marco en particular obtiene los mejores resultados.

    – Ben Voigt

    2 de agosto de 2014 a las 15:28

  • @BenVoigt Mi error. Entonces, sobre ese tema: qué variación en el código para un lenguaje/marco en particular obtiene los mejores resultados también depende de si esa variación no necesita calentamiento, un calentamiento realista o un calentamiento poco realista. Es muy fácil almacenar en caché todo y luego fingir que una variación es más rápida que todas las demás. Sin embargo, lo bueno es que se trata de C, solo pensé que su oración en negrita tenía implicaciones que harían que un punto de referencia fuera menos relevante en lugar de más.

    – Morga.

    4 de agosto de 2014 a las 16:02

  • @Morg.: Warmup es la forma más fácil de poner todas las variantes en igualdad de condiciones. Si la ejecución en caliente no es la comparación que le interesa, entonces mire todos los medios, mida el tiempo de inicio y los errores de caché, pero asegúrese de incurrir en ellos para todas las versiones. Puede iniciar el ejecutable desde cero, pero eso no significa que los archivos de datos no estén en el caché del disco, etc. Realmente es bastante complicado medir el tiempo de ejecución “en frío”.

    – Ben Voigt

    4 de agosto de 2014 a las 16:14


avatar de usuario
ese otro tipo

Puedo reproducir esto con GCC 4.8.2-19ubuntu1 sin optimización:

$ ./a.out 
4.780179
3.762356

Aquí está el bucle vacío:

0x00000000004005af <+50>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b4 <+55>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bc <+63>:    jb     0x4005af <main+50>

Y aquí está el que no está vacío:

0x000000000040061a <+157>:   mov    -0x24(%rbp),%eax
0x000000000040061d <+160>:   cltd   
0x000000000040061e <+161>:   shr    $0x1f,%edx
0x0000000000400621 <+164>:   add    %edx,%eax
0x0000000000400623 <+166>:   and    $0x1,%eax
0x0000000000400626 <+169>:   sub    %edx,%eax
0x0000000000400628 <+171>:   add    %eax,-0x28(%rbp)
0x000000000040062b <+174>:   addq   $0x1,-0x20(%rbp)
0x0000000000400630 <+179>:   cmpq   $0x7fffffff,-0x20(%rbp)
0x0000000000400638 <+187>:   jb     0x40061a <main+157>

Insertemos un nop en el bucle vacío:

0x00000000004005af <+50>:    nop
0x00000000004005b0 <+51>:    addq   $0x1,-0x20(%rbp)
0x00000000004005b5 <+56>:    cmpq   $0x7fffffff,-0x20(%rbp)
0x00000000004005bd <+64>:    jb     0x4005af <main+50>

Ahora corren igual de rápido:

$ ./a.out 
3.846031
3.705035

Me imagino que esto muestra la importancia de la alineación, pero me temo que no puedo decir específicamente cómo: |

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad