para - manual de programacion android pdf

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

Question

Mientras trataba de saber cuánto tiempo una línea de código C solía ejecutar, noté esta cosa extraña:

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 bucle vacío usa más tiempo que el segundo que tiene una instrucción dentro? Por supuesto que he probado muchas variantes pero cada vez, un ciclo vacío toma más tiempo que uno con una sola instrucción dentro.

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

Estoy usando codeblocks 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).

Answer 1

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

Tanto OP como "ese otro tipo" aparentemente descubrieron que el ciclo corto lleva 11 ciclos, mientras que el largo toma 9 ciclos. Para el ciclo largo, 9 ciclos es mucho tiempo a pesar de que hay muchas operaciones. Para el ciclo corto, debe haber un bloqueo debido a que es muy corto, y simplemente al agregar un nop hace que el ciclo sea lo suficientemente largo como para evitar el bloqueo.

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 y lo escribimos de nuevo ( addq ). Lo leemos de nuevo inmediatamente y lo comparamos ( cmpq ). Y luego hacemos un bucle. Pero el ciclo usa predicción de bifurcación. Entonces, en el momento en que se ejecuta el addq , el procesador no está realmente seguro de poder escribir en i (porque la predicción de bifurcación podría estar equivocada).

Entonces nos comparamos con i . El procesador tratará de evitar leerlo de memoria, porque leerlo lleva mucho tiempo. En cambio, un poco de hardware recordará que simplemente le escribimos añadiéndole, y en lugar de leer i , la instrucción cmpq obtiene los datos de las instrucciones de la tienda. Desafortunadamente, no estamos seguros en este momento si la escritura en realidad 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 almacenamiento condicional, y el cmpq que no se está seguro de dónde obtener los datos, están muy muy juntos. Están excepcionalmente juntos. Puede ser que estén tan cerca unos de otros, el procesador no puede darse cuenta en este momento si tomar i de las instrucciones de la tienda o leerlo de memoria. Y lo lee de memoria, que es más lento porque tiene que esperar a que termine la tienda. Y agregar solo un nop le da al procesador suficiente tiempo.

Usualmente piensas que hay memoria RAM, y hay memoria caché. En un procesador Intel moderno, la lectura de memoria puede leer de (más lento a más rápido):

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

Entonces, ¿qué hace el procesador internamente en el ciclo corto y lento?

1. Leer i desde la memoria caché L1
2. Agregar 1 a i
3. Escribir i en caché L1
4. Espere hasta que se escriba en el caché L1
5. Leer i desde la memoria caché L1
6. Compare i con INT_MAX
7. Sucurge a (1) si es menor.

En el bucle largo, rápido, el procesador hace:

1. Un montón de cosas
2. Leer i desde la memoria caché L1
3. Agregar 1 a i
4. Realice una instrucción de "tienda" que escribirá en la caché L1
5. Lea i directamente desde la instrucción "store" sin tocar el caché L1
6. Compare i con INT_MAX
7. Sucurge a (1) si es menor.

Answer 2

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>

Inserte 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: |

Answer 3

Suponiendo que su código utiliza un tipo entero entero de 32 bits (que probablemente su sistema lo haga), 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++) {
^

Tratemos de 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 la salida de ensamblaje de este código. Personalmente, encuentro que el ensamble interno de LLVM es muy legible, así que voy a mostrarlo. 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 no hay operaciones entre las llamadas a clock() para ningún caso . Entonces ambos están compilados exactamente a lo mismo .

Answer 4

Esta respuesta asume que ya has entendido y abordado los puntos excelentes sobre el comportamiento indefinido que Sharth hace en su respuesta . También señala los trucos que el compilador puede jugar en su código. Debería tomar medidas para asegurarse de que el compilador no reconozca todo el ciclo como inútil. Por ejemplo, cambiando la declaración del iterador a volatile uint64_t i; impedirá la eliminación del ciclo, y volatile int A; asegurará que el segundo bucle en realidad haga más trabajo que el primero. Pero incluso si haces todo eso, aún puedes descubrir que:

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

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

Más importante aún, tienes una CPU i5, que tiene sincronización dinámica. Cuando el programa comienza a ejecutarse, la velocidad del reloj probablemente sea baja, porque la CPU ha estado inactiva. El solo hecho de 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 Haswell i5-4200U de mi ultrabook, el multiplicador anterior es 8 y el último 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 (ejecutando un punto de referencia repetidamente, y tirando el primer resultado) para un cronometraje más preciso no es solo para marcos administrados con compiladores JIT.