Änderung der Komplexitätsklasse durch Compileroptimierung?

8

Ich suche nach einem Beispiel, bei dem ein Algorithmus anscheinend seine Komplexitätsklasse aufgrund von Compiler- und / oder Prozessoroptimierungsstrategien ändert.

Lorenz Lo Sauer
quelle
2
Dies könnte definitiv für die Komplexität des Weltraums passieren, wenn beispielsweise die Schwanzrekursion entfernt wird.
Eliot Ball
4
Einfach: Eine leere Schleife O (n) kann zu O (1) optimiert werden: siehe diesen SO-Beitrag: stackoverflow.com/questions/10300253/…
Doc Brown
Es ist einfacher Beispiele in Haskell zu finden, obwohl es nicht wirklich Optimierung ist - nur die faule Semantik der Sprache , die die möglicherweise großen Teile des Codes für Funktionen bedeuten , die wurden nicht ausgewertet werden , da die Ergebnisse genannt wird , werden nie benutzt. In Haskell ist es sogar üblich, unbegrenzt rekursive Funktionen zu definieren, die unendliche Listen zurückgeben. Solange Sie nur einen endlichen Teil der Liste verwenden, wird immer nur ein endlicher Betrag der Rekursion ausgewertet (seltsamerweise möglicherweise nicht rekursiv) und nur dieser endliche Teil der Liste berechnet.
Steve314
1
@ Steve314: Ich glaube, es gab ein Beispiel dafür im Computersprachen-Benchmark-Spiel, bei dem die Haskell-Implementierung 10-mal schneller war als die C-Implementierung, da die Ergebnisse des Benchmarks und damit im Wesentlichen das gesamte Haskell-Programm nie gedruckt wurden zusammengestellt bisint main(void) { exit(0); };
Jörg W Mittag
@ Jörg - es würde mich nicht überraschen, aber ich denke, die Haskell-Entwickler haben geschummelt. Sie können in Haskell erzwingen, dass etwas eifrig evaluiert wird, wenn dies erforderlich ist, und seltsamerweise dient es hauptsächlich der Optimierung. Eine strikte / eifrige Evaluierung ist oft viel schneller als faul, da sie den Aufwand für die Verschiebung der Evaluierung vermeidet. Ein guter Haskell-Compiler fängt viel davon selbst mithilfe der "Strenge-Analyse" ab, aber es gibt Zeiten, in denen Sie das Problem erzwingen müssen.
Steve314

Antworten:

4

Nehmen wir ein einfaches Programm, das das Quadrat einer in der Befehlszeile eingegebenen Zahl druckt.

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

Wie Sie sehen können, handelt es sich um eine O (n) -Berechnung, die immer wieder wiederholt wird.

Wenn Sie dies mit gcc -Seinem kompilieren, erhalten Sie ein Segment, das ist:

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

Hier sehen Sie, wie das Hinzufügen durchgeführt wird, ein Vergleich und ein Rücksprung für die Schleife.

Durchführen der Kompilierung mit gcc -S -O3, um Optimierungen des Segments zwischen den Aufrufen von printf zu erhalten:

        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

Man kann jetzt sehen, stattdessen hat es keine Schleife und außerdem keine Adds. Stattdessen gibt es einen Anruf, bei imulldem die Zahl mit sich selbst multipliziert wird.

Der Compiler hat die Schleife und den darin enthaltenen mathematischen Operator erkannt und durch die richtige Berechnung ersetzt.


Beachten Sie, dass dies einen Anruf atoizum Abrufen der Nummer beinhaltete. Wenn die Nummer bereits im Code vorhanden ist, berechnet der Complier den Wert vor, anstatt tatsächliche Anrufe zu tätigen, wie in einem Vergleich zwischen der Leistung von sqrt in C # und C gezeigt, bei der sqrt(2)(eine Konstante) 1.000.000 Mal über eine Schleife summiert wurde.

Gemeinschaft
quelle
7

Die Tail Call-Optimierung kann die Speicherplatzkomplexität verringern. Ohne TCO weist diese rekursive Implementierung einer whileSchleife beispielsweise eine Raumkomplexität im ungünstigsten Fall auf Ο(#iterations), während sie mit TCO eine Raumkomplexität im ungünstigsten Fall aufweist Ο(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); });

Dies erfordert nicht einmal allgemeine Gesamtbetriebskosten, sondern nur einen sehr engen Sonderfall, nämlich die Beseitigung der direkten Schwanzrekursion.

Sehr interessant wäre jedoch, wenn eine Compileroptimierung nicht nur die Komplexitätsklasse ändert, sondern den Algorithmus tatsächlich vollständig ändert.

Der Glorious Glasgow Haskell Compiler macht das manchmal, aber das ist nicht wirklich das, worüber ich spreche, das ist eher wie Betrug. GHC verfügt über eine einfache Pattern Matching Language, mit der der Entwickler der Bibliothek einige einfache Codemuster erkennen und durch anderen Code ersetzen kann. Und die GHC Umsetzung der Haskell - Standardbibliothek hat einige dieser Anmerkungen zu enthalten, so dass bestimmte Verwendungen von spezifischen Funktionen , die ineffizient sind dafür bekannt, neu geschrieben in effizientere Versionen.

Diese Übersetzungen werden jedoch von Menschen geschrieben und sind für bestimmte Fälle geschrieben. Deshalb halte ich das für Betrug.

Ein Supercompiler kann den Algorithmus möglicherweise ohne menschliche Eingabe ändern, aber AFAIK hat noch nie einen Supercompiler auf Produktionsebene erstellt.

Jörg W Mittag
quelle
Vielen Dank für das großartige Beispiel und für die Erwähnung von GHC. Noch eine Frage: Was ist mit der Ausführung außerhalb der Reihenfolge? Gibt es ein bekanntes Beispiel, bei dem diese Art der Optimierung zu einer Änderung der Komplexitätsklasse eines Algorithmus führte?
Lorenz Lo Sauer
0

Ein Compiler, der sich bewusst ist, dass die Sprache eine Reduzierung der Stärke durch große Zahlen verwendet (Multiplikationen durch den Index einer Schleife durch eine Addition ersetzen), würde die Komplexität dieser Multiplikation von O (n log n) bestenfalls auf O (n) ändern. .

Ein Programmierer
quelle