Von welchen Optimierungen kann erwartet werden, dass GHC zuverlässig funktioniert?

183

GHC hat viele Optimierungen, die es durchführen kann, aber ich weiß nicht, was sie alle sind, wie wahrscheinlich und unter welchen Umständen sie durchgeführt werden sollen.

Meine Frage ist: Welche Transformationen kann ich erwarten, dass sie jedes Mal oder fast jedes Mal angewendet werden? Wenn ich mir einen Code ansehe, der häufig ausgeführt (ausgewertet) wird, und mein erster Gedanke lautet "hmm, vielleicht sollte ich das optimieren". In diesem Fall sollte mein zweiter Gedanke lauten: "Denken Sie nicht einmal darüber nach." GHC hat das "?

Ich las die Zeitung Stream Fusion: Von Listen über Streams bis hin zu gar nichts , und die Technik, mit der die Listenverarbeitung in eine andere Form umgeschrieben wurde, die die normalen Optimierungen von GHC dann zuverlässig in einfache Schleifen umwandeln würden, war für mich neu. Wie kann ich feststellen, wann meine eigenen Programme für diese Art der Optimierung in Frage kommen?

Das GHC-Handbuch enthält einige Informationen , die jedoch nur einen Teil zur Beantwortung der Frage beitragen.

EDIT: Ich beginne ein Kopfgeld. Was ich möchte, ist eine Liste von Transformationen auf niedrigerer Ebene wie Lambda / Let / Case-Floating, Spezialisierung auf Typ- / Konstruktor- / Funktionsargumente, Strenge-Analyse und Unboxing, Worker / Wrapper und alles andere, was GHC ausgelassen hat zusammen mit Erklärungen und Beispielen für Eingabe- und Ausgabecode sowie idealerweise Darstellungen von Situationen, in denen der Gesamteffekt mehr als die Summe seiner Teile ist. Und im Idealfall wird erwähnt, wann Transformationen nicht möglich sindgeschehen. Ich erwarte keine neuartigen Erklärungen für jede Transformation, ein paar Sätze und einzeilige Inline-Codebeispiele könnten ausreichen (oder ein Link, wenn es sich nicht um zwanzig Seiten wissenschaftlicher Arbeit handelt), solange das Gesamtbild stimmt klar am Ende davon. Ich möchte in der Lage sein, einen Code zu betrachten und eine gute Vermutung darüber anzustellen, ob er zu einer engen Schleife kompiliert wird oder warum nicht oder was ich ändern müsste, um ihn zu erstellen. (Ich interessiere mich hier nicht so sehr für die großen Optimierungs-Frameworks wie Stream Fusion (ich habe gerade einen Artikel darüber gelesen); mehr für die Art von Wissen, über das Leute, die diese Frameworks schreiben, verfügen.)

optimization haskell ghc glaebhoerl
quelle

Dies ist eine sehr würdige Frage. Eine würdige Antwort zu schreiben ist ... schwierig.

MathematicalOrchid

Ein wirklich guter Ausgangspunkt ist dieser: aosabook.org/en/ghc.html

Gabriel Gonzalez

Wenn in jeder Sprache Ihr erster Gedanke "Vielleicht sollte ich das optimieren" lautet, sollte Ihr zweiter Gedanke "Ich werde es zuerst profilieren" sein.

John L

Obwohl die Art von Wissen, nach der Sie suchen, hilfreich ist und dies immer noch eine gute Frage ist, denke ich, dass Sie wirklich besser bedient werden, wenn Sie versuchen, so wenig wie möglich zu optimieren. Schreiben Sie, was Sie meinen, und nur dann , wenn sich herausstellt , dass Sie brauchen , um dann darüber nachdenken , macht der Code weniger einfach aus Gründen der Performance. Anstatt Code zu betrachten und zu denken, "das wird häufig ausgeführt, vielleicht sollte ich es optimieren", sollte man nur denken, wenn man beobachtet, dass Code zu langsam läuft, "ich sollte herausfinden, was häufig ausgeführt wird, und das optimieren". .

