Geekly articles weekly

Vergleichen des gleichen Projekts in Rust, Haskell, C ++, Python, Scala und OCaml

Im letzten Semester der Universität habe ich mich für den CS444-Compilerkurs entschieden . Dort musste jede Gruppe von 1-3 Personen einen Compiler aus einer wesentlichen Teilmenge von Java in x86 schreiben. Sprache, um eine Gruppe auszuwählen. Dies war eine seltene Gelegenheit, Implementierungen großer Programme mit derselben Funktionalität, die von sehr kompetenten Programmierern in verschiedenen Sprachen geschrieben wurden, zu vergleichen und die Unterschiede in Design und Sprachauswahl zu vergleichen. Ein solcher Vergleich ließ viele interessante Gedanken aufkommen. Ein derart kontrollierter Sprachvergleich ist selten zu sehen. Es ist nicht perfekt, aber viel besser als die meisten subjektiven Geschichten, auf denen die Meinungen der Leute über Programmiersprachen basieren.

Wir haben unseren Rust-Compiler erstellt und ihn zuerst mit dem Haskell-Teamprojekt verglichen. Ich hatte erwartet, dass ihr Programm viel kürzer sein würde, aber es stellte sich heraus, dass es gleich groß oder größer war. Gleiches gilt für OCaml. Dann habe ich es mit dem C ++ - Compiler verglichen, und dort war zu erwarten, dass der Compiler etwa 30% größer war, hauptsächlich aufgrund von Headern, fehlenden Summentypen und Mustervergleich. Der folgende Vergleich wurde mit meiner Freundin durchgeführt, die den Compiler selbst in Python erstellt und aufgrund der Möglichkeiten der Metaprogrammierung und der dynamischen Typen weniger als die Hälfte des Codes im Vergleich zu uns verwendet hat. Ein anderer Freund hatte ein kleineres Scala-Programm. Was mich am meisten überraschte, war der Vergleich mit einem anderen Team, das ebenfalls Rust verwendete, aber aufgrund unterschiedlicher Designentscheidungen dreimal so viel Code hatte. Am Ende war der größte Unterschied in der Codemenge in derselben Sprache!

Ich werde erklären, warum ich dies für einen guten Vergleich halte, einige Informationen zu jedem Projekt geben und einige Gründe für Unterschiede in der Größe des Compilers erläutern. Ich werde auch aus jedem Vergleich Schlussfolgerungen ziehen. Fühlen Sie sich frei, diese Links zu verwenden, um zu dem Abschnitt von Interesse zu gelangen:

Inhalt


  • Warum finde ich das sinnvoll?
  • Rost (Vergleichsbasis)
  • Haskell : 1,0-1,6 Größen, je nachdem, wie Sie zählen, aus interessanten Gründen
  • C ++ : 1.4 Größen aus offensichtlichen Gründen
  • Python : 0,5 Größe durch ausgefallene Metaprogrammierung!
  • Rust (eine andere Gruppe) : dreimal so groß aufgrund eines anderen Designs!
  • Scala : 0,7 Größen
  • OCaml : 1,0-1,6 Größe, je nachdem, wie Sie zählen, ähnlich wie bei Haskell

Warum finde ich das sinnvoll?


