Optimización de código C

Para una tarea de un curso llamado Informática de alto rendimiento, necesité optimizar el siguiente fragmento de código:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            if (i > j){
               y = y + 8*(i-j);
            }else{
               y = y + 8*(j-i);
            }
        }
    }
    return x;
}

Usando algunas recomendaciones, logré optimizar el código (o al menos eso creo), como:

1. Propagación constante
2. Simplificación Algebraica
3. Propagación de copias
4. Eliminación de subexpresiones comunes
5. Eliminación de código muerto
6. Eliminación invariable de bucle
7. cambios bit a bit en lugar de multiplicación, ya que son menos costosos.

Aquí está mi código:

int foobar(int a, int b, int N) {

    int i, j, x, y, t;
    x = 0;
    y = 0;
    for (i = 0; i <= N; i++) {
        t = i + 512;
        for (j = i + 1; j <= N; j++) {
            x = x + ((i<<3) + (j<<2))*t;
        }
    }
    return x;
}

Según mi instructor, un código de instrucciones bien optimizado debe tener menos o menos instrucciones a nivel de lenguaje ensamblador. Y por lo tanto, se deben ejecutar las instrucciones en menos tiempo que el código original, es decir, los cálculos se hacen con:

tiempo de ejecución = número de instrucciones * ciclos por instrucción

Cuando genero código ensamblador usando el comando: gcc -o code_opt.s -S foobar.c,

el código generado tiene muchas más líneas que el original a pesar de haber hecho algunas optimizaciones, y el tiempo de ejecución es menor, pero no tanto como en el código original. ¿Qué estoy haciendo mal?

No pegue el código ensamblador ya que ambos son muy extensos. Así que estoy llamando a la función “foobar” en la principal y estoy midiendo el tiempo de ejecución usando el comando de tiempo en Linux

int main () {
    int a,b,N;

    scanf ("%d %d %d",&a,&b,&N);
    printf ("%d\n",foobar (a,b,N));
    return 0;
}

Inicialmente:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
        if (i > j){
           y = y + 8*(i-j);
        }else{
           y = y + 8*(j-i);
        }
    }
}

eliminando y cálculos:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 4*(2*i+j)*(i+2*k);
    }
}

Terrible i, j, k:

for (i = 0; i <= N; i++) {
    for (j = i + 1; j <= N; j++) {
        x = x + 8*i*i + 16*i*k ;                // multiple of  1  (no j)
        x = x + (4*i + 8*k)*j ;                 // multiple of  j
    }
}

Moviéndolos externamente (y eliminando el bucle que se ejecuta N-i veces):

for (i = 0; i <= N; i++) {
    x = x + (8*i*i + 16*i*k) * (N-i) ;
    x = x + (4*i + 8*k) * ((N*N+N)/2 - (i*i+i)/2) ;
}

reescritura:

for (i = 0; i <= N; i++) {
    x = x +         ( 8*k*(N*N+N)/2 ) ;
    x = x +   i   * ( 16*k*N + 4*(N*N+N)/2 + 8*k*(-1/2) ) ;
    x = x +  i*i  * ( 8*N + 16*k*(-1) + 4*(-1/2) + 8*k*(-1/2) );
    x = x + i*i*i * ( 8*(-1) + 4*(-1/2) ) ;
}

Reescritura – recálculo:

for (i = 0; i <= N; i++) {
    x = x + 4*k*(N*N+N) ;                            // multiple of 1
    x = x +   i   * ( 16*k*N + 2*(N*N+N) - 4*k ) ;   // multiple of i
    x = x +  i*i  * ( 8*N - 20*k - 2 ) ;             // multiple of i^2
    x = x + i*i*i * ( -10 ) ;                        // multiple of i^3
}

Otro movimiento a externo (y eliminación del bucle i):