Ben

Ich habe völlig damit gerechnet, dass dieser Teil die Ermahnungen zum "Profilieren" hervorrufen würde! :). Aber ich denke, die andere Seite der Medaille ist, wenn ich sie profiliere und sie langsam ist, kann ich sie vielleicht umschreiben oder einfach in eine Form optimieren, die immer noch auf hohem Niveau ist, aber GHC kann sie besser optimieren, anstatt sie selbst von Hand zu optimieren? Was die gleiche Art von Wissen erfordert. Und wenn ich dieses Wissen überhaupt gehabt hätte, hätte ich mir einen Bearbeitungsprofilzyklus ersparen können.

Glaebhoerl

Antworten:

110

Diese GHC Trac-Seite erklärt auch die Pässe ziemlich gut. Diese Seite erklärt die Reihenfolge der Optimierung, ist jedoch wie der Großteil des Trac-Wikis veraltet.

Für Einzelheiten ist es wahrscheinlich am besten, sich anzusehen, wie ein bestimmtes Programm kompiliert wird. Der beste Weg, um zu sehen, welche Optimierungen durchgeführt werden, besteht darin, das Programm mithilfe des -vFlags ausführlich zu kompilieren . Am Beispiel des ersten Stücks Haskell, das ich auf meinem Computer finden konnte:

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

Wenn *** Simplifier:wir vom ersten bis zum letzten Blick auf alle Optimierungsphasen schauen, sehen wir ziemlich viel.

Zunächst läuft der Simplifier zwischen fast allen Phasen. Dies erleichtert das Schreiben vieler Durchgänge erheblich. Wenn Sie beispielsweise viele Optimierungen implementieren, erstellen sie einfach Umschreiberegeln, um die Änderungen zu verbreiten, anstatt sie manuell ausführen zu müssen. Der Vereinfacher umfasst eine Reihe einfacher Optimierungen, einschließlich Inlining und Fusion. Die Hauptbeschränkung, die ich kenne, ist, dass GHC sich weigert, rekursive Funktionen zu integrieren, und dass die Dinge korrekt benannt werden müssen, damit die Fusion funktioniert.

Als nächstes sehen wir eine vollständige Liste aller durchgeführten Optimierungen:

Spezialisieren

Die Grundidee der Spezialisierung besteht darin, Polymorphismus und Überladung zu beseitigen, indem Orte identifiziert werden, an denen die Funktion aufgerufen wird, und Versionen der Funktion erstellt werden, die nicht polymorph sind - sie sind spezifisch für die Typen, mit denen sie aufgerufen werden. Sie können den Compiler auch anweisen, dies mit dem zu tunSPECIALISE Pragma . Nehmen Sie als Beispiel eine Fakultätsfunktion:
```
fac :: (Num a, Eq a) => a -> a
fac 0 = 1
fac n = n * fac (n - 1)
```
Da der Compiler keine Eigenschaften der zu verwendenden Multiplikation kennt, kann er diese überhaupt nicht optimieren. Wenn es jedoch sieht, dass es auf einem verwendet wirdInt , kann es jetzt eine neue Version erstellen, die sich nur im Typ unterscheidet:
```
fac_Int :: Int -> Int
fac_Int 0 = 1
fac_Int n = n * fac_Int (n - 1)
```
Als nächstes können die unten genannten Regeln ausgelöst werden, und Sie erhalten am Ende etwas, das an Unboxed arbeitet Int s arbeitet, was viel schneller als das Original ist. Eine andere Möglichkeit, die Spezialisierung zu betrachten, ist die teilweise Anwendung auf Typklassenwörterbücher und Typvariablen.

Die Quelle hier enthält eine Menge Notizen.
Schweben Sie raus

EDIT: Ich habe das anscheinend schon einmal falsch verstanden. Meine Erklärung hat sich komplett geändert.