Bevor Sie sagen, dass die Codemenge (ich habe sowohl Zeichenfolgen als auch Bytes verglichen) eine schreckliche Metrik ist, möchte ich darauf hinweisen, dass sie in diesem Fall ein gutes Verständnis vermitteln kann. Zumindest ist dies das am besten kontrollierte Beispiel, bei dem verschiedene Teams dasselbe große Programm schreiben, von dem ich gehört oder gelesen habe.

  • Niemand (einschließlich mir) wusste, dass ich diesen Parameter messen würde, also versuchte niemand, Metriken abzuspielen. Alle versuchten nur, das Projekt schnell und korrekt abzuschließen.
  • Alle (mit Ausnahme des Python-Projekts, auf das ich später noch eingehen werde) haben das Programm nur zum Zweck des Bestehens derselben automatisierten Testsuite zur gleichen Zeit implementiert, sodass die Ergebnisse von Gruppen, die unterschiedliche Probleme lösen, nicht stark verzerrt werden können.
  • Das Projekt wurde innerhalb weniger Monate mit dem Team abgeschlossen und sollte schrittweise erweitert werden und sowohl bekannte als auch unbekannte Tests bestehen. Dies bedeutet, dass es nützlich war, sauberen, klaren Code zu schreiben.
  • Abgesehen vom Bestehen der Kurstests wird der Code für nichts anderes verwendet, niemand wird ihn lesen und als Compiler für eine begrenzte Teilmenge von Java in Text Assembler wird er nicht nützlich sein.
  • Es sind keine anderen Bibliotheken als die Standardbibliothek zulässig und keine Helfer zum Parsen, selbst wenn sie sich in der Standardbibliothek befinden. Dies bedeutet, dass der Vergleich nicht durch die leistungsstarken Compiler-Bibliotheken verzerrt werden kann, über die nur einige Befehle verfügen.
  • Es gab nicht nur öffentliche, sondern auch geheime Tests. Sie begannen einmal nach der endgültigen Lieferung. Dies bedeutete, dass es einen Anreiz gab, Ihren eigenen Testcode zu schreiben und sicherzustellen, dass der Compiler zuverlässig und korrekt ist und komplexe Grenzsituationen handhabt.
  • Obwohl alle Teilnehmer Studenten sind, halte ich sie für ziemlich kompetente Programmierer. Jeder von ihnen absolvierte mindestens zwei Jahre lang ein Praktikum, hauptsächlich in High-Tech-Unternehmen, manchmal sogar an Compilern. Fast alle von ihnen programmieren seit 7-13 Jahren und sind Enthusiasten, die außerhalb ihrer Kurse viel im Internet lesen.
  • Der generierte Code wurde nicht berücksichtigt, aber die Grammatikdateien und der Code, der den anderen Code generiert hat, wurden berücksichtigt.

Daher denke ich, dass die Menge an Code ein gutes Verständnis dafür liefert, wie viel Aufwand erforderlich ist, um jedes Projekt zu unterstützen, wenn es langfristig wäre. Ich denke, dass nicht zu viel Unterschied zwischen den Projekten es Ihnen auch erlaubt, einige außergewöhnliche Aussagen zu widerlegen, die ich gelesen habe, zum Beispiel, dass der Haskell-Compiler aufgrund der Sprache mehr als halb so groß wie C ++ sein wird.

Rost (Vergleichsbasis)


Ich und einer meiner Kameraden haben früher jeweils mehr als 10.000 Zeilen in Rust geschrieben, und der dritte Kollege hat vielleicht 500 Zeilen auf einigen Hackathons geschrieben. Unser Compiler wurde in 6806 Zeilen wc -l , 5900 Zeilen der Quelle (ohne Leerzeichen und Kommentare) und 220 KB wc -c .

Ich habe festgestellt, dass in anderen Projekten diese Proportionen mit wenigen Ausnahmen, die ich bemerken werde, grob eingehalten werden. Für den Rest des Artikels meine ich, wenn ich mich auf Zeichenfolgen oder Summen beziehe, wc -l , aber das spielt keine Rolle (es sei denn, ich bemerke den Unterschied), und Sie können mit einem Koeffizienten konvertieren.

Ich habe einen weiteren Artikel geschrieben, der unser Design beschreibt und alle öffentlichen und geheimen Tests bestanden hat. Es enthält auch einige zusätzliche Funktionen, die wir zum Spaß gemacht haben, nicht zum Bestehen von Tests, bei denen wahrscheinlich etwa 400 Zeilen hinzugefügt wurden. Es hat auch ungefähr 500 Zeilen unserer Einheitentests.

Haskell


Zum Haskell-Team gehörten zwei meiner Freunde, die jeweils ein paar tausend Zeilen Haskell geschrieben und viele Online-Inhalte über Haskell und andere ähnliche funktionale Sprachen wie OCaml und Lean gelesen haben. Sie hatten einen anderen Teamkollegen, den ich nicht sehr gut kannte, aber es scheint, dass ein starker Programmierer Haskell zuvor benutzt hat.

Ihr Compiler umfasste insgesamt 9.750 Zeilen wc -l , 357 KB und 7777 Codezeilen (SLOC). Dieses Team hat auch die einzigen signifikanten Unterschiede zwischen diesen Verhältnissen: Ihr Compiler ist 1,4-mal größer als unser in Zeilen, 1,3-mal in SLOC und 1,6-mal in Bytes. Sie haben keine zusätzlichen Funktionen implementiert, 100% der öffentlichen und geheimen Tests bestanden.

