Mudança da classe de complexidade através da otimização do compilador?

Estou procurando um exemplo em que um algoritmo aparentemente está alterando sua classe de complexidade devido a estratégias de otimização de compilador e / ou processador.

Vamos usar um programa simples que imprima o quadrado de um número digitado na linha 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 você pode ver, este é um cálculo de O (n), repetindo repetidamente.

Ao compilar isso, gcc -Sobtém-se um segmento que é:

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

Neste você pode ver a adição sendo feita, uma comparação e um retorno ao loop.

Fazendo a compilação com gcc -S -O3para obter otimizações do segmento entre as chamadas para 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

Agora, pode-se ver que ele não tem loop e, além disso, não adiciona. Em vez disso, há uma chamada na imullqual multiplica o número por si só.

O compilador reconheceu um loop e o operador matemático interno e o substituiu pelo cálculo apropriado.

Observe que isso incluiu uma chamada atoipara obter o número. Quando o número já existe no código, o complier pré-calcula o valor em vez de fazer chamadas reais, como demonstrado em uma comparação entre o desempenho do sqrt em C # e C em que sqrt(2)(uma constante) foi somada em um loop 1.000.000 de vezes.

A otimização de chamada de cauda pode reduzir a complexidade do espaço. Por exemplo, sem o TCO, essa implementação recursiva de um whileloop tem uma complexidade de espaço no pior caso Ο(#iterations), enquanto que com o TCO tem uma complexidade de espaço no pior caso Ο(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); });

Isso nem precisa de TCO geral, apenas um caso especial muito estreito, a eliminação da recursão direta da cauda.

O que seria muito interessante, porém, é que a otimização do compilador não apenas altera a classe de complexidade, mas na verdade altera completamente o algoritmo.

O Glorioso Glasgow Haskell Compiler às vezes faz isso, mas isso não é realmente o que eu estou falando, isso é mais como fazer batota. O GHC possui uma linguagem de correspondência de padrões simples que permite ao desenvolvedor da biblioteca detectar alguns padrões de código simples e substituí-los por códigos diferentes. Ea implementação GHC da biblioteca padrão Haskell não conter algumas dessas anotações, para que usos específicos de funções específicas que são conhecidos por ser ineficiente são reescritas em versões mais eficientes.

No entanto, essas traduções são escritas por seres humanos e para casos específicos, é por isso que considero trapacear.

Um supercompilador pode ser capaz de alterar o algoritmo sem entrada humana, mas no AFAIK nenhum supercompilador em nível de produção foi criado.

Um compilador que está ciente de que a linguagem está usando big-num fazendo redução de força (substituindo multiplicações pelo índice de um loop por uma adição) alteraria a complexidade dessa multiplicação de O (n log n) na melhor das hipóteses para O (n) .