Cambiamento della classe di complessità attraverso l'ottimizzazione del compilatore?

Consente di eseguire un semplice programma che stampa il quadrato di un numero immesso sulla riga di 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;
}

Come puoi vedere, questo è un calcolo O (n), che si ripete ripetutamente.

Compilando questo con gcc -S si ottiene un segmento che è:

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

In questo puoi vedere l'aggiunta in corso, un confronto e un salto indietro per il ciclo.

Esegui la compilazione con gcc -S -O3 per ottenere le ottimizzazioni del segmento tra le chiamate 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

Ora è possibile vedere che non ha loop e inoltre non aggiunge. Invece c'è una chiamata a imull che moltiplica il numero di per sé.

Il compilatore ha riconosciuto un loop e l'operatore matematico all'interno e lo ha sostituito con il calcolo corretto.

Nota che questo includeva una chiamata a atoi per ottenere il numero. Quando il numero esiste già nel codice, il compilatore pre-calcola il valore anziché effettuare chiamate effettive come dimostrato in un confronto tra le prestazioni di sqrt in C # e C in cui sqrt(2) (una costante) veniva sommata in un ciclo 1.000.000 di volte.

L'ottimizzazione delle chiamate tail può ridurre la complessità dello spazio. Ad esempio, senza TCO, questa implementazione ricorsiva di un ciclo while ha una complessità dello spazio nel caso peggiore Ο(#iterations) , mentre con TCO ha una complessità spaziale nel caso peggiore di Ο(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); });

Questo non ha nemmeno bisogno del TCO generale, richiede solo un caso speciale molto ristretto, vale a dire l'eliminazione della ricorsione diretta della coda.

Tuttavia, ciò che sarebbe molto interessante, è dove l'ottimizzazione del compilatore non cambia solo la classe di complessità, ma in realtà cambia completamente l'algoritmo.

Il Glorious Glasgow Haskell Compiler a volte lo fa, ma non è veramente di cosa sto parlando, è più come barare. GHC ha un semplice Pattern Matching Language che consente allo sviluppatore della libreria di rilevare alcuni semplici schemi di codice e sostituirli con codice diverso. E l'implementazione GHC della libreria standard Haskell fa contiene alcune di quelle annotazioni, in modo che usi specifici di funzioni specifiche che sono noti per essere inefficienti vengano riscritti in versioni più efficienti.

Tuttavia, queste traduzioni sono scritte da umani, e sono scritte per casi specifici, ecco perché considero questo imbroglio.

Un Supercompiler potrebbe essere in grado di modificare l'algoritmo senza input umani, ma AFAIK non è mai stato realizzato un supercompiler di livello produttivo.

Un compilatore che è consapevole del fatto che la lingua sta usando il big-num facendo riduzione della forza (sostituendo le moltiplicazioni per l'indice di un ciclo con un'aggiunta) cambierebbe la complessità di quella moltiplicazione da O (n log n) nel migliore dei casi a O (n).