Es ist wichtig zu beachten, dass die Einbeziehung von Tests dieses Team am meisten betroffen hat. Da sie sich sorgfältig der Richtigkeit des Codes näherten, umfassten sie 1.600 Testzeilen. Sie haben mehrere Grenzsituationen erfasst, die unser Team nicht erfasst hat, aber diese Fälle wurden einfach nicht durch Kurstests überprüft. Ohne Tests auf beiden Seiten (6,3 Tausend Zeilen gegenüber 8,1 Tausend Zeilen) ist ihr Compiler also nur 30% höher als unser Compiler.

Hier tendiere ich zu Bytes als vernünftigeres Maß für den Volumenvergleich, da es in einem Haskell-Projekt im Durchschnitt längere Zeilen gibt, da es keine große Anzahl von Zeilen aus einer schließenden Klammer enthält und rustfmt nicht einzeilige Funktionsketten in mehrere Zeilen rustfmt .

Nachdem wir mit einem meiner Teamkollegen gestöbert hatten, fanden wir die folgende Erklärung für diesen Unterschied:

  • Wir verwendeten einen handgeschriebenen lexikalischen Analysator und eine rekursive Abstiegsmethode. Sie verwendeten einen NFA- und DFA- Generator und einen LR-Parser und anschließend einen Durchgang, um den Analysebaum in AST ( abstrakter Syntaxbaum , bequemere Darstellung des Codes) zu konvertieren. Dies gab ihnen deutlich mehr Code: 2677 Zeilen im Vergleich zu unserem 1705, ungefähr 1000 Zeilen mehr.
  • Sie verwendeten das phantasievolle generische AST, das zu verschiedenen Typparametern überging, da in jedem Durchgang weitere Informationen hinzugefügt wurden. Diese und weitere Hilfsfunktionen zum Umschreiben erklären wahrscheinlich, warum ihr AST-Code etwa 500 Zeilen länger ist als unsere Implementierung, in der wir Strukturliterale sammeln und Option<_> mutieren, um Informationen hinzuzufügen.
  • Sie haben während der Generierung immer noch ungefähr 400 Codezeilen, die hauptsächlich mit der größeren Abstraktion verbunden sind, die erforderlich ist, um den Code auf rein funktionale Weise zu generieren und zu kombinieren, wobei wir einfach Mutations- und Schreibzeilen verwenden.

Diese Unterschiede plus Tests erklären alle Volumenunterschiede. Tatsächlich sind unsere Dateien für Faltkonstanten und Kontextauflösung sehr eng. Trotzdem gibt es aufgrund längerer Zeilen einen gewissen Unterschied bei den Bytes: Wahrscheinlich, weil mehr Code benötigt wird, um den gesamten Baum in jedem Durchgang neu zu schreiben.

Aus diesem Grund sind Rust und Haskell meiner Meinung nach gleichermaßen ausdrucksstark, vielleicht mit einem leichten Vorteil, da Rust die Mutation leicht verwenden kann, wenn es zweckmäßig ist. Es war auch interessant zu wissen, dass sich meine Wahl der rekursiven Abstiegsmethode und des handgeschriebenen lexikalischen Analysators ausgezahlt hat: Es war ein Risiko, das den Empfehlungen und Anweisungen des Professors widersprach, aber ich entschied, dass es einfacher und richtig war.

Haskell-Fans werden argumentieren, dass dieses Team die Haskell-Funktionen wahrscheinlich nicht voll ausgenutzt hat, und wenn sie die Sprache besser kennen, könnten sie ein Projekt mit weniger Code erstellen. Ich stimme zu, jemand wie Edward Kmett kann denselben Compiler in einer viel geringeren Menge schreiben. In der Tat verwendete das Team meines Freundes nicht viele ausgefallene, hochentwickelte Abstraktionen und ausgefallene Kombinatorbibliotheken wie Lens . All dies beeinträchtigt jedoch die Lesbarkeit des Codes. Alle Leute im Team sind erfahrene Programmierer, sie wussten, dass Haskell zu sehr bizarren Dingen fähig war, entschieden sich jedoch, sie nicht zu verwenden, weil sie beschlossen, dass das Verstehen mehr Zeit in Anspruch nehmen würde als sie speichern und den Code für andere schwieriger zu verstehen machen würden. Dies scheint ein echter Kompromiss zu sein, und die Behauptung, Haskell sei magisch für Compiler geeignet, geht in etwa so: "Haskell erfordert extrem hohe Fähigkeiten beim Schreiben von Compilern, wenn Sie sich nicht für die Codeunterstützung für Leute interessieren, die auch nicht sehr gut mit Haskell umgehen können."

