(void *) blog

Posted on by fortytwo_de


El post de hoy va a ser más denso que los demás. Avisados estáis.

El programa más simple

… más que Hello World

int main() {
    return 0;
}

Probablemente sea el programa más simple que se puede escribir en C sin que salten errores de compilación. Pero en realidad, este programa ya hace muchas cosas.

Para entender mejor lo que hace, lo voy a destripar con -S en gcc.

$ gcc simple.c -S

Y el resultado es bastante largo, pero voy a omitir las partes que pertenencen a la gestión del stack frame y todas estas cosas que los sistemas operativos modernos tienen.

_main:
Leh_func_begin1:
    pushq   %rbp
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    movl    $0, -8(%rbp)
    movl    -8(%rbp), %eax
    movl    %eax, -4(%rbp)
    movl    -4(%rbp), %eax
    popq    %rbp
    ret
Leh_func_end1:

Unas cuantas cosas que conviene saber:

  • pushq añade un quad al stack.
  • %rbp es un registro de la CPU que se utiliza para almacenar el puntero del frame. Un stack frame contiene información sobre la función.
  • movq a, b mueve información del registro b al registro a. Equivalente a b = a.
  • popq coge el último quad pusheado al stack y lo guarda en el registro que se le pasa como parámetro.
  • ret tiene una funcionalidad similar a hacer jmp `popq`. Es decir, salta a la dirección de memoria contenida en el último elemento del stack.

En este ejemplo, se guarda el valor $0 (es decir, 0) en una dirección relativa a %rbp, con 8 bytes de diferencia.

Es decir, se está almacenando una variable de tipo long, que ocupan 8 bytes.

Declarando una variable

En este ejemplo, sólo añado la declaración de una variable.

int main() {
    int a = 1337;
    return 0;
}

El equivalente en ensamblador:

_main:
Leh_func_begin1:
        pushq   %rbp
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    movl    $1337, -12(%rbp)
    movl    $0, -8(%rbp)
    movl    -8(%rbp), %eax
    movl    %eax, -4(%rbp)
    movl    -4(%rbp), %eax
    popq    %rbp
    ret
Leh_func_end1:

No ha cambiado mucho, excepto esta línea:

    movl    $1337, -12(%rbp)

Esto demuestra que GCC se encarga de asignar los espacios en memoria que van a utilizar las variables: incluso antes de definir el espacio para el valor de retorno (0, en el ejemplo), GCC ya sabe que los primeros 8 bytes van a estar ocupados.

Como un int sólo ocupa 4 bytes, se le asigna la dirección en memoria -12(%rbp).

Bucles

… o la importancia de precalcular los valores para evitar ciclos innecesarios

Ahora que se conoce un poco mejor cómo funciona internamente un programa, voy a explicar la importancia de precalcular los valores en la cláusula condicional de un bucle.

El ejemplo más sencillo posible de un bucle for:

int main(int argc, char** argv) {
    int i = 0;
    for(i = 0; i < 10; i++) {
            // do stuff
    }   
}

En ensamblador:

_main:
Leh_func_begin1:
    pushq   %rbp
Ltmp0:
    movq    %rsp, %rbp
Ltmp1:
    movl    %edi, -4(%rbp)
    movq    %rsi, -16(%rbp)
    movl    $0, -24(%rbp)
    movl    $0, -24(%rbp)
    jmp     LBB1_2
LBB1_1:
    movl    -24(%rbp), %eax
    addl    $1, %eax
    movl    %eax, -24(%rbp)
LBB1_2:
    movl    -24(%rbp), %eax
    cmpl    $9, %eax
    jle     LBB1_1
    movl    -20(%rbp), %eax
    popq    %rbp
    ret
Leh_func_end1:

Aquí empiezan a aparecer cosas más interesantes: tenemos labels nuevos, que son prácticamente equivalentes a las cláusulas del for.

Primero, se declara i = 0 como int:

movl    $0, -24(%rbp)

nota: esta línea aparece dos veces porque en el código también la he escrito dos veces, pero se podría optimizar

Luego, se salta a la cláusula de comparación, para ver si el código del bucle debe ejecutarse.

jmp     LBB1_2

El label LBB1_1 es el equivalente a i++:

LBB1_1:
    movl    -24(%rbp), %eax
    addl    $1, %eax
    movl    %eax, -24(%rbp)

