Was sind die wichtigsten Design-Entscheidungen, um einen extrem schnellen Compiler zu entwickeln?

Question

Ich möchte wissen, wie man einen Compiler entwickelt, der sehr, sehr schnell kompiliert.

Zunächst möchte ich einige offensichtliche Missverständnisse in Bezug auf meine Frage ausräumen:

1. Ich bin no Es geht um die Geschwindigkeit des vom Compiler erzeugten Codes. Es gibt bereits viele verfügbare Ressourcen, um zu lernen, wie man generierten Code optimiert. Was ich nicht finde, sind Informationen darüber, wie man die Compiler schnell.

2. Ich bin auch nicht an einer Diskussion darüber interessiert, warum C++-Compiler generell langsamer sind als Java-Compiler (zum Beispiel). Ich bin daran interessiert, welche Techniken eingesetzt werden können, um den Compiler für eine bestimmte Sprache zu beschleunigen.

3. Ich möchte auch nichts über verteilte Kompilierungssysteme wie Microsofts Incredibuild oder Unix' distcc hören. Diese Systeme geben Ihnen keine schneller Compilern, sie geben Ihnen nur mehr Kompilatoren. Das ist sicherlich nützlich, aber das ist nicht die Frage, die ich stelle. Ich möchte wissen, wie man einen schnellen Compiler für eine einzelne CPU entwickelt.

4. Auch ccache ist nicht die Antwort, nach der ich suche. Das ist ein System, mit dem man die Verwendung des Compilers vermeiden kann, aber es macht den Compiler nicht schneller. Auch das ist nützlich, aber das ist nicht die Frage, die ich stelle.

Ich hoffe, meine Frage ist jetzt klar und deutlich. Aber vielleicht wird sie durch ein wenig Geschichte noch klarer.

C-Compiler waren früher sehr langsam. Dann, 1986, stellte THINK Technologies Lightspeed C für Macintosh vor, und es kompilierte Programme fast sofort. Lightspeed C war also viel schneller als alle anderen C-Compiler, dass es kaum einen Vergleich gab. (Vielleicht war Lightspeed C nicht der erste der neuen Generation von blitzschnellen Compilern, aber nach meiner Erfahrung war es der erste. Turbo Pascal kam schon früher [1983] auf den Markt, aber ich hatte keine Erfahrung damit, so dass ich nicht weiß, wie er in Bezug auf die Geschwindigkeit im Vergleich abschneidet).

Seitdem gibt es viele schnelle Compiler. Es scheint, dass es in den 1980er Jahren eine Art Quantensprung in der Compilertechnologie gab, und dass ist das, was ich zu verstehen versuche. Was war der Durchbruch?

Die Antwort ist vielleicht so einfach: Bei IDEs wie Lightspeed und Turbo hat der integrierte Editor den Quellcode bereits im RAM. Wenn der Compiler mit diesen Daten arbeitet, entfällt die Festplatten-E/A, die der langsamste Teil jedes Compilers ist. Das ist wahrscheinlich ein sehr wichtiger Beitrag zur Geschwindigkeitsverbesserung, wenn die Größe des Quellcodes im Verhältnis zur Speichergröße klein ist. (Damals waren die RAM-Größen viel kleiner, aber das galt auch für die typischen Programmgrößen.)

War es das? Oder gab es noch andere wichtige Innovationen? Und hat sich die Geschwindigkeit der Compiler seither wesentlich verbessert?

Answer 1

• Einfache Syntax, die in einem einzigen Durchgang geparst werden kann.
• Einfacher Zielcode. Wenn Sie nicht direkt auf Maschinencode abzielen, können Sie sich viele Dinge erlauben.
• Überhaupt nicht kompilieren. Wenn Sie keine schnelle Ausführung benötigen oder hauptsächlich für einmalige Skripte konzipiert sind, brauchen Sie keine Zeit mit der Analyse des Codes zu verschwenden.
• Versuchen Sie nicht, ich wiederhole, versuchen Sie nicht, die Festplatten-/Cache-Verwaltung Ihres Betriebssystems zu überlisten. Bilden Sie die ganze verdammte Datei ab und lesen Sie sie, als ob Sie sie aus dem RAM lesen würden. Wenn Sie nicht über einen virtuellen Speicher verfügen, ist eine schnelle Kompilierung das geringste Ihrer Probleme.
• Vermeiden Sie die Erstellung von XML-DOM-ähnlichen aufgeblähten Datenstrukturen für AST. Sie müssen Ihre Operatorpräferenzen nicht animieren. Behalten Sie Zeiger auf die gemappten Daten, anstatt Dinge herumzukopieren.
• Profilieren Sie Ihren Code, wenn Sie es schnell wollen. Immer.

Zusatz:

• Lernen Sie verschiedene Arten des Parsing. Wenn Sie sich nicht sicher sind, ob Sie einen Parser schreiben können, verwenden Sie bewährte Parser/Lexer-Generatoren wie antlr, lemon usw.

Answer 2

Ein Problem ist, was Sie für generierten Code ausgeben. Sie können so viel Compilerzeit in die Optimierung stecken, wie Sie wollen. Eine einfache Generierung, die vielleicht sogar etwas dumm aussieht, wird Ihnen Zeit sparen. Damals, als ich Turbo Pascal und Lightspeed C benutzte, war es natürlich das Wichtigste, eine ausführbare Datei zu erhalten, und nicht, wie gut sie optimiert war. Die Desktop-Compiler-Technologie war damals der Großrechner-Compiler-Technologie weit hinterher.