Es ist auch interessant festzustellen, dass der Professor zu Beginn jedes Projekts sagt, dass die Studenten jede Sprache verwenden können, die auf einem Universitätsserver ausgeführt wird, warnt jedoch davor, dass sich die Teams in Haskell von den anderen unterscheiden: Sie haben die größte Streuung in den Noten. Viele Leute überschätzen ihre Fähigkeiten und die Haskell-Teams haben die schlechtesten Noten, obwohl andere genauso gut abschneiden wie meine Freunde.

C ++


Dann habe ich mit meinem Freund vom C ++ - Team gesprochen. Ich kannte nur eine Person in diesem Team, aber C ++ wird in mehreren Kursen an unserer Universität verwendet, sodass wahrscheinlich jeder im Team C ++ - Erfahrung hatte.

Ihr Projekt bestand aus 8733 Zeilen und 280 KB, ohne den Testcode, aber mit etwa 500 Zeilen zusätzlicher Funktionen. Damit ist es 1,4-mal größer als unser Code ohne Tests, der auch etwa 500 Zeilen mit zusätzlichen Funktionen enthält. Sie haben 100% der öffentlichen Tests bestanden, aber nur 90% der geheimen Tests. Vermutlich, weil sie die in der Spezifikation geforderten ausgefallenen vtables-Arrays nicht implementiert haben, die möglicherweise 50 bis 100 Codezeilen belegen.

Ich habe mich nicht zu tief mit diesen Größenunterschieden befasst. Ich denke, das liegt hauptsächlich an:

  • Sie verwenden den LR-Parser und den Baumumschreiber anstelle der rekursiven Abstiegsmethode.
  • Das Fehlen von Summentypen und Mustervergleichen in C ++, die wir weit verbreitet haben und die sehr nützlich waren.
  • Die Notwendigkeit, alle Signaturen in den Header-Dateien zu duplizieren, ist in Rust nicht der Fall.

