optimizar - optimizacion de codigo en c++

Optimización de código C

Question

Para una asignación de un curso llamado High Performance Computing, tuve que 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 la copia
4. Eliminación de subexpresiones comunes
5. Eliminación del código muerto
6. Eliminación de invariantes en bucle
7. Cambios en el 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;
}

De acuerdo con mi instructor, las instrucciones de código bien optimizadas deberían tener instrucciones más económicas o menos costosas en el lenguaje de ensamblador. Y, por lo tanto, deben ejecutarse, las instrucciones en menos tiempo que el código original, es decir, los cálculos se realizan con:

tiempo de ejecución = cuenta de instrucción * ciclos por instrucción

Cuando genero un código de ensamblaje mediante 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 realizado 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 de ensamblaje ya que ambos son muy extensos. Así que estoy llamando a la función "foobar" en la pantalla principal y estoy midiendo el tiempo de ejecución usando el comando time en linux

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

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

Answer 1

Algunas otras cosas que puedo ver. No necesita y , por lo que puede eliminar su declaración e inicialización.

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

Además, en lugar de agregar i a 512 cada vez, puede observar que t comienza en 512 e 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, aparte de inicializar j , i y j solo se utilizan en un solo mutiple cada uno - i<<3 y j<<2 . Podemos codificar esto directamente en la lógica del bucle, por lo tanto:

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;
}

Answer 2

Escaneando brevemente la primera rutina, lo primero que notará es que las expresiones que implican "y" están completamente sin usar y se pueden eliminar (como lo hizo). Esto permite además eliminar el if / else (como lo hiciste).

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

La respuesta de Pascal me recordó que puede utilizar una optimización de zancada de bucle. Primero mueva (i<<3) * t fuera del bucle interno ( i1 ), luego calcule, al inicializar el bucle, un valor j1 que sea igual a (i<<2) * t . En cada incremento de iteración j1 por 4 * t (que es una constante calculada previamente). Reemplaza tu expresión interna con x = x + i1 + j1; .

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

Answer 3

Esta función es equivalente con la siguiente fórmula, que contiene solo 4 multiplicaciones de enteros y 1 división de enteros :

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

Para obtener esto, simplemente escribí la suma calculada por tus 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í está el enlace directo a la solución. Piensa antes de codificar. A veces tu cerebro puede optimizar el código mejor que cualquier compilador.

Answer 4

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);
    }
}

Dividiendo 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 ejecuta Ni 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 las fórmulas de summation :

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

Answer 5

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.

Answer 6

int foobar (int N) // Para evitar la desuso de pasar el argumento

{

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;

}

Answer 7

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 hacia el bucle externo: x += 8*i*i*(Ni) + 4096*i*(Ni) + 2*i*(Ni)*(N+i+1) + 1024*(Ni)*(N+i+1) .

Puede expandir la expresión anterior y aplicar la fórmula de 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án eliminados.

a y b también deben eliminarse si es posible, ya que a y b se suministran como argumentos pero nunca se utilizan 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) 2/4