Qualitativ hochwertige LISP / Scheme-Compiler, die mit C / C ++ konkurrieren können

Ist es theoretisch möglich, einen Lisp / Scheme-Compiler zu haben, der Code erzeugen kann, der mit kompiliertem C konkurrieren kann, sagen wir innerhalb einer Marge von 15-25%?

Bei meinen Tests habe ich festgestellt, dass die aktuelle Anzahl von Compilern (Bigloo, SBCL, Gambit, Chicken usw.) 20-50-mal langsamer ist als der entsprechende C-Code .

Der einzige Ausreißer ist der Stalin-Compiler . Bei einfachen Programmen werden Binärdateien erzeugt, die C entsprechen. Was ich jedoch verdächtig finde, ist, dass keines der anderen Projekte (Bigloo, Chicken, Clozure usw.) versucht hat, die von Stalin verwendeten Tricks umzusetzen ("Optimierung des gesamten Programms"). usw).

Ich bin seit Mitte der 90er Jahre ein großer Fan von LISP und würde es gerne an Bord bringen, damit mein Team Projekte in der Hälfte der Zeit, die normalerweise mit C / C ++ /. NET / etc benötigt wird, herausbringen kann, aber ... die Leistung Probleme sind eine große Hürde.

Ich frage mich, ob der Mangel an hochwertigen LISP-Compilern darauf zurückzuführen ist, dass keine ernsthafte Zeit und kein ernsthaftes Geld in das Thema investiert wurden, ODER ob dies angesichts des aktuellen Standes der Compilertechnologie einfach keine realisierbare Aufgabe ist.

Wie in den Kommentaren erwähnt, ist es nicht sehr genau anzugeben, "dass die aktuelle Anzahl der Compiler (Bigloo, SBCL, Gambit, Chicken usw.) 20-50-mal langsamer ist als der entsprechende C-Code", ohne zu qualifizieren, wie und was Sie getestet haben du hast getestet.

Für meine Verwendung stelle ich fest, dass Gambit und Chicken Scheme für viele Dinge in der Geschwindigkeit dem entsprechenden C-Code ziemlich nahe kommen, wobei die aktuelle Version von Gambit (4.7.3) im Allgemeinen schneller als Chicken (4.9.0.1) ist, jedoch älter als vor -optimierenDer ausgegebene 'C'-Code (der Annahmen über die Anzahl der verfügbaren Register trifft - setzt x686 voraus - und die Verwendung des Stapelspeichers für zusätzliche Speicheranforderungen erzwingt, welche Entscheidungen dem' C'-Compiler wie Chicken überlassen werden sollten, was häufig eliminiert das Erfordernis zusätzlicher Register und kombinierter Verarbeitungsschritte), um zu verhindern, dass der 'C'-Compiler seine eigenen Optimierungen vornimmt, was dazu führt, dass sehr enge kleine Schleifen bis zu etwa doppelt so langsam sind wie dieselben engen kleinen Schleifen in' C '(oder Chicken) ); Chicken definiert nur so viele Variablen, die für eine bestimmte Funktion lokal sind, wie es angemessen erscheint (meistens unveränderlich verwendet), und hängt dann vom Compiler ab, um die meisten davon zu optimieren. Huhn nicht

EDIT_ADD: Ich habe die Versionen des Chicken- und Gambit-C-Schemas genauer untersucht und Folgendes festgestellt:

1. Chicken ist aus dem oben genannten Grund schneller als Gambit für kleine enge Schleifen (hängt mehr vom 'C'-Compiler für Optimierungen ab, ohne selbst so viel zu tun, und nutzt daher die zusätzlichen x86-64-Register besser aus), aber auch, weil es keine enthält eine "POLL" -Stapel-Wartungsprüfung in den Schleifen, während Gambit die "POLL" -Prüfung in der Schleife enthält. Selbst wenn dies nicht ausgelöst wird (der übliche Fall), dauert es mehrere CPU-Taktzyklen, um festzustellen, dass nichts erforderlich ist (ca. 6 Zyklen). Ein zukünftiger intelligenterer Compiler sieht möglicherweise, dass es nicht erforderlich ist, eine Stapelprüfung durchzuführen, wenn er sich in einer engen Schleife befindet und keine Stapelerstellungsvorgänge ausführt. Führen Sie diese unmittelbar vor oder nach der Schleife durch und sparen Sie diese Zeit.

2. Die 'C'-Makros von Gambit leisten, wie gesagt, zu viel Arbeit, um genau zu definieren, wie die Operationen ausgeführt werden sollen, insbesondere einschließlich Operationen mit fester Stapelgröße, und diese sind für den' C'-Compiler wahrscheinlich schwieriger zu optimieren. Eine effektivere Verwendung von Registern könnte die Zeit für enge Schleifen um vielleicht 4 Zyklen reduzieren, was sie in Kombination mit den oben genannten in den Hühnerstall bringen würde.

