Ich lerne Haskell und versuche so schnell wie möglich in C zu schreiben. Für diese Übung schreibe ich eine Euler Integrator für ein einfaches eindimensionales physikalisches System.
-O3 kompiliert. Es läuft in 1.166 Sekunden. -O3 kompiliert. Es läuft in 21.3 Sekunden. -O3 -fllvm kompiliere, läuft es in 4.022 Sekunden. Also, fehlt mir etwas, um meinen Haskell-Code zu optimieren?
PS.: Ich habe die folgenden Argumente verwendet: 1e-8 5 .
C-Code:
%Vor%Haskell Code:
%Vor% Ich habe einen schönen Schub bekommen, indem ich eine Worker-Wrapper-Transformation auf runEuler angewendet habe.
Dies hilft f , in die Schleife eingezeichnet zu werden (was wahrscheinlich auch in der C-Version passiert), wodurch viel Aufwand vermieden wird.
Die wichtigsten Punkte wurden bereits erwähnt von hammar und von Philip JF . Aber lass mich sie sammeln und ein wenig Erklärung hinzufügen.
Ich werde von oben nach unten fortfahren.
%Vor% Ihr Typ hat strikte Felder. Wenn also ein Objekt dieses Typs nach WHNF ausgewertet wird, werden seine Felder ebenfalls nach WHNF ausgewertet. In diesem Fall wird das Objekt vollständig ausgewertet. Das ist gut, aber in unserem Fall leider nicht gut genug. Objekte dieses Typs können immer noch mit Zeigern zu den Rohdaten konstruiert werden, anstatt die Rohdaten in den Konstruktor zu entpacken, und genau das passiert mit dem Beschleunigungsfeld (modulo die Tatsache, dass die Schleife den Typ nicht direkt verwendet, sondern übergibt die Komponenten als Argumente). Da dieses Feld nicht in euler verwendet wird, erhalten Sie
eine Schleife mit einem Boxed Argument dort. Das bedeutet, dass in jeder Iteration einige Double# s eingerahmt und einige Double s nicht gerahmt werden müssen. Boxen und Unboxing sind keine sehr teuren Operationen, aber in einer Schleife, die sonst eng wäre, können sie eine Menge Leistung kosten. Eine weitere Instanz des gleichen Boxing / Unboxing-Problems ist mit dem Argument vom Typ EulerFunction verbunden, mehr dazu später. -funbox-strict-fields als vorgeschlagen von Philp JF , oder ein {-# UNPACK #-} pragma auf mindestens das Beschleunigungsfeld hilft hier, aber die Unterschied wird erst relevant, wenn auch das Boxing / Unboxing für die Funktionsauswertung eliminiert wird.
Sie übergeben (** 2) hier als Argument. Das ist nicht die gleiche Funktion wie in C, die entsprechende C-Funktion wäre return pow(t,2); , und mit meinem gcc verdoppelt sich die Laufzeit für das C-Programm (kein Unterschied für clang). Das große Leistungsproblem dabei ist, dass (**) eine langsame Funktion ist. Da (** 2) für viele Argumente unterschiedliche Ergebnisse von \x -> x*x hat, gibt es keine Rewrite-Regel dafür, also bekommt man diese langsame Funktion mit GHCs nativem Codegenerator (es scheint, dass LLVM sie durch \x -> x*x trotzdem von der riesigen ersetzt Leistungsunterschied der beiden GHC-Backends und das Clangergebnis). Wenn Sie (\x -> x*x) oder (^ 2) anstelle von (** 2) übergeben, erhalten Sie die Multiplikation (es gibt eine Rewrite-Regel für (^ 2) seit 7.4). An diesem Punkt, auf meinem System, gibt es keinen großen Unterschied zwischen der Leistung des NCG-generierten Codes und der LLVM-generierten, aber die NCG ist etwa 10% schneller .
Jetzt das große Problem
%Vor% runEuler ist rekursiv und kann daher nicht inlined sein. Das bedeutet, dass die übergebene Funktion auch dort nicht inline sein kann und die Argumente dt und limit auch für jede Iteration übergeben werden. Dass die Funktion nicht inline sein kann, bedeutet, dass das Argument in der Schleife eingerahmt sein muss, bevor es an die Funktion übergeben wird, und das Ergebnis muss dann entkoppelt werden. Das ist teuer. Und es bedeutet, dass keine Optimierungen vorgenommen werden können, die nach dem Einfügen des Funktionsarguments vorgenommen werden könnten.
Wenn Sie die von hammar vorgeschlagene tun
im Vergleich zu
%Vor%des Originals.
Zusammen erreicht das ungefähr die Hälfte der Geschwindigkeit des C-Programms mit dem nativen Code-Generator und die gleiche Geschwindigkeit mit dem LLVM-Backend auf meiner Box (der native Code-Generator ist nicht besonders gut beim Optimieren von Schleifen, während LLVM ist, da Schleifen sind in vielen Sprachen sehr verbreitet, die über LLVM kompiliert werden.)
Ich habe im Moment keinen funktionierenden LLVM, aber ich komme mit
um einen Faktor von zwei-O2 anstelle von -O3 in GHC (obwohl ich bezweifle, dass es darauf ankommt, -O3 wird nicht beibehalten) -funbox-strict-fields
x*x anstelle von x ** 2 (entspricht Ihrem C-Code) dh
%Vor%Sie können es wahrscheinlich weiter vorantreiben (oder vielleicht wird ein Haskell-Performance-Experte wie Dons mit einer Lösung auftauchen), ich habe noch nicht einmal den Kern dieses Generators angeschaut, aber im Allgemeinen die Art, Haskell-Code so schnell zu machen C "ist" schreibe es in C und benutze das FFI. "
Wenige Referenzen:
Unten ist Evangelisation, die die allgemeine Folklore repräsentiert. Also nimm es mit einem Körnchen Salz.
Sie können keine stabile C-ähnliche Leistung über verschiedene Mikrobenmarks von weniger ausgereiften als prähistorischen Sprachen wie C, Fortran, Ada und C ++ erhalten. Selbst Java ist noch nicht ganz da. Manchmal bekommen Sie, aber manchmal Compiler schlägt fehl, und GHC versagt ziemlich oft.
Aber Microbenchmarks sagen dir nicht alles.
Das Problem besteht darin, dass es für große Projekte finanziell nicht machbar ist, überall fein abgestimmten Low-Level-C-Code zu bekommen. Also haben C-Programme schlechte Algorithmen, schlechte Architektur, keine Engpässe auf der unteren Ebene und Pläne, irgendwann alles neu zu schreiben. In C ist es leicht, Low-Level-Code zu tunen, aber schmerzhaft schwer, große architektonische Änderungen vorzunehmen. In Haskell ist es umgekehrt, also sollte das Schreiben in einer Mischung aus Haskell und C Ihnen das Beste aus beiden Welten geben.
Tags und Links haskell ode differential-equations