x = x + ( 4*k*(N*N+N) )              * (N+1) ;
x = x + ( 16*k*N + 2*(N*N+N) - 4*k ) * ((N*(N+1))/2) ;
x = x + ( 8*N - 20*k - 2 )           * ((N*(N+1)*(2*N+1))/6);
x = x + (-10)                        * ((N*N*(N+1)*(N+1))/4) ;

Ambas eliminaciones de bucle anteriores utilizan el suma fórmulas:

Suma(1, i = 0..n) = n+1
Suma(yo¹i = 0..n) = n(n + 1)/2
Suma(yo²i = 0..n) = n(n + 1)(2n + 1)/6
Suma(yo³i = 0..n) = n²(n + 1)²/4

y no afecta el resultado final del código – eliminado:

int foobar(int a, int b, int N)
{
    int i, j, k, x, y;
    x = 0;
    //y = 0;
    k = 256;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*k);
            //if (i > j){
            //   y = y + 8*(i-j);
            //}else{
            //   y = y + 8*(j-i);
            //}
        }
    }
    return x;
}

k es simplemente una constante:

int foobar(int a, int b, int N)
{
    int i, j, x;
    x = 0;
    for (i = 0; i <= N; i++) {
        for (j = i + 1; j <= N; j++) {
            x = x + 4*(2*i+j)*(i+2*256);
        }
    }
    return x;
}

La expresión interna se puede transformar en: x += 8*i*i + 4096*i + 4*i*j + 2048*j. Usa las matemáticas para empujarlos a todos al bucle exterior: x += 8*i*i*(N-i) + 4096*i*(N-i) + 2*i*(N-i)*(N+i+1) + 1024*(N-i)*(N+i+1).

Puede expandir la expresión anterior y aplicar formula suma de cuadrados y suma de cubos para obtener una expresión de forma cerrada, que debería ejecutarse más rápido que el bucle doblemente anidado. Te lo dejo como ejercicio. Como resultado, i y j también será eliminado.

a y b también debe eliminarse si es posible, ya que a y b se proporcionan como argumento pero nunca se usan en su código.

Fórmula de suma de cuadrados y suma de cubos:

• Suma(x²x = 1..n) = n(n + 1)(2n + 1)/6
• Suma(x³x = 1..n) = n²(n + 1)²/4

Esta función es equivalente a la siguiente fórmula, que contiene solo 4 multiplicaciones de enterosy 1 división entera:

x = N * (N + 1) * (N * (7 * N + 8187) - 2050) / 6;

Para obtener esto, simplemente escribí la suma calculada por sus bucles anidados en Wolfram Alpha:

sum (sum (8*i*i+4096*i+4*i*j+2048*j), j=i+1..N), i=0..N

Aquí es el enlace directo a la solución. Piense antes de codificar. A veces, su cerebro puede optimizar el código mejor que cualquier compilador.

Analizando brevemente la primera rutina, lo primero que notará es que las expresiones que involucran “y” no se usan y pueden eliminarse (como lo hizo usted). Esto permite además eliminar el if/else (como lo hizo).

Lo que queda son los dos for bucles y la expresión desordenada. Factorizando las partes de esa expresión que no dependen de j es el siguiente paso. Eliminaste una de esas expresiones, pero (i<<3) (es decir, i * 8) permanece en el bucle interno y puede eliminarse.

La respuesta de Pascal me recordó que puedes usar una optimización de zancada en bucle. Primer paso (i<<3) * t fuera del bucle interno (llámelo i1), luego calcule, al inicializar el ciclo, un valor j1 eso es igual (i<<2) * t. En cada incremento de iteración j1 por 4 * t (que es una constante precalculada). Reemplace su expresión interna con x = x + i1 + j1;.

Uno sospecha que puede haber alguna forma de combinar los dos bucles en uno, con un paso, pero no lo veo de improviso.

Algunas otras cosas que puedo ver. no necesitas ypara que pueda eliminar su declaración e inicialización.

Además, los valores pasados ​​para a y b en realidad no se usan, por lo que podría usarlas como variables locales en lugar de x y t.

