Aufgabe: "Summiere die ersten 15.000.000 geraden Zahlen."
Haskell:
%Vor% ... aber MySum braucht Ewigkeiten. Genauer gesagt, etwa 10-20 mal langsamer als C / C ++.
Viele Male habe ich herausgefunden, dass eine Haskell-Lösung, die auf natürliche Weise codiert ist, ungefähr zehnmal langsamer ist als C. Ich habe erwartet, dass GHC ein sehr sauberer Compiler und eine solche Aufgabe ist, die so schwierig scheint.
Man würde also etwas 1,5 bis 2 mal langsamer als C erwarten. Wo ist das Problem?
Kann das besser gelöst werden?
Dies ist der C-Code, mit dem ich es vergleiche:
%Vor%Edit 1 : Ich weiß wirklich, dass es in O (1) berechnet werden kann. Bitte, widerstehen.
Edit 2 : Ich weiß wirklich, dass even [2,4..] ist, aber die Funktion even könnte etwas anderes O(1) sein und muss als Funktion implementiert werden.
Seien Sie also nicht überrascht, wenn Sie Listen als Schleifenersatz verwenden, erhalten Sie langsameren Code, wenn der Schleifenkörper klein ist.
%Vor% sum ist kein "guter Konsument", daher ist GHC (noch) nicht in der Lage, die Zwischenlisten vollständig zu eliminieren.
Wenn Sie mit Optimierungen kompilieren (und nat nicht exportieren), ist GHC intelligent genug, um filter mit der Enumeration zu fusionieren,
Aber das ist so weit, wie die Fusion von GHC es braucht. Sie bleiben mit dem Boxen Int s und dem Konstruieren von Listenzellen. Wenn Sie es eine Schleife geben, wie Sie es dem C-Compiler geben,
Sie erhalten die ungefähre Relation der Laufzeiten zwischen der C- und der Haskell-Version, die Sie erwartet haben.
Diese Art von Algorithmus ist nicht das, was GHC gelernt hat, um es gut zu optimieren, es gibt größere Fische, die anderswo frittiert werden müssen, bevor die begrenzten Manpower in diese Optimierungen gesteckt wird.
Das Problem, warum Listenfusion hier nicht funktionieren kann, ist eigentlich eher subtil. Angenommen, wir definieren das richtige RULE , um die Liste zu verschmelzen:
(Die kurze Erklärung ist, dass wir sum2 als Alias von sum definieren, was verbietet, dass GHC früh inline wird, also hat RULE eine Chance zu feuern, bevor sum2 eliminiert wird. Dann schauen wir für sum2 direkt neben dem Listengenerator build (siehe Definition ) und durch direkte Arithmetik ersetzen.)
Dies hat gemischten Erfolg, da es den folgenden Kern ergibt:
%Vor% Was ist ein schöner, vollständig fusionierter Code - mit dem einzigen Problem, dass wir in einer Nicht-Tail-Call-Position einen Aufruf an $wgo haben. Dies bedeutet, dass wir nicht auf eine Schleife schauen, sondern tatsächlich auf eine tief rekursive Funktion mit vorhersagbaren Programm-Ergebnissen:
Das Hauptproblem besteht darin, dass die Listenfusion des Preludes nur rechte Falten fusionieren kann und die Berechnung der Summe als eine direkte Falte direkt den übermäßigen Stapelverbrauch verursacht.
Die naheliegende Lösung wäre, ein Fusions-Framework zu verwenden, das tatsächlich mit linken Falten umgehen kann, wie Duncans stream-fusion-Paket , die tatsächlich sum fusion implementiert.
Eine andere Lösung wäre, sie zu hacken - und die linke Falte mit einer rechten Falte zu implementieren:
%Vor% Dies erzeugt tatsächlich nahezu perfekten Code mit aktuellen Versionen von GHC. Auf der anderen Seite ist dies im Allgemeinen eine gute Idee, da es darauf angewiesen ist, dass GHC intelligent genug ist, die teilweise angewandten Funktionen zu eliminieren. Bereits das Hinzufügen eines filter in die Kette wird diese spezielle Optimierung durchbrechen.
Erstens kannst du schlau sein, als der junge Gauss und die Summe in O (1 ) .
Spaß beiseite, Ihre Haskell-Lösung verwendet Listen. Ich bin mir ziemlich sicher, dass Ihre C / C ++ Lösung dies nicht tut. (Haskell-Listen sind sehr einfach zu verwenden, daher ist man versucht, sie auch in Fällen zu verwenden, in denen dies nicht angebracht ist.) Versuchen Sie, dies zu vergleichen:
%Vor% Kompilieren Sie es mithilfe von GHC mit -O2 -Argument . Diese Funktion ist tailrecursive , sodass der Compiler sie sehr effizient implementieren kann.
Update: Wenn Sie even function verwenden möchten, ist es möglich:
Sie können die Filterfunktion auch einfach zu einem Parameter machen:
%Vor% Es ist noch eine Sache zu beachten, dass nats und evens sogenannte Constant Applicative Forms oder kurz CAFs sind. Im Wesentlichen entsprechen diese Top-Level-Definitionen ohne Argumente. CAFs sind ein bisschen eine seltsame Ente, zum Beispiel der Grund für die gefürchtete Monomorphismus-Beschränkung; Ich bin mir nicht sicher, ob die Sprachdefinition sogar erlaubt, dass CAFs inline sind.
In meinem mentalen Modell, wie Haskell ausführt, wird dumbSum zu dem Zeitpunkt, zu dem evens einen Wert zurückgibt, so ausgewertet, dass es etwa wie 2:4: ... : 30000000 : <thunk> und nats bis 1:2: ... : 30000000 : <thunk> aussieht, wobei <thunk> s repräsentieren etwas, das noch nicht angeschaut wurde. Wenn mein Verständnis stimmt, müssen diese Zuordnungen von : passieren und können nicht weg optimiert werden.
Eine Möglichkeit, Dinge zu beschleunigen, ohne den Code zu sehr zu verändern, wäre einfach zu schreiben:
%Vor%oder
%Vor% Auf meinem Rechner, der mit -O2 kompiliert wurde, scheint das allein zu einer Beschleunigung von etwa 30% zu führen.
Ich bin kein GHC-Kenner (ich habe noch nie ein Haskell-Programm profiliert!), also könnte ich sehr daneben sein.