Ein weiterer Aspekt von Turbo Pascal und Lightspeed C war die Integration. Besonders in den Tagen vor Multitasking-Heimcomputern war das großartig. Im Gegensatz zum ersten C-Compiler, den ich besaß (für CP/M), mußte ich keine Änderungen in einem Editor vornehmen, diesen schließen, kompilieren, linken und dann ausführen. Das mag ein Teil dessen gewesen sein, was Sie gesehen haben: schnelle Ausführung von Komponenten, ohne komplizierte Befehle eintippen zu müssen. Ich kann das jetzt duplizieren, indem ich mehrere Terminals auf einem Gnome-Desktop laufen lasse: eines für vim, eines zum Ausführen von gcc und eines zum Ausführen in.

Abgesehen davon ist die Reduzierung der E/A gut. Eine schnelle lexikalische Analyse ist heutzutage im Grunde ein gelöstes Problem, aber damals nicht unbedingt. Beim Parsing bin ich mir nicht sicher, da ich mich damit zuletzt vor zwanzig Jahren befasst habe, also kann Ihnen jemand anders helfen.

Answer 3

Es ist allgemein bekannt, dass handkodierte, auf rekursivem Abstieg basierende Top-Down-Parser schneller sind als regelbasierte LALR(k)-Parser, wie sie von yacc erstellt werden - vorausgesetzt, sie sind gut kodiert. Handkodierte Parser können in manchen Fällen auch bessere Fehlermeldungen liefern.

OTOH, ein guter Grund, etwas wie yacc zu verwenden, ist, dass LALR(1) eine größere Klasse von Sprachen eindeutig parsen kann als rekursiver Abstieg - was der LL(1)-Klasse von Sprachen entspricht, wenn ich mich recht erinnere. Es kann auch weniger Zeit in Anspruch nehmen, einen Parser im Stil von yacc zu erstellen und zu überarbeiten als einen von Hand erstellten.

Es ist nicht klar, dass das Parsing der Leistungsengpass ist, verglichen mit all den anderen Problemen, die hier diskutiert wurden. Das heißt, eine schlechte Arbeit an der Datei IO oder AST-Traversal kann viel schaden - wahrscheinlich viel mehr als Sie für die Verwendung eines etwas weniger effizienten Parser zahlen würde.

Die wirklich schnellen Compiler, mit denen ich vertraut bin, verwendeten jedoch handgefertigte rekursive Descent-Parser. Ich muss zugeben, dass es schon einige Jahre her ist, dass ich beruflich mit Compilern gearbeitet habe, aber es war einmal Teil meiner täglichen Arbeit.

Answer 4

C++-Compiler sind langsamer als Java-Compiler, vor allem weil sie (in der Regel) optimierten nativen Code erzeugen, während Java-Compiler nur wenig optimierte Bytecodes erzeugen und die endgültige Optimierung und die Erzeugung des nativen Codes dem JIT-Compiler überlassen (der zur Laufzeit arbeitet). Da ernsthafte Optimierungen Kenntnisse des nativen Codes voraussetzen, kann der Bytecode-Compiler nicht viel tun.

Ich kann mich nicht zu Lightspeed äußern (da ich nichts darüber weiß), aber im Fall von Lattice und Microsoft C (langsam) gegenüber Borland TurboC (schnell) behielt Borland alle Dateien im Speicher und kompilierte sie dort (wenn Ihr Programm abstürzte, konnte dies die IDE zum Absturz bringen, wodurch Sie ungespeicherten Quellcode verloren). Die IDE von Micrsoft speicherte die Dateien immer auf der Festplatte und startete dann ein separates Programm, um die Festplatte zu lesen und sie zu kompilieren.

Die Verwendung von Precompiler-Header-Dateien trug ebenfalls zur Beschleunigung der C/C++-Kompilierung bei.

Eine weitere Möglichkeit, die Kompilierung zu beschleunigen, ist eine Sprache, die eine Kompilierung in einem Durchgang ermöglicht. Zum Beispiel verlangt Pascal, dass jede verwendete Funktion definiert wird (nicht nur deklariert, wie in C++), bevor sie verwendet wird (deshalb muss die main-Funktion als letzte in der Quelldatei stehen)

Answer 5

Heute würden Sie Ihren Compiler sicherlich dazu bringen, alle ihm zur Verfügung stehenden Kerne zu nutzen. Ich schreibe nicht über verteilte Kompilierung, sondern parallel Kompilierung: Entwerfen Sie Ihren Compiler von Grund auf für die Verwendung mehrerer Kerne. Ein naheliegender Ansatz wäre die Parallelisierung der verschiedenen Phasen eines Compilers. Das Neuschreiben eines AST könnte sicherlich auch parallelisiert werden

Und bitte, ersparen Sie sich Ihre Tipperei und sagen Sie uns nicht, dass dieser Ansatz durch Ihre "Regeln" ausgeschlossen ist. Ihre Regeln würden wahrscheinlich die Verwendung einer Fließkommaeinheit zur Optimierung der Fließkommaarithmetik verhindern oder die Verwendung eines Prozessors mit einer höheren Taktfrequenz als 1 GHz verbieten.

Wenn Sie schnelle Programme für die heutigen Computer schreiben wollen, schreiben Sie sie für die heutigen CPUs, nicht für die von gestern. Die heutigen Computer verwenden Multicore-CPUs.