3. Weder geben "Lese- / Änderungs- / Schreib" -Optimierungen für beispielsweise Vektoroperationen aus, die an Ort und Stelle geändert werden, noch geben sie Code aus, damit der Compiler dies tut. Ein intelligenteres Backend wie LLVM in Verbindung mit Haskell macht so etwas. Dies würde die Registernutzung um eins und die Ausführungszeit reduzieren, indem nur ein einziger Befehl anstelle eines separaten Lesens, Berechnens der Modifikation und Schreiben an denselben Ort verwendet wird. Dies wäre nur eine Berechnung der Modifikation (sagen wir ein bisschen oder) und dann eine Lese-Modifikation (| =), die einen einzelnen Befehl schreibt. Dies könnte die Geschwindigkeit um einen Zyklus oder so beschleunigen

4. Beide sind dynamisch typisiert und verarbeiten Daten-Tag-Bits als Teil ihrer Daten. Weder sind intelligent genug für enge Schleifen, um die Tags zu reduzieren, führen Sie die Schleife "tag-less" aus und fügen Sie die Tags dann wieder hinzu, um Ergebnisse aus der Schleife zu erhalten, noch erzeugen sie Code, wo der 'C'-Compiler dies sehen kann In einigen Fällen werden diese Operationen kombiniert. Durch die Optimierung können die Schleifenzeiten je nach Schleife um einige CPU-Zyklen oder so reduziert werden.

5. Sehr enge C-Schleifen können auf einer schnellen CPU, bei der die Zugriffsgeschwindigkeit des Speichercaches nicht gedrosselt ist, etwa 3,5 CPU-Taktzyklen pro Schleife dauern (z. B. AMD Bulldozer, der etwa doppelt so langsam ist). Die gleiche Schleife in Chicken dauert derzeit ungefähr 6 Zyklen und Gambit dauert ungefähr 16,9 Zyklen. Bei all den Optimierungen wie oben gibt es keinen Grund, warum diese Implementierungen des Schemas dies nicht konnten, es sind jedoch einige Arbeiten erforderlich:

6. Im Fall von Gambit könnte die härtere Arbeit darin bestehen, die Flussanalyse zu verbessern, um zu erkennen, wann keine "POLL" -Tests eingefügt werden müssen (dh könnte dies Interrupt-gesteuert sein, obwohl der Compiler das Deaktivieren von Interrupts für einige Verwendungszwecke zulässt? ); Die einfachere Verbesserung wäre, einfach eine bessere Registernutzung zu implementieren (dh x86-64-Register besser zu erkennen als die Standard-x686-Architektur). Für beide ist eine bessere Flussanalyse erforderlich, um zu erkennen, dass sie die Daten, insbesondere "Fixnum" -, "Flonum" - und Vektordaten, "entmarkieren" können, sodass diese Operationen nicht in engen Schleifen und beim Kombinieren von Lese- / Änderungs- / Schreibanweisungen erforderlich sind. Beide Ziele könnten durch die Verwendung eines besseren Backends wie LLVM erreicht werden (kein trivialer Arbeitsaufwand, aber beide sind bereits teilweise vorhanden).

Fazit: Chicken ist derzeit auf den schnellsten CPUs etwa 50% langsamer als "C" (nicht mein Bulldozer, wo es aufgrund der Cache-Drosselung des "C" -Codes ungefähr die gleiche Geschwindigkeit hat) und Gambit ist etwa 400% langsamer (nur etwa " 125% langsamer auf meinem langsamen Bulldozer). Zukünftige Verbesserungen an den Compilern könnten dies jedoch reduzieren, sodass entweder der Code nicht langsamer als 'C' oder innerhalb des vom OP angegebenen Bereichs ist.

Eine komplexere Sprache wie Haskell, wenn Sie das LLVM-Backend verwenden, die strikte Verwendung sorgfältig beachten (kein Problem mit dem standardmäßig immer eifrigen Schema) und geeignete Datenstrukturen verwenden (ST-Arrays ohne Box anstelle von Listen für enge Schleifen; etwas anwendbar auf Schema unter Verwendung von Vektoren), läuft ungefähr mit der gleichen Geschwindigkeit wie 'C', wenn das LLVM-Backend mit vollständigen Optimierungen verwendet wird. Wenn dies möglich ist, kann Scheme dies auch mit den oben genannten Compiler-Verbesserungen tun.

WIEDER ist keines davon 20- bis 50-mal so langsam, wenn es mit geeigneten Optimierungsflags verwendet wird. END_EDIT_ADD

Natürlich werden alle Benchmarks ungültig, wenn nicht wie in einer Produktionsumgebung die entsprechenden Optimierungseinstellungen für jeden verwendet werden ...

Ich würde denken, dass der kommerzielle Chez Scheme-Compiler in der Lage wäre, Hochleistungs-Output zu produzieren, ebenso wie Gambit und Chicken, da er kommerziell ist, hat er sicherlich "ernsthafte Zeit und Geld investiert".

Die einzige Möglichkeit, Gambit oder Chicken so langsam wie "20 bis 50 Mal langsamer als 'C'" laufen zu lassen, besteht darin, keine Optimierungseinstellungen zu verwenden. In diesem Fall laufen sie oft nicht viel schneller als in ihren REPLs interpretiert - Zehnmal langsamer als bei Verwendung dieser Einstellungen.

Ist es möglich, dass das OP diese Einstellungen nicht richtig getestet hat?

Wenn das OP seine Testverfahren klären möchte, werde ich diese Antwort gerne bearbeiten, um zu zeigen, dass zumindest Gambit und Chicken nicht so langsam sein müssen.