¿Cambio de la clase de complejidad a través de la optimización del compilador?

7

Estoy buscando un ejemplo donde un algoritmo aparentemente esté cambiando su clase de complejidad debido a las estrategias de optimización del compilador y / o procesador.

    
pregunta Lorenz Lo Sauer 26.05.2013 - 15:13

3 respuestas

4

Tomemos un programa simple que imprime el cuadrado de un número ingresado en la línea de comando.

#include <stdio.h>

int main(int argc, char **argv) {
    int num = atoi(argv[1]);
    printf("%d\n",num);
    int i = 0;
    int total = 0;
    for(i = 0; i < num; i++) {
        total += num;
    }
    printf("%d\n",total);
    return 0;
}

Como puede ver, este es un cálculo O (n) que se repite una y otra vez.

Al compilar esto con gcc -S one se obtiene un segmento que es:

LBB1_1:
        movl    -36(%rbp), %eax
        movl    -28(%rbp), %ecx
        addl    %ecx, %eax
        movl    %eax, -36(%rbp)
        movl    -32(%rbp), %eax
        addl    $1, %eax
        movl    %eax, -32(%rbp)
LBB1_2:
        movl    -32(%rbp), %eax
        movl    -28(%rbp), %ecx
        cmpl    %ecx, %eax
        jl      LBB1_1

En esto puedes ver el complemento que se está realizando, una comparación y un salto hacia atrás para el bucle.

Haciendo la compilación con gcc -S -O3 para obtener optimizaciones del segmento entre las llamadas a printf:

        callq   _printf
        testl   %ebx, %ebx
        jg      LBB1_2
        xorl    %ebx, %ebx
        jmp     LBB1_3
LBB1_2:
        imull   %ebx, %ebx
LBB1_3:
        movl    %ebx, %esi
        leaq    L_.str(%rip), %rdi
        xorb    %al, %al
        callq   _printf

Ahora se puede ver que no tiene bucle y, además, no se agrega. En su lugar, hay una llamada a imull que multiplica el número por sí mismo.

El compilador ha reconocido el bucle y el operador matemático en el interior y lo ha reemplazado por el cálculo adecuado.

Tenga en cuenta que esto incluía una llamada a atoi para obtener el número. Cuando ya exista el número en el código, el compilador calculará previamente el valor en lugar de hacer llamadas reales como se muestra en una comparación entre el rendimiento de sqrt en C # y C , donde sqrt(2) (una constante) se estaba sumando en un bucle 1,000,000 de veces.

    
respondido por el user40980 26.05.2013 - 23:29
7

La optimización de llamadas de cola puede reducir la complejidad del espacio. Por ejemplo, sin TCO, esta implementación recursiva de un bucle while tiene una complejidad de espacio en el peor de los casos Ο(#iterations) , mientras que con TCO tiene una complejidad de espacio en el peor de los casos de Ο(1) :

// This is Scala, but it works the same way in every other language.
def loop(cond: => Boolean)(body: => Unit): Unit = if (cond) { body; loop(cond)(body) }

var i = 0
loop { i < 3 } { i += 1; println(i) }
// 1
// 2
// 3

// E.g. ECMAScript:
function loop(cond, body) {
    if (cond()) { body(); loop(cond, body); };
};

var i = 0;
loop(function { return i < 3; }, function { i++; print(i); });

Esto ni siquiera necesita un TCO general, solo necesita un caso especial muy estrecho, a saber, la eliminación de la recursión directa de la cola.

Sin embargo,

lo que sería muy interesante es que la optimización de un compilador no solo cambia la clase de complejidad, sino que en realidad cambia el algoritmo por completo.

El Glorioso Compilador de Glasgow Haskell a veces hace esto, pero eso no es realmente de lo que estoy hablando, es más como hacer trampa. GHC tiene un lenguaje de coincidencia de patrones simple que permite al desarrollador de la biblioteca detectar algunos patrones de código simples y reemplazarlos con códigos diferentes. Y la implementación de GHC de la biblioteca estándar de Haskell contiene algunas de esas anotaciones, de modo que los usos específicos de funciones específicas que se sabe que son ineficientes se reescriben en versiones más eficientes.

Sin embargo, estas traducciones están escritas por humanos, y están escritas para casos específicos, por eso considero que el engaño.

Un Supercompilador puede ser capaz de cambiar el algoritmo sin entrada humana, pero AFAIK nunca se ha creado un supercompilador de nivel de producción.

    
respondido por el Jörg W Mittag 26.05.2013 - 17:50
0

Un compilador que es consciente de que el lenguaje está usando big-num haciendo reducción de la fuerza (reemplazando las multiplicaciones por el índice de un bucle por una adición) cambiaría la complejidad de esa multiplicación de O (n log n) en el mejor de los casos (n).

    
respondido por el AProgrammer 26.05.2013 - 19:32

Lea otras preguntas en las etiquetas