Aquí están pasando varias cosas:

  • Se mueve el contenido de la variable i al registro %eax.
  • Se suma 1 ($1) al registro %eax
  • Se asigna el valor del registro %eax a la variable i.

Y por último, el label que determina si el código del bucle se debe ejecutar. Es decir, el equivalente a i < 10.

LBB1_2:
    movl    -24(%rbp), %eax
    cmpl    $9, %eax
    jle     LBB1_1
  • Se mueve el valor de la variable i al registro %eax
  • Se compara $9 con %eax.
  • Se salta (jump, J) al label LBB1_2 si %eax es menor (less, L) o igual (equal, E) que el valor comparado.

Precisamente por esta sección de código es importante precalcular los valores de comparación en vez de calcularlos cada vez en el bucle.

Calcular los valores en el bucle vs. precalcularlos

En este ejemplo, el bucle va a ejecutarse si i es menor que 102. Tengo que llevarlo a una función separada porque si pongo i < 10*10, GCC lo va a optimizar automáticamente.

int max() {
    return 10*10;
}

int main(int argc, char** argv) {
        int i = 0;
        for(i = 0; i < max(); i++) {
                // do stuff
        }
}

Ahora, la cláusula de comparación del bucle cuesta más:

LBB2_2:
    callq   _max
    movl    %eax, %ecx
    movl    -24(%rbp), %edx
    cmpl    %edx, %ecx
    jg      LBB2_1

Es importante entender que el resultado de una función, por lo general, se guarda en el registro %eax.

Aquí, el label de comparación guarda el resultado de la función max en %ecx, para compararlo luego.

Después se guarda el contenido de la variable i (es decir, -24(%rbp)) en el registro %ecx, y luego se comparan.

Y ahora, se puede ver la ventaja de precalcular el resultado de la función max en el siguiente ejemplo:

int max() {
    return 10*10;
}

int main(int argc, char** argv) {
    int i = 0, n = max();
    for(i = 0; i < n; i++) {
            // do stuff
    }
}

Primero se declara la variable ncomo el resultado de la función max:

    callq   _max
    movl    %eax, %ecx
    movl    %ecx, -28(%rbp)

Y luego, en el label de comparación, sólo se tienen que comparar esos dos valores:

LBB2_2:
    movl    -24(%rbp), %eax
    movl    -28(%rbp), %ecx
    cmpl    %ecx, %eax
    jl      LBB2_1

Que, obviamente, es mucho más eficiente que llamar todas las veces a la función max().

Posted on by fortytwo_de | Posted in ASM, C, Programación


4 Responses to Optimización de bucles

  1. Dirbaio says:


    Optimizaciones de bajo nivel, hmm?

    Si compilas con la opción -O3 en GCC, el compilador ya hace muchas optimizaciones por si solo.
    Por ejemplo, este caso:
    http://hastebin.com/cetabixaci.mel

    La función devuelve un valor determinado. Sin optimización, GCC compila el for y todo, pero con optimización, se da cuenta de que estás calculando un valor constante y lo devuelve literalmente. Mola.

    Si realmente quieres optimizar tu codigo, es mejor mirar el codigo que GCC genera con -O3


    • fortytwo_de says:


      La opción -O3 de GCC es muy potente y hace cosas bastante complicadas. Concretamente, en los bucles, si activas el switch -funroll-loops probablemente sería hasta capaz de decir “vale, esta función siempre va a devolver 100, en vez de hacer comparaciones y saltos condicionales que generalmente son bastante caros, voy a repetir el código del bucle 100 veces”.

      De hecho, -O3 es tan agresivo que si en el código del bucle no pongo nada se carga directamente todo el bucle. Ejemplo: http://hastebin.com/lopusurico.asm

      Aquí he tenido que “hacer algo” (devolverlo (sí, ya sé que main no puede devolver un valor cualquiera)) con el valor de x para que GCC no lo optimice. Lo dicho, es bastante agresivo :P


  2. Morris says:


    I see you share interesting things here, you can earn some additional
    cash, your website has huge potential, for the monetizing
    method, just type in google – K2 advices how to monetize a website


  3. Mel says:


    I read a lot of interesting content here. Probably you
    spend a lot of time writing, i know how to save you a lot
    of time, there is an online tool that creates unique, google friendly articles in seconds, just type in google
    - k2seotips unlimited content


Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>