Die Grundidee dabei ist, Berechnungen, die nicht wiederholt werden sollen, aus Funktionen zu verschieben. Angenommen, wir hatten Folgendes:
```
\x -> let y = expensive in x+y
```
Im obigen Lambda wird jedes Mal, wenn die Funktion aufgerufen wird, neu yberechnet. Eine bessere Funktion, die das Herausschwimmen erzeugt, ist
```
let y = expensive in \x -> x+y
```
Um den Prozess zu erleichtern, können andere Transformationen angewendet werden. Zum Beispiel passiert dies:
```
 \x -> x + f 2
 \x -> x + let f_2 = f 2 in f_2
 \x -> let f_2 = f 2 in x + f_2
 let f_2 = f 2 in \x -> x + f_2
```
Wiederum wird eine wiederholte Berechnung gespeichert.

Die Quelle ist in diesem Fall sehr gut lesbar.

Im Moment sind Bindungen zwischen zwei benachbarten Lambdas nicht schwebend. Dies ist beispielsweise nicht der Fall:
```
\x y -> let t = x+x in ...
```
gehe zu
```
 \x -> let t = x+x in \y -> ...
```
Nach innen schweben

Zitieren des Quellcodes,

Der Hauptzweck von floatInwardsbesteht darin, in Zweige eines Falls zu schweben, damit wir keine Dinge zuordnen, sie auf dem Stapel speichern und dann feststellen, dass sie in dem ausgewählten Zweig nicht benötigt werden.

Nehmen wir als Beispiel an, wir hätten diesen Ausdruck:
```
let x = big in
    case v of
        True -> x + 1
        False -> 0
```
Wenn dies vausgewertet wird, haben wir Falsedurch Zuweisung x, was vermutlich ein großer Nachteil ist, Zeit und Raum verschwendet. Das Schweben nach innen behebt dies und erzeugt Folgendes:
```
case v of
    True -> let x = big in x + 1
    False -> let x = big in 0
```
, die anschließend durch den Vereinfacher mit ersetzt wird
```
case v of
    True -> big + 1
    False -> 0
```
Obwohl dieses Papier andere Themen abdeckt, gibt es eine ziemlich klare Einführung. Beachten Sie, dass das Ein- und Ausschwimmen trotz ihrer Namen aus zwei Gründen nicht in eine Endlosschleife gerät:
1. Float in Floats lässt caseAnweisungen ein, während Float Out Funktionen behandelt.
2. Es gibt eine feste Reihenfolge der Durchgänge, daher sollten sie sich nicht unendlich abwechseln.

Bedarfsanalyse

Eine Nachfrageanalyse oder Strenge-Analyse ist weniger eine Transformation als vielmehr, wie der Name schon sagt, ein Informationserfassungspass. Der Compiler findet Funktionen, die ihre Argumente (oder zumindest einige von ihnen) immer auswerten, und übergibt diese Argumente mithilfe von Call-by-Value anstelle von Call-by-Need. Da Sie den Overheads von Thunks ausweichen können, ist dies oft viel schneller. Viele Leistungsprobleme in Haskell entstehen entweder dadurch, dass dieser Durchgang fehlschlägt oder der Code einfach nicht streng genug ist. Ein einfaches Beispiel ist der Unterschied zwischen der Verwendung von foldr,foldl undfoldl'Um eine Liste von Ganzzahlen zusammenzufassen: Die erste verursacht einen Stapelüberlauf, die zweite einen Heap-Überlauf und die letzte läuft aufgrund der Strenge einwandfrei. Dies ist wahrscheinlich die am einfachsten zu verstehende und am besten dokumentierte. Ich glaube, dass Polymorphismus und CPS-Code dies oft zunichte machen.
Worker Wrapper bindet

