Im Folgenden sind drei Versionen von pythagoreischen Triplets mit Brute-Force mit einer zusätzlichen Einschränkung, dass a + b + c = 1000. Alle von ihnen wurden mit GHC 7.0.3 -O3 erfüllt. Beispiellaufzeiten sind unten aufgeführt.
Fragen :
Ich erkenne, dass der Unterschied klein ist, aber die Reihenfolge ist im Durchschnitt konsistent.
%Vor%Lassen Sie uns die drei Programme A , B und C nennen.
Wir beginnen mit dem einfachsten: C hat eine zusätzliche Einschränkung ( b >= a ) relativ zu B . Intuitiv bedeutet dies, dass der Suchbereich, der in C durchlaufen wird, kleiner ist als der von B . Wir können dies rationalisieren, indem wir notieren, dass anstatt über jedes möglicherweise permutierte Paar a, b (von dem wir wissen, dass es 1000^2=1000000 mögliche Paare gibt) nicht alle Fälle berücksichtigt werden, in denen b kleiner als a ist. Vermutlich erzeugt die Überprüfung, ob b >= a ein wenig zusätzlichen Code (den Vergleich) erzeugt, der durch Berechnung, die durch Ausführen des Vergleichs vermieden wird, aufgewogen wird, daher stellen wir eine (leichte) Beschleunigung fest. Fair genug.
Der nächste ist etwas kniffliger: Es scheint, dass A die gleiche Einschränkung wie C hat ( b >= a ), aber anders kodiert (dh hier haben wir es kodiert) wie der Wertebereich b in List Monad erreichen kann). Wir könnten dann denken, dass A schneller ausgeführt werden sollte als B (ähnlich wie C ). Es ist klar, dass unsere Intuition fehlt.
Jetzt, da wir unserer Intuition nicht immer vertrauen können, sollten wir untersuchen, was wirklich in dem generierten GHC-Kern . Läßt den Kern für unsere 3 Programme (ohne Optimierungen) ablegen:
%Vor% Wenn wir B.core und C.core vergleichen, werden wir feststellen, dass beide Dateien ungefähr dieselbe Struktur haben:
Beginnen Sie damit, einige bekannte Funktionen aufzurufen: (System.IO.print ...) , (Data.List.product ...) und (GHC.List.head ...)
Als nächstes definieren wir ein Paar verschachtelter rekursiver Funktionen mit Signatur:
%Vor%Wir nennen jede dieser definierten Funktionen in einer Aufzählung der Form:
%Vor% und führen Sie unsere Logik innerhalb der innersten definierten Funktion aus. Wir können sehen, dass in B.core
entspricht einem naiven Filter aller möglichen Werte, die unserer Bedingung entsprechen, während wir in C.core stattdessen:
entspricht der Addition einer zusätzlichen >= -Restriktion vor unserer Triplet-Einschränkung und durchsucht daher weniger ganze Zahlen für eine kürzere Laufzeit, genau wie es unsere Intuition erwartet.
Beim Vergleich von A.core und B.core sehen wir sofort eine vertraute Struktur (ein geschachteltes Paar von rekursiven Funktionen, die jeweils über eine Enumeration aufgerufen werden) und tatsächlich erscheint die Kernausgabe für A und B sind fast identisch! Der Unterschied scheint in der innersten Aufzählung zu liegen:
Hier sehen wir den Enumerationsbereich von einer gegebenen Induktionsvariablen ds3_dxb bis 1000 , im Gegensatz zu einem statischen Bereich ( [1..1000 ]).
Was gibt dann? Sollte dies nicht darauf hinweisen, dass A schneller ausgeführt werden sollte als B ? (Wir erwarten naiv, dass A ähnlich wie C funktioniert, vorausgesetzt, dass sie dieselben Einschränkungen implementieren). Nun, es stellt sich heraus, dass die verschiedenen Compiler-Optimierungen im Spiel äußerst komplexes Verhalten erzeugen und die verschiedenen Kombinationen oft nicht-intuitive (und ehrlich gesagt bizarre) Ergebnisse liefern, und in diesem Fall haben wir zwei Compiler miteinander spielen: ghc und gcc . Um diese Ergebnisse verstehen zu können, müssen wir uns auf den generierten optimierten Kern verlassen (Letztlich zählt aber der generierte Assembler, aber das werden wir vorerst ignorieren).
Lassen Sie uns den optimierten Kern erzeugen:
%Vor% und vergleichen Sie unser Problemkind ( A ) mit seinen schnelleren Gegenstücken. Vergleichsweise B und C führen beide eine Klasse von Optimierungen durch, die A allein nicht kann: let-floating und Lambda-Heben . Wir können dies erkennen, indem wir feststellen, dass unsere rekursiven Funktionen in B und C einige 40 weniger Codezeilen enthalten, was zu engeren inneren Schleifen führt. Um zu verstehen, warum A nicht von dieser Optimierung profitiert, sollten wir uns den Code anschauen, der nicht veröffentlicht wird:
Das heißt, eine Subtraktion ( minusInteger ) und eine Gleichheit ( eqInteger ) sowie zwei Quadrate ( ^_^ ) werden innerhalb des kritischen Abschnitts unserer Schleife ausgeführt (repräsentiert durch den Körper einer Hilfsfunktion) ), während die gleiche Hilfsfunktion in C.core weniger Berechnungen enthält (und wenn wir weiter ausgraben würden, würden wir sehen, dass GHC nicht feststellen kann, ob es sicher ist, diese Berechnungen im Optimierungspass zu speichern).Dies stimmt mit unserer früheren Analyse überein, da wir sehen können, dass die Einschränkung ( b >= a ) tatsächlich vorhanden ist, im Gegensatz zu C konnten wir die Mehrheit der redundanten Berechnung außerhalb der Schleife.
Um dies zu bestätigen, erhöhen wir die Grenzen der Schleife willkürlich (um es zu demonstrieren), sagen wir zu [1..10000] . Wir sollten erwarten, dass das Laufzeitverhalten von A asymptotisch nahe dem Laufzeitverhalten von C sein sollte, genau wie wir erwarten, dass B im Staub bleibt .
und was weißt du, es ist genau so, wie wir es erwarten! Ihre anfänglichen Grenzen waren einfach zu klein, um irgendwelche interessanten Leistungsmerkmale durchscheinen zu lassen (was auch immer die Theorie Ihnen sagen mag, ständiger Aufwand ist in der Praxis wichtig ). Eine andere Möglichkeit, dieses Ergebnis zu betrachten, ist, dass unsere anfängliche Intuition über A übereinstimmende C Leistung tatsächlich genauer war, als sie zuerst erschien.
Natürlich kann all dies für das vorliegende Codebeispiel zu viel Aufwand sein, aber diese Art der Analyse kann in ressourcenbeschränkten Umgebungen sehr nützlich sein.
Tags und Links haskell performance list-comprehension