Zeitliche Komplexität eines Compilers

54

Ich interessiere mich für die zeitliche Komplexität eines Compilers. Dies ist natürlich eine sehr komplizierte Frage, da viele Compiler, Compileroptionen und Variablen zu berücksichtigen sind. Insbesondere interessiere ich mich für LLVM, würde mich aber für Gedanken interessieren, die Menschen hatten, oder Orte, an denen sie mit der Forschung beginnen könnten. Ein ganz Google scheint wenig ans Licht zu bringen.

Ich würde vermuten, dass es einige Optimierungsschritte gibt, die exponentiell sind, aber nur einen geringen Einfluss auf die tatsächliche Zeit haben. Exponentiale, die auf der Zahl basieren, sind z. B. Argumente einer Funktion.

Von meinem Kopf aus würde ich sagen, dass das Erzeugen des AST-Baums linear wäre. Für die IR-Erzeugung müsste der Baum schrittweise durchlaufen werden, während die Werte in ständig wachsenden Tabellen nachgeschlagen werden, also oder O ( n log n ) . Die Codegenerierung und -verknüpfung wäre eine ähnliche Art von Operation. Daher würde ich O ( n 2 ) annehmen, wenn wir Exponentiale von Variablen entfernen würden, die nicht realistisch wachsen.O(n2)O(nLogn)O(n2)

Ich könnte mich jedoch völlig irren. Hat jemand irgendwelche Gedanken dazu?

Superbriggs
quelle
7
Sie müssen vorsichtig sein, wenn Sie behaupten, dass alles "exponentiell", "linear", oder O ( n log n ) ist . Zumindest für mich ist es überhaupt nicht offensichtlich, wie Sie Ihre Eingabe messen (Exponential in was? Wofür steht n ?)O(n2)O(nLogn)n
Juho
2
Wenn Sie LLVM sagen, meinen Sie Clang? LLVM ist ein großes Projekt mit mehreren unterschiedlichen Compiler-Teilprojekten, daher ist es etwas mehrdeutig.
Nate CK
5
Für C # ist es für Worst-Case-Probleme mindestens exponentiell (Sie können das NP-vollständige SAT-Problem in C # codieren). Dies ist nicht nur eine Optimierung, sondern eine Voraussetzung für die Auswahl der richtigen Überladung einer Funktion. Für Sprachen wie C ++ ist dies nicht zu entscheiden, da die Vorlagen vollständig sind.
CodesInChaos
2
@Zane Ich verstehe deinen Standpunkt nicht. Die Vorlageninstanziierung erfolgt während der Kompilierung. Sie können schwierige Probleme in Vorlagen so codieren, dass der Compiler gezwungen ist, das Problem zu lösen, um eine korrekte Ausgabe zu erzielen. Sie könnten den Compiler als Interpreter der vollständigen Template-Programmiersprache betrachten.
CodesInChaos
3
Die Auflösung von C # -Überladungen ist ziemlich schwierig, wenn Sie mehrere Überladungen mit Lambda-Ausdrücken kombinieren. Sie können das verwenden, um eine Boolesche Formel so zu codieren, dass das NP-complete 3SAT-Problem erforderlich ist, um festzustellen, ob eine entsprechende Überlastung vorliegt. Um das Problem tatsächlich zu kompilieren, muss der Compiler die Lösung für diese Formel finden, die möglicherweise noch schwieriger ist. Eric Lippert spricht ausführlich darüber in seinem Blogbeitrag Lambda Expressions vs. Anonymous Methods, Teil 5
CodesInChaos

Antworten:

50

Das beste Buch, um Ihre Frage zu beantworten, ist wahrscheinlich: Cooper und Torczon, "Engineering a Compiler", 2003. Wenn Sie Zugang zu einer Universitätsbibliothek haben, sollten Sie eine Kopie ausleihen können.

In einem Produktionscompiler wie llvm oder gcc bemühen sich die Designer, alle Algorithmen unter wobei n die Größe der Eingabe ist. Für einige der Analysen für die "Optimierungs" -Phasen bedeutet dies, dass Sie Heuristiken verwenden müssen, anstatt wirklich optimalen Code zu erzeugen.O(n2)n

O(n)O(n)

O(n)O(1)O(s)s

Dann wird der Analysebaum typischerweise zu einem Kontrollflussgraphen "abgeflacht". Die Knoten des Steuerflussdiagramms können Anweisungen mit drei Adressen sein (ähnlich einer RISC-Assemblersprache), und die Größe des Steuerflussdiagramms ist in der Regel linear in Bezug auf die Größe des Analysebaums.

O(d)dO(n)n