Wir haben auch die Kompilierungszeit verglichen. Auf meinem Laptop dauert der Clean-Debug-Build unseres Compilers 9,7 s, der Clean-Release 12,5 s und der inkrementelle Debug-Build 3,5 s. Mein Freund hatte keine Zeitangaben für seinen C ++ - Build (unter Verwendung von parallel make), aber er sagte, dass die Zahlen ähnlich sind, mit der Einschränkung, dass sie Implementierungen vieler kleiner Funktionen in die Header-Dateien einfügen, um das Duplizieren von Signaturen auf Kosten einer längeren Zeit zu reduzieren (nämlich Daher kann ich den Netzleitungs-Overhead in den Header-Dateien nicht messen.

Python


Mein Freund, ein sehr guter Programmierer, hat beschlossen, das Projekt alleine in Python zu machen. Sie implementierte auch erweiterte Funktionen (zum Spaß) als jedes andere Team, einschließlich einer SSA-Zwischenansicht mit Registerzuordnung und anderen Optimierungen. Da es alleine funktionierte und viele zusätzliche Funktionen implementierte, achtete es am wenigsten auf die Qualität des Codes, z. B. undifferenzierte Ausnahmen für alle Fehler (basierend auf Backtraces zum Debuggen), anstatt Fehlertypen und entsprechende Meldungen zu implementieren, wie z uns.

Ihr Compiler bestand aus 4581 Zeilen und bestand alle öffentlichen und geheimen Tests. Sie implementierte auch erweiterte Funktionen als jeder andere Befehl, aber es ist schwierig zu bestimmen, wie viel zusätzlicher Code benötigt wurde, da viele der zusätzlichen Funktionen leistungsfähigere Versionen einfacher Dinge waren, die jeder implementieren musste, wie z. B. Faltkonstanten und Generieren von Code. Zusätzliche Funktionen sind wahrscheinlich mindestens 1000 bis 2000 Zeilen, daher bin ich mir sicher, dass ihr Code mindestens doppelt so aussagekräftig ist wie unser.

Ein großer Teil dieses Unterschieds ist wahrscheinlich die dynamische Eingabe. Nur in unseren ast.rs 500 Zeilen mit Typdefinitionen und viele weitere Typen, die an anderer Stelle im Compiler definiert sind. Wir sind auch immer auf das Typensystem selbst beschränkt. Zum Beispiel benötigen wir eine Infrastruktur, um dem AST ergonomisch neue Informationen hinzuzufügen, wenn wir ihn durchlaufen und später darauf zugreifen. In Python können Sie einfach neue Felder auf AST-Knoten festlegen.

Leistungsstarke Metaprogrammierung erklärt auch einen Teil des Unterschieds. Obwohl sie beispielsweise einen LR-Parser anstelle einer rekursiven Abstiegsmethode verwendete, war in meinem Fall meines Erachtens weniger Code erforderlich, da ihre LR-Grammatik anstelle einer Baumumschreibung Python-Codeteile zum Erstellen des AST enthielt, den der Generator in Python-Funktionen umwandeln konnte mit eval . Ein Grund dafür, dass wir den LR-Parser nicht verwendet haben, ist, dass das Erstellen eines AST ohne Umschreiben des Baums viel Zeremonie erfordert (entweder Rust-Dateien oder prozedurale Makros erstellen), um die Grammatik mit Fragmenten des Rust-Codes zu verknüpfen.

Ein weiteres Beispiel für die Leistungsfähigkeit der Metaprogrammierung und der dynamischen Typisierung ist die 400- visit.rs Datei visit.rs , bei der es sich im Grunde um einen sich wiederholenden Boilerplate-Code handelt, der einen Besucher in einer Reihe von AST-Strukturen implementiert. In Python kann dies eine kurze Funktion von ungefähr 10 Zeilen sein, die die Felder eines AST-Knotens rekursiv __dict__ und sie besucht (unter Verwendung des Attributs __dict__ ).

Als Fan von Rust und statisch typisierten Sprachen im Allgemeinen möchte ich feststellen, dass das Typensystem sehr nützlich ist, um Fehler zu vermeiden und die Leistung zu verbessern. Ungewöhnliche Metaprogrammierungen können es auch schwierig machen zu verstehen, wie der Code funktioniert. Dieser Vergleich überraschte mich jedoch durch die Tatsache, dass ich nicht erwartet hatte, dass der Unterschied in der Codemenge so groß sein würde. Wenn der Unterschied insgesamt wirklich nahe daran liegt, doppelt so viel Code schreiben zu müssen, halte ich Rust immer noch für einen geeigneten Kompromiss, aber immer noch halb so viel Code ist ein Argument, und in Zukunft tendiere ich dazu, etwas in Ruby / Python zu tun wenn Sie nur schnell etwas alleine bauen und es dann wegwerfen müssen.

Rust (eine andere Gruppe)


Der interessanteste Vergleich für mich war mit meinem Freund, der auch ein Projekt in Rust mit einem Teamkollegen (den ich nicht kannte) durchführte. Mein Freund hatte eine gute Rust Erfahrung. Er hat zur Entwicklung des Rust-Compilers beigetragen und viel gelesen. Ich weiß nichts über seinen Kameraden.

Ihr Projekt bestand aus 17.211 Rohzeilen, 15.000 Quellzeilen und 637 KB, ohne den Testcode und den generierten Code. Es hatte keine zusätzlichen Funktionen und bestand nur 4 von 10 geheimen Tests und 90% der öffentlichen Tests für die Codegenerierung, da sie vor Ablauf der Frist nicht genügend Zeit hatten, um bizarrere Teile der Spezifikation zu implementieren. Ihr Programm ist dreimal größer als unser, in derselben Sprache geschrieben und mit weniger Funktionalität!

Dieses Ergebnis war wirklich erstaunlich für mich und überschattete alle Unterschiede zwischen den Sprachen, die ich bisher gelernt habe. Aus diesem Grund haben wir die Listen der wc -l Dateigrößen verglichen und auch überprüft, wie jeder von uns bestimmte Dinge implementiert hat, die zu unterschiedlichen Codegrößen geführt haben.

Es scheint, dass alles auf die konsequente Annahme verschiedener Entwurfsentscheidungen hinausläuft. Zum Beispiel benötigt ihr Frontend (lexikalische Analyse, Analyse, Erstellung von AST) 7597 Zeilen gegenüber unserem 2164. Sie verwendeten den lexikalischen DFA-Analysator und den LALR-Parser (1), aber andere Gruppen machten ähnliche Dinge ohne so viel Code. Als ich mir ihre Weeder-Datei ansah, bemerkte ich eine Reihe von Designentscheidungen, die sich von unseren unterschieden:

  • Sie entschieden sich für die Verwendung eines vollständig typisierten Analysebaums anstelle eines standardmäßigen, einheitlichen, auf Zeichenfolgen basierenden Analysebaums. Dies erforderte wahrscheinlich viel mehr Typdefinitionen und zusätzlichen Konvertierungscode in der Analysephase oder einen komplexeren Parser.
  • Sie verwendeten Tryfrom- tryfrom Implementierungen, um zwischen Parsing-Baumtypen und AST-Typen zu konvertieren und diese zu validieren. Dies führt zu vielen 10-20-Zeilen- impl Blöcken. Zu diesem Zweck haben wir Funktionen verwendet, die Result , wodurch weniger Zeilen generiert werden. Außerdem werden wir ein wenig von der Typstruktur befreit, was die Parametrisierung und Wiederverwendung vereinfacht. Einige der Dinge, die für uns einzeilige match Zweige waren, hatten 10-zeilige impl Blöcke.
  • Unsere Typen sind so strukturiert, dass das Kopieren und Einfügen reduziert wird. Beispielsweise verwendeten sie separate Felder is_abstract , is_native und is_static , in denen der Code für die Einschränkungsprüfung zweimal kopiert werden musste: einmal für Methoden vom Typ void und einmal für Methoden mit Rückgabetyp mit geringfügigen Änderungen. Während unsere void nur ein spezieller Typ war, haben wir eine Taxonomie von Modifikatoren mit mode und visibility , die Einschränkungen auf visibility anwendeten, und Einschränkungen wurden standardmäßig für den Übereinstimmungsoperator generiert, wodurch die Modifikatorsätze in mode und visibility .

Ich habe mir den Code der Durchläufe der Analyse ihres Compilers nicht angesehen, aber sie sind auch großartig. Ich habe mit meinem Freund gesprochen, und es scheint, dass sie nichts Ähnliches wie die Infrastruktur von Besuchern implementiert haben, wie unsere. Ich denke, dass dies zusammen mit einigen anderen kleineren Designunterschieden den Größenunterschied dieses Teils erklärt. Der Besucher lässt zu, dass sich unsere Analysepässe nur auf die Teile des AST konzentrieren, die er benötigt, anstatt das Muster über die gesamte AST-Struktur hinweg abzugleichen. Dies spart viel Code.

Ihr Teil für die Codegenerierung besteht aus 3594 Zeilen und unser Teil - 1560. Ich habe mir ihren Code angesehen und es scheint, dass fast der gesamte Unterschied darin besteht, dass sie eine Zwischendatenstruktur für Assembler-Anweisungen gewählt haben, bei der wir nur die Zeichenfolgenformatierung für die direkte Assembler-Ausgabe verwendet haben . Sie mussten Typen und Ausgabefunktionen für alle verwendeten Anweisungen und Operandentypen definieren. Dies bedeutete auch, dass die Montageanleitung für den Bau mehr Code benötigte. Wo wir einen mov ecx, [edx] mit kurzen Anweisungen hatten, wie z. B. mov ecx, [edx] , brauchten sie einen riesigen rustfmt Operator, der in 6 Zeilen unterteilt war und eine Anweisung mit einer Reihe verschachtelter Zwischentypen für Operanden mit bis zu 6 Ebenen verschachtelter Klammern erstellte. Wir könnten auch Blöcke verwandter Anweisungen, wie z. B. eine Funktionspräambel, in einer einzigen Formatanweisung ausgeben, in der die vollständige Konstruktion für jede Anweisung angegeben werden muss.

Unser Team erwog, eine solche Abstraktion wie ihre zu verwenden. Es war einfacher, entweder eine Textassembly auszugeben oder Maschinencode direkt auszugeben, dies war jedoch keine Voraussetzung für den Kurs. Dasselbe könnte mit weniger Code und besserer Leistung unter Verwendung des X86Writer- X86Writer mit Methoden wie push(reg: Register) . Wir haben auch berücksichtigt, dass dies das Debuggen und Testen vereinfachen könnte, aber wir haben festgestellt, dass das Anzeigen des generierten Textassemblers mithilfe von Snapshot-Tests einfacher zu lesen und zu testen ist, wenn Sie Kommentare großzügig einfügen. Aber wir haben (anscheinend richtig) vorausgesagt, dass es viel zusätzlichen Code erfordern würde, und es gab keinen wirklichen Nutzen angesichts unserer wirklichen Bedürfnisse, also machten wir uns keine Sorgen.

Es ist gut, dies mit der Zwischendarstellung zu vergleichen, die das C ++ - Team als zusätzliche Funktion verwendet hat und für die nur 500 zusätzliche Zeilen benötigt wurden. Sie verwendeten eine sehr einfache Struktur (für einfache Typdefinitionen und Build-Code), die Operationen verwendete, die den Anforderungen von Java nahe kamen. Dies bedeutete, dass ihre Zwischendarstellung viel kleiner war (und daher weniger Build-Code erforderte) als der resultierende Assembler, da viele Sprachoperationen wie Aufrufe und Casts in viele Assembler-Anweisungen erweitert wurden. Sie sagen auch, dass es wirklich beim Debuggen geholfen hat, da es viel Müll herausgeschnitten und die Lesbarkeit verbessert hat. Eine übergeordnete Präsentation ermöglichte auch einige einfache Optimierungen der Zwischendarstellung. Das C ++ - Team hat ein wirklich gutes Design entwickelt, das sie mit viel weniger Code viel besser macht.

Im Allgemeinen scheint der gemeinsame Grund für den dreifachen Unterschied im Volumen in der konsequenten Übernahme verschiedener Entwurfsentscheidungen, sowohl großer als auch kleiner, in Richtung mehr Code zu liegen. Sie haben eine Reihe von Abstraktionen implementiert, die wir nicht implementiert haben - sie haben mehr Code hinzugefügt und einige unserer Abstraktionen übersprungen, wodurch sich die Codemenge verringert.

Dieses Ergebnis hat mich wirklich überrascht. Ich wusste, dass Designentscheidungen wichtig sind, aber ich hätte nicht im Voraus vermutet, dass sie zu Unterschieden dieser Größe führen würden, da ich nur Personen untersuchte, die ich als starke kompetente Programmierer betrachte. Von allen Vergleichsergebnissen ist dies für mich das wichtigste.Es hat mir wahrscheinlich geholfen, dass ich vor dem Besuch dieses Kurses viel darüber gelesen habe, wie man Compiler schreibt, damit ich intelligente Projekte verwenden kann, die andere Leute entwickelt haben und die gut funktionieren, wie AST-Besucher und die Methode der rekursiven Abstammung, obwohl sie nicht unterrichtet wurden auf unserem Kurs.

Was mich wirklich zum Nachdenken gebracht hat, sind die Kosten der Abstraktion. Abstraktionen können die zukünftige Erweiterung erleichtern oder vor bestimmten Arten von Fehlern schützen. Sie müssen jedoch berücksichtigt werden, da Sie dreimal so viel Code zum Verstehen und Umgestalten erhalten, dreimal so viele mögliche Fehlerstellen und weniger Zeit zum Testen und weiter Entwicklung. Unser Schulungskurs war anders als in der realen Welt: Wir wussten mit Sicherheit, dass wir den Code nach der Entwicklung niemals berühren würden. Dadurch entfallen die Vorteile einer proaktiven Abstraktion. Wenn ich jedoch auswählen müsste, welcher Compiler mit einer beliebigen Funktion erweitert werden soll, was Sie später sagen werden, würde ich unseren auswählen, ohne meine Vertrautheit damit zu berücksichtigen. Nur weil es viel weniger Code zu verstehen gibt und ich möglicherweise die beste Abstraktion für die Anforderungen auswählen könnte (z.Zwischendarstellung des C ++ - Befehls), wenn ich die spezifischen Anforderungen kenne.

Meiner Ansicht nach wurde auch die Taxonomie von Abstraktionen gestärkt: Es gibt solche, die den Code reduzieren und nur die aktuellen Anforderungen berücksichtigen, wie unsere Besuchervorlage, und es gibt Abstraktionen, die Code hinzufügen, aber die Vorteile der Erweiterbarkeit, des Debuggens oder der Korrektheit bieten.

Scala


Ich habe auch mit einem Freund gesprochen, der im letzten Semester ein Projekt über Scala gemacht hat, aber das Projekt und die Tests waren genau gleich. Ihr Compiler bestand aus 4141 Zeilen und ~ 160 KB Code, ohne die Tests. Sie haben 8 von 10 geheimen Tests und 100% offenen Tests bestanden und keine zusätzlichen Funktionen implementiert. Im Vergleich zu unseren 5906 Zeilen ohne zusätzliche Funktionen und Tests ist ihr Compiler also 30% weniger.

Einer der kleinen Designfaktoren war ein anderer Ansatz zum Parsen. Der Kurs ermöglichte die Verwendung eines Befehlszeilentools für den LR-Tabellengenerator. Niemand außer diesem Team hat es benutzt. Dies ersparte ihnen die Implementierung des LR-Tabellengenerators. Sie konnten auch vermeiden, LR-Grammatik mit einem Python-Skript mit 150 Zeilen zu schreiben, das die im Internet gefundene Java-Grammatik-Webseite kratzte und in das Eingabeformat des Generators übersetzte. Sie mussten in Scala noch eine Art Baum bauen, aber im Allgemeinen betrug die Analysephase 1073 Zeilen im Vergleich zu unserer 1443, obwohl unsere Gradientenabstiegsmethode hier einen Volumenvorteil gegenüber allen anderen Teams bot.

Der Rest ihres Compilers war auch kleiner als unser, ohne offensichtliche große Designunterschiede, obwohl ich mich nicht mit dem Code befasst habe. Ich vermute, dass dies auf Unterschiede in der Ausdruckskraft von Scala und Rust zurückzuführen ist. Scala und Rust verfügen über ähnliche Programmierfunktionen, die für Compiler nützlich sind, z. B. den Mustervergleich. Der verwaltete Speicher von Scala speichert jedoch den Code, der für die Funktion des Leihprüfers in Rust erforderlich ist. Darüber hinaus hat Scala einen vielfältigeren syntaktischen Zucker als Rust.

OCaml


Da alle Mitglieder unseres Teams ein Praktikum bei Jane Street (Technologiehandelsunternehmen - ca. Per.) Machen, war ich besonders daran interessiert, das Ergebnis anderer ehemaliger Jane Street-Praktikanten zu betrachten, die OCaml als Autor des Compilers ausgewählt haben.

Ihr Compiler bestand aus 10.914 Zeilen und 377 KB, einschließlich einer kleinen Menge Testcode und ohne zusätzliche Funktionen. Sie haben 9/10 Geheimtests und alle öffentlichen Tests bestanden.

Wie bei anderen Gruppen scheint der Hauptunterschied in der Größe auf die Verwendung des LR-Parsers und des Umschreibens von Bäumen zum Parsen sowie der Regex-> NFA-> DFA-Konvertierungspipeline für die lexikalische Analyse zurückzuführen zu sein. Ihr Frontend (lexikalische Analyse, Analyse, AST-Konstruktion) besteht aus 5548 Zeilen und unserem - 2164, mit ähnlichen Verhältnissen für Bytes. Sie verwendeten auch Tests für ihren Parser mit der Erwartung, dass dies unseren Snapshot-Tests ähnlich war, bei denen die erwartete Ausgabe außerhalb des Codes lag, sodass ihre Parser-Tests ~ 600 Zeilen der Gesamtzahl und unserer - etwa 200 - ergaben.

Damit verbleiben 5366 Zeilen für den Rest des Compilers (461 Zeilen davon sind Schnittstellendateien mit Typdeklarationen) und 4642 für uns. Der Unterschied beträgt nur 15%, wenn wir ihre Schnittstellendateien zählen, und fast die gleiche Größe, wenn wir nicht zählen. Abgesehen von unseren Parsing-Design-Lösungen scheinen Rust und OCaml gleichermaßen ausdrucksstark zu sein, außer dass OCaml Front-End-Dateien benötigt und Rust nicht.

Fazit


Generell bin ich sehr froh, dass ich diesen Vergleich gemacht habe, viel gelernt habe und viele Male überrascht war. Ich denke, die allgemeine Schlussfolgerung ist, dass Designentscheidungen viel wichtiger sind als Sprache, aber Sprache ist wichtig, weil sie Ihnen Werkzeuge für die Implementierung verschiedener Designs bietet.

Source: https://habr.com/ru/post/de456638/

More articles:


All Articles