Además, en lugar de agregar i a 512 cada vez que pasa puede notar que t comienza en 512 y se incrementa en 1 en cada iteración.

int foobar(int a, int b, int N) {
    int i, j;
    a = 0;
    b = 512;
    for (i = 0; i <= N; i++, b++) {
        for (j = i + 1; j <= N; j++) {
            a = a + ((i<<3) + (j<<2))*b;
        }
    }
    return a;
}

Una vez que llegue a este punto, también puede observar que, además de inicializar j, i y j solo se usan en un solo múltiplo cada uno – i<<3 y j<<2. Podemos codificar esto directamente en la lógica del bucle, así:

int foobar(int a, int b, int N) {
    int i, j, iLimit, jLimit;
    a = 0;
    b = 512;
    iLimit = N << 3;
    jLimit = N << 2;
    for (i = 0; i <= iLimit; i+=8) {
        for (j = i >> 1 + 4; j <= jLimit; j+=4) {
            a = a + (i + j)*b;
        }
        b++;
    }
    return a;
}

OK… así que aquí está mi solución, junto con comentarios en línea para explicar lo que hice y cómo.

int foobar(int N)
{ // We eliminate unused arguments 
    int x = 0, i = 0, i2 = 0, j, k, z;

    // We only iterate up to N on the outer loop, since the
    // last iteration doesn't do anything useful. Also we keep
    // track of '2*i' (which is used throughout the code) by a 
    // second variable 'i2' which we increment by two in every
    // iteration, essentially converting multiplication into addition.
    while(i < N) 
    {           
        // We hoist the calculation '4 * (i+2*k)' out of the loop
        // since k is a literal constant and 'i' is a constant during
        // the inner loop. We could convert the multiplication by 2
        // into a left shift, but hey, let's not go *crazy*! 
        //
        //  (4 * (i+2*k))         <=>
        //  (4 * i) + (4 * 2 * k) <=>
        //  (2 * i2) + (8 * k)    <=>
        //  (2 * i2) + (8 * 512)  <=>
        //  (2 * i2) + 2048

        k = (2 * i2) + 2048;

        // We have now converted the expression:
        //      x = x + 4*(2*i+j)*(i+2*k);
        //
        // into the expression:
        //      x = x + (i2 + j) * k;
        //
        // Counterintuively we now *expand* the formula into:
        //      x = x + (i2 * k) + (j * k);
        //
        // Now observe that (i2 * k) is a constant inside the inner
        // loop which we can calculate only once here. Also observe
        // that is simply added into x a total (N - i) times, so 
        // we take advantange of the abelian nature of addition
        // to hoist it completely out of the loop

        x = x + (i2 * k) * (N - i);

        // Observe that inside this loop we calculate (j * k) repeatedly, 
        // and that j is just an increasing counter. So now instead of
        // doing numerous multiplications, let's break the operation into
        // two parts: a multiplication, which we hoist out of the inner 
        // loop and additions which we continue performing in the inner 
        // loop.

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

El código, sin ninguna de las explicaciones, se reduce a esto:

int foobar(int N)
{
    int x = 0, i = 0, i2 = 0, j, k, z;

    while(i < N) 
    {                   
        k = (2 * i2) + 2048;

        x = x + (i2 * k) * (N - i);

        z = i * k;

        for (j = i + 1; j <= N; j++) 
        {
            z = z + k;          
            x = x + z;      
        }

        i++;
        i2 += 2;
    }   

    return x;
}

Espero que esto ayude.

int foobar(int N) //Para evitar pasar un argumento sin usar

{

int i, j, x=0;   //Remove unuseful variable, operation so save stack and Machine cycle

for (i = N; i--; )               //Don't check unnecessary comparison condition 

   for (j = N+1; --j>i; )

     x += (((i<<1)+j)*(i+512)<<2);  //Save Machine cycle ,Use shift instead of Multiply

return x;

}