O(n2)Dies bedeutet jedoch, dass Sie auf Informationen (und programmverbessernde Transformationen) verzichten müssen, deren Nachweis möglicherweise teuer ist. Ein klassisches Beispiel hierfür ist die Alias-Analyse, bei der Sie für ein Paar von Speicherschreibvorgängen nachweisen möchten, dass die beiden Schreibvorgänge niemals auf denselben Speicherort abzielen können. (Möglicherweise möchten Sie eine Alias-Analyse durchführen, um festzustellen, ob Sie eine Anweisung über die andere verschieben können.) Um jedoch genaue Informationen zu Aliasen zu erhalten, müssen Sie möglicherweise jeden möglichen Steuerpfad durch das Programm analysieren, der in Bezug auf die Anzahl der Zweige exponentiell ist im Programm (und damit exponentiell in der Anzahl der Knoten im Kontrollflussgraphen.)

Als nächstes kommen Sie in die Registerzuordnung. Registerzuordnung kann als formulieren Graph-Färbungsproblem , und Färbung ein Diagramm mit einer minimalen Anzahl von Farben ist bekannt, dass NP-Hard. Daher verwenden die meisten Compiler eine Art gierige Heuristik in Kombination mit Register-Spilling, um die Anzahl der Register-Spills innerhalb eines angemessenen Zeitraums so gut wie möglich zu reduzieren.

Schließlich kommen Sie in die Codegenerierung. Die Codegenerierung erfolgt typischerweise als maximaler Basisblock zu einem Zeitpunkt, an dem ein Basisblock eine Menge linear verbundener Kontrollflussgraphknoten mit einem einzelnen Eingang und einem einzelnen Ausgang ist. Dies kann als ein Diagramm umformuliert werden, das ein Problem abdeckt, bei dem das Diagramm, das Sie abdecken möchten, das Abhängigkeitsdiagramm des Satzes von Anweisungen mit drei Adressen im Basisblock ist, und Sie versuchen, einen Satz von Diagrammen abzudecken, die die verfügbare Maschine darstellen Anleitung. Dieses Problem ist exponentiell in Bezug auf die Größe des größten Basisblocks (der im Prinzip in der gleichen Größenordnung wie die Größe des gesamten Programms liegen kann), weshalb dies wiederum in der Regel mit Heuristiken durchgeführt wird, bei denen nur eine kleine Teilmenge der möglichen Abdeckungen vorhanden ist untersucht.

Wandering Logic
quelle
4
Thirded! Übrigens sind viele der Probleme, die Compiler zu lösen versuchen (z. B. Registerzuweisung), NP-schwer, aber andere sind formal nicht entscheidbar. Angenommen, Sie haben beispielsweise einen Aufruf p () gefolgt von einem Aufruf q (). Wenn p eine reine Funktion ist, können Sie die Aufrufe sicher neu anordnen, solange p () keine Endlosschleife ausführt. Um dies zu beweisen, muss das Halteproblem gelöst werden. Wie bei den NP-harten Problemen könnte ein Compiler-Schreiber so viel oder so wenig Aufwand in die Annäherung an eine mögliche Lösung stecken.
Pseudonym
4
Oh, noch etwas: Es gibt heute einige Typsysteme, die in der Theorie sehr komplex sind. Inferenz vom Typ Hindley-Milner ist dem DEXPTIME-complete bekannt, und ML-ähnliche Sprachen müssen sie korrekt implementieren. In der Praxis ist die Laufzeit jedoch linear, da a) pathologische Fälle in realen Programmen niemals auftreten und b) reale Programmierer dazu neigen, Typanmerkungen einzufügen, wenn auch nur, um bessere Fehlermeldungen zu erhalten.
Pseudonym
1
Gute Antwort, das einzige, was zu fehlen scheint, ist der einfache Teil der Erklärung, der in einfachen Worten formuliert ist: Ein Programm kann in O (n) kompiliert werden. Das Optimieren eines Programms vor dem Kompilieren, wie es jeder moderne Compiler tun würde, ist eine praktisch unbegrenzte Aufgabe. Die Zeit, die tatsächlich benötigt wird, wird nicht durch eine inhärente Beschränkung der Aufgabe bestimmt, sondern durch die praktische Notwendigkeit, dass der Compiler irgendwann fertig sein muss, bevor die Leute das Warten satt haben. Es ist immer ein Kompromiss.
aaaaaaaaaaa
@Pseudonym: Die Tatsache, dass der Compiler das Stopp-Problem oft lösen müsste (oder sehr unangenehme NP-Probleme), ist einer der Gründe, warum Standards dem Compiler-Schreiber Spielraum bei der Annahme geben, dass undefiniertes Verhalten nicht vorkommt (wie Endlosschleifen und dergleichen) ).
Vonbrand
15

Tatsächlich sind einige Sprachen (wie C ++, Lisp und D) zur Kompilierungszeit vollständig, so dass das Kompilieren im Allgemeinen nicht entscheidend ist. Für C ++ liegt dies an der rekursiven Template-Instanziierung. Für Lisp und D können Sie fast jeden Code zur Kompilierungszeit ausführen, sodass Sie den Compiler in eine Endlosschleife werfen können, wenn Sie möchten.

