trigonometria - Dos funciones muy similares que involucran a sen() exhiben un rendimiento muy diferente: ¿por qué?

seno de pi

Question

Considere los siguientes dos programas que realizan los mismos cálculos de dos maneras diferentes:

// v1.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x;
   for (j = 0; j < nbr_values; j++) {
      x = 1;
      for (i = 0; i < n_iter; i++)
         x = sin(x);
   }
   printf("%f/n", x);
   return 0;
}

y

// v2.c
#include <stdio.h>
#include <math.h>
int main(void) {
   int i, j;
   int nbr_values = 8192;
   int n_iter = 100000;
   float x[nbr_values];
   for (i = 0; i < nbr_values; ++i) {
      x[i] = 1;
   }
   for (i = 0; i < n_iter; i++) {
      for (j = 0; j < nbr_values; ++j) {
         x[j] = sin(x[j]);
      }
   }
   printf("%f/n", x[0]);
   return 0;
}

Cuando los compilo usando gcc 4.7.2 con -O3 -ffast-math y corro en un cuadro Sandy Bridge, el segundo programa es dos veces más rápido que el primero.

¿Porqué es eso?

Un sospechoso es la dependencia de datos entre iteraciones sucesivas del ciclo i en v1 . Sin embargo, no veo muy bien cuál podría ser la explicación completa.

(Pregunta inspirada en ¿Por qué mi ejemplo python / numpy es más rápido que la implementación C pura? )

EDITAR:

Aquí está el ensamblaje generado para v1 :

        movl    $8192, %ebp
        pushq   %rbx
LCFI1:
        subq    $8, %rsp
LCFI2:
        .align 4
L2:
        movl    $100000, %ebx
        movss   LC0(%rip), %xmm0
        jmp     L5
        .align 4
L3:
        call    _sinf
L5:
        subl    $1, %ebx
        jne     L3
        subl    $1, %ebp
        .p2align 4,,2
        jne     L2

y para v2 :

        movl    $100000, %r14d
        .align 4
L8:
        xorl    %ebx, %ebx
        .align 4
L9:
        movss   (%r12,%rbx), %xmm0
        call    _sinf
        movss   %xmm0, (%r12,%rbx)
        addq    $4, %rbx
        cmpq    $32768, %rbx
        jne     L9
        subl    $1, %r14d
        jne     L8

Answer 1

En el primer ejemplo, ejecuta 100000 bucles de sin, 8192 veces.

En el segundo ejemplo, ejecuta 8192 bucles de sin, 100000 veces.

Aparte de eso y almacenar el resultado de manera diferente, no veo ninguna diferencia.

Sin embargo, lo que hace la diferencia es que la entrada se cambia para cada ciclo en el segundo caso. Entonces sospecho que lo que sucede es que el valor del pecado, en ciertos momentos del ciclo, es mucho más fácil de calcular. Y eso puede hacer una gran diferencia. Calcular el pecado no es del todo trivial, y es un cálculo en serie que gira hasta que se alcanza la condición de salida.

Answer 2

Ignora la estructura de bucles todos juntos, y solo piensa en la secuencia de llamadas al sin . v1 hace lo siguiente:

x <-- sin(x)
x <-- sin(x)
x <-- sin(x)
...

es decir, cada cómputo de sin( ) no puede comenzar hasta que el resultado de la llamada previa esté disponible; debe esperar la totalidad del cálculo anterior. Esto significa que para N llamadas a sin , el tiempo total requerido es 819200000 veces la latencia de una única evaluación de sin .

En v2 , por el contrario, haces lo siguiente:

x[0] <-- sin(x[0])
x[1] <-- sin(x[1])
x[2] <-- sin(x[2])
...

note que cada llamada al sin no depende de la llamada previa. Efectivamente, las llamadas al sin son todas independientes, y el procesador puede comenzar en cada una de ellas tan pronto como esté disponible el registro necesario y los recursos de la ALU (sin esperar a que se complete el cálculo anterior). Por lo tanto, el tiempo requerido es una función del rendimiento de la función sin, no la latencia, por lo que v2 puede terminar en un tiempo significativamente menor.

También debo señalar que DeadMG tiene razón en que v1 y v2 son formalmente equivalentes, y en un mundo perfecto el compilador los optimizaría a ambos en una sola cadena de 100000 evaluaciones de errores (o simplemente evaluando el resultado en tiempo de compilación). Tristemente, vivimos en un mundo imperfecto.