Ich habe mehr über die Programmiersprache nachgedacht, die ich entwerfe. und ich frage mich, wie ich die Kompilierzeit minimieren könnte?
Ihr Hauptproblem ist heute I / O. Ihre CPU ist um ein Vielfaches schneller als der Hauptspeicher und der Arbeitsspeicher ist etwa 1000 Mal schneller als der Zugriff auf die Festplatte.
Wenn Sie also keine umfangreichen Optimierungen am Quellcode vornehmen, wird die CPU die meiste Zeit darauf warten, dass Daten gelesen oder geschrieben werden.
Teste diese Regeln:
Gestalten Sie Ihren Compiler so, dass er in mehreren unabhängigen Schritten funktioniert. Das Ziel besteht darin, jeden Schritt in einem anderen Thread ausführen zu können, sodass Sie Multi-Core-CPUs verwenden können. Es wird auch helfen, den gesamten Kompiliervorgang zu parallelisieren (d. H. Mehrere Dateien gleichzeitig zu kompilieren)
Es ermöglicht Ihnen auch, viele Quelldateien im Voraus zu laden und vorzuverarbeiten, damit der eigentliche Kompilierungsschritt schneller ausgeführt werden kann.
Versuchen Sie, Dateien unabhängig voneinander zu kompilieren. Erstellen Sie beispielsweise einen "fehlenden Symbolpool" für das Projekt. Fehlende Symbole sollten keine Kompilierungsfehler verursachen. Wenn Sie irgendwo ein fehlendes Symbol finden, entfernen Sie es aus dem Pool. Wenn alle Dateien kompiliert wurden, überprüfen Sie, ob der Pool leer ist.
Erstellen Sie einen Cache mit wichtigen Informationen. Beispiel: Datei X verwendet Symbole aus Datei Y. Auf diese Weise können Sie die Kompilierung der Datei Z (die nichts in Y referenziert) überspringen, wenn sich Y ändert. Wenn Sie einen Schritt weiter gehen möchten, legen Sie alle Symbole, die irgendwo in einem Pool definiert sind. Wenn sich eine Datei so ändert, dass Symbole hinzugefügt / entfernt werden, wissen Sie sofort, welche Dateien betroffen sind (ohne sie zu öffnen).
Kompilieren Sie im Hintergrund. Starten Sie einen Compiler-Prozess, der das Projektverzeichnis auf Änderungen prüft und kompiliert, sobald der Benutzer die Datei speichert. Auf diese Weise müssen Sie jedes Mal nur ein paar Dateien kompilieren, anstatt alles. Auf lange Sicht werden Sie viel mehr kompilieren, aber für den Benutzer werden Umsatzzeiten viel kürzer sein (= Zeit Benutzer muss warten, bis sie das kompilierte Ergebnis nach einer Änderung ausführen kann).
Verwenden Sie einen Just-in-time-Compiler (z. B. kompilieren Sie eine Datei, wenn sie verwendet wird, z. B. in einer import-Anweisung). Die Projekte werden dann in Quellform verteilt und kompiliert, wenn sie zum ersten Mal ausgeführt werden. Python macht das. Um dies durchzuführen, können Sie die Bibliothek während der Installation Ihres Compilers vorkompilieren.
Verwenden Sie keine Header-Dateien. Bewahren Sie alle Informationen an einem einzigen Ort auf und generieren Sie gegebenenfalls Header-Dateien aus der Quelle. Vielleicht behalten Sie die Header-Dateien nur im Speicher und speichern sie nicht auf der Festplatte.
Ich habe selbst einen Compiler implementiert und musste dies erst einmal sehen, nachdem die Leute angefangen hatten, Hunderte von Quelldateien zu füttern. Ich war ziemlich überrascht, was ich herausgefunden habe.
Es stellt sich heraus, dass das Wichtigste, was Sie optimieren können, nicht Ihre Grammatik ist. Es ist auch nicht Ihr lexikalischer Analysator oder Ihr Parser. Das Wichtigste in Bezug auf die Geschwindigkeit ist stattdessen der Code, der Ihre Quelldateien von der Festplatte einliest. I / O's auf Festplatte sind langsam . Wirklich langsam. Sie können die Geschwindigkeit Ihres Compilers anhand der Anzahl der ausgeführten Festplatten-I / Os messen.
Es stellt sich also heraus, dass das Beste, was Sie tun können, um einen Compiler zu beschleunigen, darin besteht, die gesamte Datei in einem großen I / O in den Speicher zu schreiben, alles zu lesen, zu parsen usw. aus dem RAM und dann zu schreiben das Ergebnis in einem großen I / O auf die Festplatte ausgeben.
Ich habe mit einem der Head-Leute darüber gesprochen, Gnat (Ada-Compiler von GCC) darüber zu halten, und er sagte mir, dass er eigentlich alles auf RAM-Disketten legte, so dass sogar seine Datei-I / O wirklich nur RAM las und schreibt.
In den meisten Sprachen (ziemlich gut alles außer C ++) ist das Kompilieren einzelner Kompilierungseinheiten ziemlich schnell.
Das Binden / Verknüpfen ist oft langsam - der Linker muss das ganze Programm und nicht nur eine einzelne Einheit referenzieren.
C ++ leidet darunter - es sei denn, Sie verwenden das pImpl-Idiom - es erfordert die Implementierungsdetails jedes Objekts und aller Inline-Funktionen, um Client-Code zu kompilieren.
Java (source to bytecode) leidet darunter, dass die Grammatik keine Objekte und Klassen unterscheidet. Sie müssen die Foo - Klasse laden, um zu sehen, ob Foo.Bar.Baz das Baz - Feld des Objekts ist, auf das das statische Feld von Foo-Klasse oder ein statisches Feld der Foo.Bar-Klasse. Sie können die Quelle der Foo-Klasse zwischen den beiden ändern und nicht die Quelle des Client-Codes ändern, sondern den Client-Code neu kompilieren, da der Bytecode zwischen den beiden Formen unterscheidet, obwohl die Syntax dies nicht tut . AFAIK Python Bytecode unterscheidet nicht zwischen den beiden - Module sind wahre Mitglieder ihrer Eltern.
C ++ und C leiden darunter, wenn Sie mehr Header als erforderlich hinzufügen, da der Präprozessor jeden Header mehrmals verarbeiten muss und der Compiler sie kompiliert. Das Minimieren der Header-Größe und -Komplexität hilft, was darauf hindeutet, dass eine bessere Modularität die Kompilierungszeit verbessern würde. Es ist nicht immer möglich, die Headerkompilierung zwischenzuspeichern, da die Definitionen, die vorhanden sind, wenn der Header vorverarbeitet wird, seine Semantik und sogar die Syntax ändern können.
C leidet, wenn Sie den Präprozessor viel verwenden, aber die eigentliche Kompilierung ist schnell; Ein Großteil des C-Codes verwendet typedef struct _X* X_ptr , um die Implementierung besser zu verbergen als C ++ - ein C-Header kann leicht aus typedefs und Funktionsdeklarationen bestehen, was eine bessere Kapselung ergibt.
Ich würde daher vorschlagen, dass Ihre Sprache die Implementierungsdetails aus dem Client-Code ausblenden soll. Wenn Sie eine OO-Sprache mit Instanzmembern und Namespaces sind, machen Sie die Syntax für den Zugriff auf die beiden eindeutig. Ermöglichen Sie echte Module, sodass Client-Code nur die Schnittstelle und nicht die Implementierungsdetails kennen muss. Präprozessor-Makros oder andere Variationsmechanismen dürfen die Semantik referenzierter Module nicht ändern.
Hier sind einige Performance-Tricks, die wir gelernt haben, indem wir die Übersetzungsgeschwindigkeit messen und was sie beeinflusst:
Schreiben Sie einen Two-Pass-Compiler: Zeichen in IR, IR in Code. (Es ist einfacher, einen drei -Umsetzer-Compiler zu schreiben, der Zeichen -> AST -> IR-Code verarbeitet, aber nicht so schnell.
Als Konsequenz haben Sie keinen Optimierer; Es ist schwer, einen schnellen Optimierer zu schreiben.
Erwägen Sie, Bytecode anstelle von systemeigenem Maschinencode zu generieren. Die virtuelle Maschine für Lua ist ein gutes Modell.
Versuchen Sie einen Linear-Scan-Registerzuordner oder den einfachen Registerzuordner, den Fraser und Hanson in lcc verwendet haben >.
In einem einfachen Compiler ist die lexikalische Analyse oft der größte Leistungsengpass. Wenn Sie C- oder C ++ - Code schreiben, verwenden Sie re2c . Wenn Sie eine andere Sprache verwenden (die Sie sehr viel angenehmer finden), lesen Sie den Artikel über re2c und wenden Sie die gelernten Lektionen an.
Generieren Sie Code mit maximalem Munch oder möglicherweise iburg .
Überraschenderweise ist der GNU-Assembler bei vielen Compilern ein Engpass. Wenn Sie Binär direkt generieren können, tun Sie dies. Oder sehen Sie sich das New-Jersey-Maschinencode-Toolkit an.
Entwerfen Sie wie oben erwähnt Ihre Sprache, um etwas wie #include zu vermeiden. Verwenden Sie entweder keine Schnittstellendateien oder kompilieren Sie Ihre Schnittstellendateien vorkompilieren. Diese Taktik reduziert drastisch die Belastung des Lexers, was, wie gesagt, oft der größte Engpass ist.
Hier ist eine Aufnahme ..
Verwenden Sie inkrementelle Kompilierung, wenn Ihre Toolchain dies unterstützt. (machen, visuelles Studio, etc).
Wenn Sie beispielsweise in GCC / make viele Dateien kompilieren müssen, aber nur Änderungen an einer Datei vornehmen, wird nur diese eine Datei kompiliert.
Eiffel hatte eine Vorstellung von verschiedenen Zuständen von "eingefroren", und Neukompilieren bedeutete nicht notwendigerweise, dass die gesamte Klasse neu kompiliert wurde.
Wie viel können Sie die komplizierten Module aufteilen, und wie viel interessieren Sie, um sie zu verfolgen?
Eine Sache, die in den bisherigen Antworten überraschend fehlte: Sie machen eine kontextfreie Grammatik, usw. Sehen Sie sich Sprachen an, die von Wirth entwickelt wurden, wie Pascal & amp; Modula-2. Sie müssen Pascal nicht erneut implementieren, aber das Grammatik-Design ist für schnelles Kompilieren maßgeschneidert. Dann sehen Sie, ob Sie irgendwelche alten Artikel über die Tricks finden können, die Anders beim Implementieren von Turbo Pascal machte. Tipp: Tabelle gefahren.
In C ++ können Sie eine verteilte Kompilierung mit Tools wie Incredibuild
verwendenEine einfache Sache: Stellen Sie sicher, dass der Compiler native Multi-Core-CPUs nutzen kann.
Wie ernst ist ein Compiler das?
Wenn die Syntax nicht ziemlich kompliziert ist, sollte der Parser nicht mehr als 10-100 mal langsamer laufen als nur durch die Zeichen der Eingabedatei.
Ebenso sollte die Codegenerierung durch Ausgabeformatierung eingeschränkt sein.
Sie sollten keine Leistungsprobleme haben, es sei denn, Sie machen einen großen, seriösen Compiler, der in der Lage ist, Mega-Line-Anwendungen mit vielen Header-Dateien zu verarbeiten.
Dann müssen Sie sich über vorkompilierte Header, Optimierungsdurchläufe und Verknüpfungen sorgen.
Ich habe nicht viel Arbeit zur Minimierung der Kompilierzeit gesehen. Aber einige Ideen fallen mir ein:
Wenn Sie keine hochspezialisierte Sprache schreiben, ist die Kompilierzeit nicht wirklich ein Problem.
Mach ein Build-System, das nicht lutscht!
Es gibt eine riesige Menge an Programmen mit vielleicht drei Quelldateien, die weniger als eine Sekunde brauchen, um kompiliert zu werden, aber bevor Sie so weit kommen, müssen Sie ein Automakeskript durchsehen, das etwa zwei Minuten dauert von einem int . Und wenn du eine Minute später etwas anderes kompilierst, lässt es dich fast genau die gleichen Tests bestehen.
Wenn also der Compiler dem Benutzer keine scheußlichen Dinge antut, wie zB die Größe von int s ändern oder grundlegende Funktionsimplementierungen zwischen Läufen ändern, dann lade diese Informationen einfach in eine Datei und lasse sie los Holen Sie es in einer Sekunde anstatt in 2 Minuten.
Tags und Links performance compiler-construction language-design