Demi
quelle
3
Die Typensysteme von Haskell (mit Erweiterungen) und Scala sind ebenfalls vollständig, was bedeutet, dass die Typprüfung unendlich viel Zeit in Anspruch nehmen kann. Scala hat jetzt auch Turing-Complete-Makros im Vordergrund.
Jörg W Mittag
5

Aus meiner tatsächlichen Erfahrung mit dem C # -Compiler kann ich sagen, dass die Größe der Ausgabebinärdatei für bestimmte Programme exponentiell in Bezug auf die Größe der Eingabequelle zunimmt (dies ist in der C # -Spezifikation tatsächlich erforderlich und kann nicht reduziert werden) muss auch mindestens exponentiell sein.

Die allgemeine Aufgabe zur Überlastungslösung in C # ist bekanntermaßen NP-hart (und die tatsächliche Implementierungskomplexität ist mindestens exponentiell).

Für die Verarbeitung von XML-Dokumentationskommentaren in C # -Quellen müssen auch beliebige XPath 1.0-Ausdrücke zur Kompilierungszeit ausgewertet werden, was ebenfalls exponentiell ist (AFAIK).

Vladimir Reshetnikov
quelle
Wodurch werden C # -Binaries auf diese Weise in die Luft gesprengt? Klingt für mich wie ein Sprachfehler ...
vonbrand
1
Auf diese Weise werden generische Typen in Metadaten codiert. class X<A,B,C,D,E> { class Y : X<Y,Y,Y,Y,Y> { Y.Y.Y.Y.Y.Y.Y.Y.Y y; } }
Vladimir Reshetnikov
-2

Messen Sie es mit realistischen Codebasen, z. B. einer Reihe von Open Source-Projekten. Wenn Sie die Ergebnisse als (codeSize, finishTime) zeichnen, können Sie diese Diagramme zeichnen. Wenn Ihre Daten f (x) = y O (n) sind, sollte das Zeichnen von g = f (x) / x eine gerade Linie ergeben, nachdem die Daten groß werden.

Zeichnen Sie f (x) / x, f (x) / lg (x), f (x) / (x * lg (x)), f (x) / (x * x) usw. Die Grafik taucht entweder ab auf Null stellen, ungebunden erhöhen oder abflachen. Diese Idee eignet sich zum Beispiel zum Messen der Einfügezeiten ausgehend von einer leeren Datenbank (z. B. um über einen längeren Zeitraum nach einem Leistungsleck zu suchen).

rauben
quelle
1
Die empirische Messung von Laufzeiten begründet keine Komplexität der Berechnungen. Erstens wird die Komplexität der Berechnungen am häufigsten als Worst-Case-Laufzeit ausgedrückt. Zweitens, selbst wenn Sie einen Durchschnittsfall messen möchten, müssen Sie feststellen, dass Ihre Eingaben in diesem Sinne "durchschnittlich" sind.
David Richerby
Na klar, es ist nur eine Schätzung. Einfache empirische Tests mit vielen realen Daten (jedes Commit für eine Reihe von Git-Repos) können jedoch ein vorsichtiges Modell übertreffen. Wenn eine Funktion tatsächlich O (n ^ 3) ist und Sie f (n) / (n n n) zeichnen , sollten Sie auf jeden Fall eine verrauschte Linie mit einer Steigung von ungefähr Null erhalten. Wenn Sie nur O (n ^ 3) / (n * n) zeichnen würden, würden Sie einen linearen Anstieg sehen. Es ist wirklich offensichtlich, wenn Sie die Linie überschätzen und beobachten, wie sie schnell auf Null abtaucht.
Rob
1
Θ(nLogn)Θ(n2)Θ(nLogn)Θ(n2)
Ich bin damit einverstanden, dass Sie genau das wissen müssen, wenn Sie befürchten, von einem Angreifer, der Ihnen schlechte Eingaben liefert, einen Denial-of-Service zu erhalten, und einige kritische Eingaben in Echtzeit analysieren. Die eigentliche Funktion, die die Kompilierungszeiten misst, wird sehr verrauscht sein, und der uns interessierende Fall wird in realen Code-Repositorys vorliegen.
Rob
1
Die Frage fragt nach der zeitlichen Komplexität des Problems. Dies wird normalerweise als Worst-Case-Laufzeit interpretiert, bei der es sich nachdrücklich nicht um die Laufzeit von Code in Repositorys handelt. Die von Ihnen vorgeschlagenen Tests geben einen angemessenen Überblick darüber, wie lange der Compiler einen bestimmten Codeteil voraussichtlich übernehmen wird. Dies ist eine gute und nützliche Sache, die Sie wissen sollten. Sie sagen jedoch fast nichts über die rechnerische Komplexität des Problems aus.
David Richerby