Die Grundidee der Worker / Wrapper-Transformation besteht darin, eine enge Schleife für eine einfache Struktur zu erstellen und diese an den Enden zu und von dieser Struktur zu konvertieren. Nehmen Sie zum Beispiel diese Funktion, die die Fakultät einer Zahl berechnet.
```
factorial :: Int -> Int
factorial 0 = 1
factorial n = n * factorial (n - 1)
```
Mit der Definition von Intin GHC haben wir
```
factorial :: Int -> Int
factorial (I# 0#) = I# 1#
factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
    I# down# -> down#)
```
Beachten Sie, wie der Code in I#s abgedeckt ist ? Wir können sie folgendermaßen entfernen:
```
factorial :: Int -> Int
factorial (I# n#) = I# (factorial# n#)

factorial# :: Int# -> Int#
factorial# 0# = 1#
factorial# n# = n# *# factorial# (n# -# 1#)
```
Obwohl dieses spezielle Beispiel auch von SpecConstr hätte erstellt werden können, ist die Worker / Wrapper-Transformation in Bezug auf die möglichen Funktionen sehr allgemein.
Gemeinsamer Unterausdruck

Dies ist eine weitere wirklich einfache Optimierung, die sehr effektiv ist, wie die Strenge-Analyse. Die Grundidee ist, dass wenn Sie zwei Ausdrücke haben, die gleich sind, sie den gleichen Wert haben. Wenn es sich beispielsweise fibum einen Fibonacci-Zahlenrechner handelt, wird CSE transformiert
```
fib x + fib x
```
in
```
let fib_x = fib x in fib_x + fib_x
```
das halbiert die Berechnung. Leider kann dies gelegentlich anderen Optimierungen im Wege stehen. Ein weiteres Problem besteht darin, dass sich die beiden Ausdrücke an derselben Stelle befinden müssen und dass sie syntaktisch identisch und nicht wertmäßig identisch sein müssen. Zum Beispiel wird CSE im folgenden Code nicht ohne ein paar Inlining ausgelöst:
```
x = (1 + (2 + 3)) + ((1 + 2) + 3)
y = f x
z = g (f x) y
```
Wenn Sie jedoch über llvm kompilieren, erhalten Sie möglicherweise einen Teil davon kombiniert, da die globale Wertnummerierung erfolgreich ist.
Fall befreien

Dies scheint eine schrecklich dokumentierte Transformation zu sein, abgesehen von der Tatsache, dass sie eine Codeexplosion verursachen kann. Hier ist eine neu formatierte (und leicht umgeschriebene) Version der kleinen Dokumentation, die ich gefunden habe:

Dieses Modul geht hinüber Coreund sucht nach casefreien Variablen. Das Kriterium lautet: Wenn caseauf der Route zum rekursiven Aufruf eine freie Variable vorhanden ist , wird der rekursive Aufruf durch eine Entfaltung ersetzt. Zum Beispiel in
```
f = \ t -> case v of V a b -> a : f t
```
das Innere fwird ersetzt. zu machen
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t
```
Beachten Sie die Notwendigkeit der Abschattung. Vereinfachend bekommen wir
```
f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)
```
Dies ist ein besserer Code, da er aim Inneren frei letrecist und keine Projektion von benötigt v. Beachten Sie, dass dies im Gegensatz zu SpecConstr, bei dem Argumente bekannter Form vorliegen, freie Variablen betrifft .

Weitere Informationen zu SpecConstr finden Sie weiter unten.
SpecConstr - dies transformiert Programme wie
```
f (Left x) y = somthingComplicated1
f (Right x) y = somethingComplicated2
```
in
```
f_Left x y = somethingComplicated1
f_Right x y = somethingComplicated2

{-# INLINE f #-}
f (Left x) = f_Left x
f (Right x) = f_Right x
```
Nehmen Sie als erweitertes Beispiel diese Definition von last:
```
last [] = error "last: empty list"
last (x:[]) = x
last (x:x2:xs) = last (x2:xs)
```
Wir transformieren es zuerst zu
```
last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last (x2:xs)

{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
Als nächstes läuft der Vereinfacher, und wir haben
```
last_nil = error "last: empty list"
last_cons x [] = x
last_cons x (x2:xs) = last_cons x2 xs

{-# INLINE last #-}
last [] = last_nil
last (x : xs) = last_cons x xs
```
Beachten Sie, dass das Programm jetzt schneller ist, da wir die Vorderseite der Liste nicht wiederholt ein- und auspacken. Beachten Sie auch, dass das Inlining von entscheidender Bedeutung ist, da es die tatsächliche Verwendung der neuen, effizienteren Definitionen ermöglicht und die rekursiven Definitionen verbessert.

SpecConstr wird durch eine Reihe von Heuristiken gesteuert. Die in der Zeitung erwähnten sind als solche:
1. Die Lambdas sind explizit und die Arität ist a.
2. Die rechte Seite ist "ausreichend klein", etwas, das von einer Flagge gesteuert wird.
3. Die Funktion ist rekursiv und der spezialisierbare Aufruf wird auf der rechten Seite verwendet.
4. Alle Argumente für die Funktion sind vorhanden.
5. Mindestens eines der Argumente ist eine Konstruktoranwendung.
6. Dieses Argument wird irgendwo in der Funktion fallbezogen analysiert.
Die Heuristiken haben sich jedoch mit ziemlicher Sicherheit geändert. In der Tat erwähnt das Papier eine alternative sechste Heuristik:

Spezialisieren Sie sich xnur dann auf ein Argument , wenn xes nur von a geprüft caseund nicht an eine normale Funktion übergeben oder als Teil des Ergebnisses zurückgegeben wird.

Dies war eine sehr kleine Datei (12 Zeilen) und hat möglicherweise nicht so viele Optimierungen ausgelöst (obwohl ich denke, dass sie alle durchgeführt wurden). Dies sagt Ihnen auch nicht, warum diese Pässe ausgewählt wurden und warum sie in diese Reihenfolge gebracht wurden.

gereeter
quelle

Jetzt kommen wir irgendwohin! Kommentare: In dem Teil über Spezialisieren scheint der Satz abgeschnitten zu sein. Ich sehe keinen Grund zum Float-Out: Wofür ist es? Wie entscheidet es, ob es rein oder raus schwebt (warum gerät es nicht in eine Schleife)? Ich hatte den Eindruck von irgendwo , dass GHC hat CSE nicht überhaupt , aber anscheinend das war falsch. Ich habe das Gefühl, dass ich mich in Details verliere, anstatt ein großes Bild zu sehen ... das Thema ist noch komplizierter als ich dachte. Vielleicht ist meine Frage unmöglich und es gibt keine Möglichkeit, diese Intuition zu erlangen, außer eine Menge Erfahrung oder selbst an GHC zu arbeiten?

Glaebhoerl

Nun, ich weiß es nicht, aber ich habe noch nie an GHC gearbeitet, also müssen Sie in der Lage sein, etwas Intuition zu bekommen .

gereeter

Ich habe die von Ihnen erwähnten Probleme behoben.

gereeter

Auch im Großen und Ganzen bin ich der Meinung, dass es wirklich keine gibt. Wenn ich erraten möchte, welche Optimierungen durchgeführt werden, gehe ich eine Checkliste durch. Dann mache ich es noch einmal, um zu sehen, wie jeder Durchgang die Dinge verändert. Und wieder. Im Wesentlichen spiele ich den Compiler. Das einzige mir bekannte Optimierungsschema, das wirklich ein "großes Bild" hat, ist die Superkompilierung.

gereeter

Was meinst du mit "Dinge müssen richtig benannt werden, damit die Fusion funktioniert" genau?

Vincent Beffara

Faulheit

Es ist keine "Compiler-Optimierung", aber es wird durch die Sprachspezifikation garantiert, sodass Sie immer darauf zählen können, dass dies geschieht. Im Wesentlichen bedeutet dies, dass die Arbeit erst ausgeführt wird, wenn Sie mit dem Ergebnis "etwas tun". (Es sei denn, Sie tun eines von mehreren Dingen, um Faulheit absichtlich auszuschalten.)

Dies ist offensichtlich ein ganzes Thema für sich, und SO hat bereits viele Fragen und Antworten dazu.

Nach meiner begrenzten Erfahrung hat es zu weitaus größeren Leistungseinbußen (in Bezug auf Zeit und Raum), wenn Sie Ihren Code zu faul oder zu streng machen, als bei allen anderen Dingen, über die ich gleich sprechen werde ...

Strenge Analyse

Bei Faulheit geht es darum, Arbeit zu vermeiden, es sei denn, dies ist notwendig. Wenn der Compiler feststellen kann, dass ein bestimmtes Ergebnis "immer" benötigt wird, muss er die Berechnung nicht speichern und später ausführen. es wird es nur direkt ausführen, weil das effizienter ist. Dies ist eine sogenannte "Strenge-Analyse".

Das Problem ist natürlich, dass der Compiler nicht immer erkennen kann , wann etwas streng gemacht werden könnte. Manchmal müssen Sie dem Compiler kleine Hinweise geben. (Mir ist kein einfacher Weg bekannt, um festzustellen, ob die Strenge-Analyse das getan hat, was Sie denken, außer durch die Core-Ausgabe zu waten.)

Inlining

Wenn Sie eine Funktion aufrufen und der Compiler erkennen kann, welche Funktion Sie aufrufen, versucht er möglicherweise, diese Funktion zu "inline", dh den Funktionsaufruf durch eine Kopie der Funktion selbst zu ersetzen. Der Aufwand für einen Funktionsaufruf ist normalerweise recht gering, aber durch Inlining können häufig andere Optimierungen vorgenommen werden, die sonst nicht möglich gewesen wären, sodass Inlining ein großer Gewinn sein kann.

Funktionen werden nur inline gesetzt, wenn sie "klein genug" sind (oder wenn Sie ein Pragma hinzufügen, das speziell nach Inlining fragt). Außerdem können Funktionen nur eingebunden werden, wenn der Compiler erkennen kann, welche Funktion Sie aufrufen. Es gibt zwei Möglichkeiten, die der Compiler möglicherweise nicht erkennen kann:

Wenn die von Ihnen aufgerufene Funktion von einem anderen Ort übergeben wird. Wenn die filterFunktion kompiliert wird, können Sie das Filterprädikat beispielsweise nicht inline setzen, da es sich um ein vom Benutzer angegebenes Argument handelt.
Wenn die aufgerufene Funktion eine Klassenmethode ist und der Compiler nicht weiß, um welchen Typ es sich handelt. Wenn die sumFunktion kompiliert wird, kann der Compiler die +Funktion beispielsweise nicht einbinden , da er summit mehreren verschiedenen Nummerntypen arbeitet, von denen jeder eine andere +Funktion hat.

Im letzteren Fall können Sie das {-# SPECIALIZE #-}Pragma verwenden, um Versionen einer Funktion zu generieren, die für einen bestimmten Typ fest codiert sind. ZB {-# SPECIALIZE sum :: [Int] -> Int #-}würde eine Version von sumfest codiert für den IntTyp kompilieren , was bedeutet, dass +in dieser Version eingefügt werden kann.

Beachten Sie jedoch, dass unsere neue Spezialfunktion sumnur aufgerufen wird, wenn der Compiler erkennen kann, dass wir arbeiten Int. Andernfalls wird das ursprüngliche polymorphe sumaufgerufen. Auch hier ist der tatsächliche Funktionsaufrufaufwand ziemlich gering. Es sind die zusätzlichen Optimierungen, die Inlining ermöglichen kann, die von Vorteil sind.

Häufige Eliminierung von Subexpressionen

Wenn ein bestimmter Codeblock denselben Wert zweimal berechnet, kann der Compiler diesen durch eine einzelne Instanz derselben Berechnung ersetzen. Zum Beispiel, wenn Sie dies tun

(sum xs + 1) / (sum xs + 2)

dann könnte der Compiler dies optimieren

let s = sum xs in (s+1)/(s+2)

Sie können erwarten, dass der Compiler dies immer tut. In einigen Situationen kann dies jedoch zu einer schlechteren und nicht zu einer besseren Leistung führen, sodass GHC dies nicht immer tut. Ehrlich gesagt verstehe ich die Details dahinter nicht wirklich. Aber unter dem Strich ist es nicht schwer, diese Transformation manuell durchzuführen, wenn sie für Sie wichtig ist. (Und wenn es nicht wichtig ist, warum machst du dir dann Sorgen?)

Fallausdrücke

Folgendes berücksichtigen:

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

Die ersten drei Gleichungen prüfen alle, ob die Liste (unter anderem) nicht leer ist. Aber das Gleiche dreimal zu überprüfen, ist verschwenderisch. Glücklicherweise ist es für den Compiler sehr einfach, dies in mehrere verschachtelte Fallausdrücke zu optimieren. In diesem Fall so etwas wie

foo xs =
  case xs of
    y:ys ->
      case y of
        0 -> "zero"
        1 -> "one"
        _ -> foo ys
    []   -> "end"

Dies ist weniger intuitiv, aber effizienter. Da der Compiler diese Umwandlung problemlos durchführen kann, müssen Sie sich darüber keine Sorgen machen. Schreiben Sie einfach Ihren Mustervergleich auf die intuitivste Art und Weise. Der Compiler ist sehr gut darin, dies neu zu ordnen und neu anzuordnen, um es so schnell wie möglich zu machen.

Verschmelzung

Die Standard-Haskell-Sprache für die Listenverarbeitung besteht darin, Funktionen zu verketten, die eine Liste enthalten und eine neue Liste erstellen. Das kanonische Beispiel ist

map g . map f

Während Faulheit garantiert, dass unnötige Arbeit übersprungen wird, sind leider alle Zuweisungen und Freigaben für die Zwischenlisten-Sap-Leistung. Bei "Fusion" oder "Entwaldung" versucht der Compiler, diese Zwischenschritte zu eliminieren.

Das Problem ist, dass die meisten dieser Funktionen rekursiv sind. Ohne die Rekursion wäre es eine elementare Übung beim Inlining, alle Funktionen in einen großen Codeblock zu zerlegen, den Vereinfacher darüber auszuführen und wirklich optimalen Code ohne Zwischenlisten zu erzeugen. Aber wegen der Rekursion wird das nicht funktionieren.

Sie können {-# RULE #-}Pragmas verwenden, um einige dieser Probleme zu beheben. Beispielsweise,

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

Jedes Mal, wenn GHC eine mapAnwendung sieht map, wird sie in einem einzigen Durchgang über die Liste gequetscht, wodurch die Zwischenliste entfernt wird.

Das Problem ist, dies funktioniert nur für mapgefolgt von map. Es gibt viele andere Möglichkeiten - mapgefolgt von filter, filtergefolgt von mapusw. Anstatt für jede eine Lösung von Hand zu codieren, wurde die sogenannte "Stromfusion" erfunden. Dies ist ein komplizierterer Trick, den ich hier nicht beschreiben werde.

Das lange und kurze daran ist: Dies sind alles spezielle Optimierungstricks, die vom Programmierer geschrieben wurden . GHC selbst weiß nichts über Fusion; Es ist alles in den Listenbibliotheken und anderen Containerbibliotheken. Welche Optimierungen stattfinden, hängt also davon ab, wie Ihre Container-Bibliotheken geschrieben sind (oder realistischer davon, welche Bibliotheken Sie verwenden).

Wenn Sie beispielsweise mit Haskell '98 -Arrays arbeiten, erwarten Sie keinerlei Fusion. Ich verstehe jedoch, dass die vectorBibliothek über umfangreiche Fusionsfunktionen verfügt. Es geht nur um die Bibliotheken; Der Compiler liefert nur das RULESPragma. (Das ist übrigens extrem mächtig. Als Bibliotheksautor können Sie damit Client-Code umschreiben!)

Meta:

Ich stimme den Leuten zu, die sagen "Code zuerst, Profil zweitens, drittens optimieren".
Ich stimme auch den Leuten zu, die sagen: "Es ist nützlich, ein mentales Modell für die Kosten einer bestimmten Designentscheidung zu haben."

Balance in allen Dingen und all dem ...

MathematicalOrchid
quelle

it's something guaranteed by the language specification ... work is not performed until you "do something" with the result.

- nicht genau. Die Sprachspezifikation verspricht eine nicht strenge Semantik ; es verspricht nichts darüber, ob überflüssige Arbeiten ausgeführt werden oder nicht.

Dan Burton

@ DanBurton Sicher. Aber das ist nicht einfach in wenigen Sätzen zu erklären. Da GHC fast die einzige noch vorhandene Haskell-Implementierung ist, ist die Tatsache, dass GHC faul ist, für die meisten Menschen gut genug.

MathematicalOrchid

@MathematicalOrchid: Spekulative Bewertungen sind ein interessantes Gegenbeispiel, obwohl ich zustimmen würde, dass es für Anfänger wahrscheinlich zu viel ist.

Ben Millwood

Über CSE: Mein Eindruck ist, dass dies fast nie gemacht wird, da es zu unerwünschtem Teilen und damit zu Raumspitzen führen kann.

Joachim Breitner

Entschuldigen Sie, dass (a) Sie vorher nicht geantwortet haben und (b) Ihre Antwort nicht akzeptiert haben. Das ist lang und beeindruckend, deckt aber nicht das Gebiet ab, das ich wollte. Was ich möchte, ist eine Liste von Transformationen auf niedrigerer Ebene wie Lambda / Let / Case-Floating, Spezialisierung auf Typ- / Konstruktor- / Funktionsargumente, Strenge-Analyse und Unboxing (die Sie erwähnen), Worker / Wrapper und alles, was GHC sonst noch tut mit Erklärungen und Beispielen für Eingabe- und Ausgabecode sowie idealerweise Beispielen für deren kombinierte Wirkung und solche, bei denen die Transformationen nicht stattfinden . Ich denke, ich sollte ein Kopfgeld machen?

Glaebhoerl

Wenn eine let-Bindung v = rhs nur an einer Stelle verwendet wird, können Sie sich darauf verlassen, dass der Compiler sie einbindet, auch wenn rhs groß ist.

Die Ausnahme (die im Kontext der aktuellen Frage fast keine ist) besteht darin, dass Lambdas das Risiko einer Doppelarbeit eingehen. Erwägen:

let v = rhs
    l = \x-> v + x
in map l [1..100]

Dort wäre das Inlining von v gefährlich, da die eine (syntaktische) Verwendung zu 99 zusätzlichen Auswertungen von rhs führen würde. In diesem Fall ist es jedoch sehr unwahrscheinlich, dass Sie es auch manuell einbinden möchten. Im Wesentlichen können Sie also die Regel verwenden:

Wenn Sie einen Namen einfügen möchten, der nur einmal vorkommt, wird der Compiler dies trotzdem tun.

Als glückliche Folge ist die Verwendung einer Let-Bindung, um eine lange Aussage einfach zu zerlegen (mit der Hoffnung, Klarheit zu gewinnen), im Wesentlichen kostenlos.

Dies kommt von community.haskell.org/~simonmar/papers/inline.pdf, die viel mehr Informationen über Inlining enthält.

Daniel
quelle