Wann erfolgt die automatische Memoisierung in GHC Haskell?

106

Ich kann nicht herausfinden, warum m1 anscheinend gespeichert ist, während m2 nicht im Folgenden enthalten ist:

m1      = ((filter odd [1..]) !!)

m2 n    = ((filter odd [1..]) !! n)

m1 10000000 benötigt beim ersten Anruf etwa 1,5 Sekunden und bei nachfolgenden Anrufen einen Bruchteil davon (vermutlich wird die Liste zwischengespeichert), während m2 10000000 immer die gleiche Zeit benötigt (Neuerstellung der Liste bei jedem Anruf). Irgendeine Idee, was los ist? Gibt es Faustregeln, ob und wann GHC eine Funktion auswendig lernt? Vielen Dank.

haskell ghc memoization Jordanien
quelle

Antworten:

112

GHC speichert keine Funktionen.

Es berechnet jedoch einen bestimmten Ausdruck im Code höchstens einmal pro Mal, wenn sein umgebender Lambda-Ausdruck eingegeben wird, oder höchstens einmal, wenn er sich auf der obersten Ebene befindet. Das Bestimmen, wo sich die Lambda-Ausdrücke befinden, kann etwas schwierig sein, wenn Sie syntaktischen Zucker wie in Ihrem Beispiel verwenden. Konvertieren Sie diese also in eine äquivalente desugarierte Syntax:

m1' = (!!) (filter odd [1..])              -- NB: See below!
m2' = \n -> (!!) (filter odd [1..]) n

(Hinweis: Der Haskell 98-Bericht beschreibt tatsächlich einen linken Bedienerabschnitt (a %)als äquivalent zu \b -> (%) a b, aber GHC empfiehlt ihn (%) a. Diese sind technisch unterschiedlich, da sie durch unterschieden werden können seq. Ich glaube, ich habe möglicherweise ein GHC Trac-Ticket dazu eingereicht.)

In Anbetracht dieser, können Sie diese in sehen m1', der Ausdruck filter odd [1..]ist nicht in jedem Lambda-Ausdruck enthalten ist , so wird es nur einmal pro Durchlauf des Programms berechnet werden, während in m2', filter odd [1..]wird jedes Mal , wenn der Lambda-Ausdruck berechnet werden eingegeben wird , das heißt, bei jedem Anruf von m2'. Das erklärt den Unterschied im Timing, den Sie sehen.

Tatsächlich teilen einige Versionen von GHC mit bestimmten Optimierungsoptionen mehr Werte als in der obigen Beschreibung angegeben. Dies kann in einigen Situationen problematisch sein. Betrachten Sie zum Beispiel die Funktion

f = \x -> let y = [1..30000000] in foldl' (+) 0 (y ++ [x])

GHC stellt möglicherweise fest, dass ydies nicht von xder Funktion abhängt, und schreibt sie neu in

f = let y = [1..30000000] in \x -> foldl' (+) 0 (y ++ [x])

In diesem Fall ist die neue Version viel weniger effizient, da sie etwa 1 GB aus dem Speicher lesen muss, in dem sie ygespeichert ist, während die ursprüngliche Version auf konstantem Speicherplatz ausgeführt wird und in den Cache des Prozessors passt. Unter GHC 6.12.1 ist die Funktion fbeim Kompilieren ohne Optimierungen fast doppelt so schnell wie beim Kompilieren -O2.

Reid Barton
quelle
1
Die Kosten für die Auswertung (ungerade [1 ..] filtern) sind ohnehin nahe Null - es handelt sich schließlich um eine verzögerte Liste, sodass die tatsächlichen Kosten in der Anwendung (x !! 10000000) liegen, wenn die Liste tatsächlich ausgewertet wird. Außerdem scheinen sowohl m1 als auch m2 nur einmal mit -O2 und -O1 (auf meinem ghc 6.12.3) mindestens innerhalb des folgenden Tests bewertet zu werden: (test = m1 10000000 seqm1 10000000). Es gibt jedoch einen Unterschied, wenn kein Optimierungsflag angegeben ist. Und beide Varianten Ihres "f" haben übrigens unabhängig von der Optimierung eine maximale Residenz von 5356 Bytes (mit weniger Gesamtzuordnung, wenn -O2 verwendet wird).
Ed'ka
1
@ Ed'ka: Probieren Sie dieses Testprogramm mit der obigen Definition von f: main = interact $ unlines . (show . map f . read) . lines; kompilieren mit oder ohne -O2; dann echo 1 | ./main. Wenn Sie einen Test wie schreiben main = print (f 5), ykann bei der Verwendung Müll gesammelt werden, und es gibt keinen Unterschied zwischen den beiden fs.
Reid Barton
ähm, das sollte map (show . f . read)natürlich sein. Und jetzt, da ich GHC 6.12.3 heruntergeladen habe, sehe ich die gleichen Ergebnisse wie in GHC 6.12.1. Und ja, Sie haben Recht mit dem Original m1und m2: Versionen von GHC, die diese Art des Hebens mit aktivierten Optimierungen durchführen, werden sich m2in verwandeln m1.
Reid Barton
Ja, jetzt sehe ich den Unterschied (-O2 ist definitiv langsamer). Vielen Dank für dieses Beispiel!
Ed'ka
29

m1 wird nur einmal berechnet, da es sich um eine konstante Antragsform handelt, während m2 keine CAF ist, und wird daher für jede Bewertung berechnet.

Weitere Informationen finden Sie im GHC-Wiki zu CAFs: http://www.haskell.org/haskellwiki/Constant_applicative_form

sclv
quelle
1
Die Erklärung „m1 wird nur einmal berechnet, weil es sich um eine konstante Antragsform handelt“ ist für mich nicht sinnvoll. Da vermutlich sowohl m1 als auch m2 Variablen der obersten Ebene sind, denke ich, dass diese Funktionen nur einmal berechnet werden, unabhängig davon, ob es sich um CAFs handelt oder nicht. Der Unterschied besteht darin, ob die Liste [1 ..]während der Ausführung eines Programms nur einmal oder einmal pro Anwendung der Funktion berechnet wird, aber hängt sie mit CAF zusammen?
Tsuyoshi Ito
1
Auf der verlinkten Seite: "Ein CAF ... kann entweder zu einem Diagramm kompiliert werden, das von allen Verwendungszwecken gemeinsam genutzt wird, oder zu einem gemeinsam genutzten Code, der sich bei der ersten Auswertung mit einem Diagramm überschreibt." Da m1es sich um eine CAF handelt, gilt die zweite und wird filter odd [1..](nicht nur [1..]!) Nur einmal berechnet. GHC könnte auch feststellen, dass m2auf filter odd [1..]denselben Thunk verwiesen wird, und einen Link zu demselben Thunk setzen, der in verwendet wird. Dies m1wäre jedoch eine schlechte Idee: In einigen Situationen kann dies zu großen Speicherlecks führen.
Alexey Romanov
@ Alexander: Danke für die Korrektur über [1..]und filter odd [1..]. Im Übrigen bin ich immer noch nicht überzeugt. Wenn ich mich nicht irre, ist CAF nur relevant, wenn wir argumentieren wollen, dass ein Compiler das In durch ein globales Thunk ersetzen könnte (das sogar das gleiche Thunk sein kann wie das in ). Aber in der Situation des Fragestellers hat, hat der Compiler nicht tun „Optimierung“ , und ich kann nicht seine Bedeutung für die Frage sehen. filter odd [1..]m2m1
Tsuyoshi Ito
2
Es ist wichtig , dass sie es ersetzen kann in m1 , und es tut.
Alexey Romanov
13

Es gibt einen entscheidenden Unterschied zwischen den beiden Formen: Die Monomorphismusbeschränkung gilt für m1, aber nicht für m2, da m2 explizit Argumente angegeben hat. Der Typ von m2 ist also allgemein, aber der von m1 ist spezifisch. Die ihnen zugewiesenen Typen sind:

m1 :: Int -> Integer
m2 :: (Integral a) => Int -> a

Die meisten Haskell-Compiler und -Interpreter (alle, die ich tatsächlich kenne) merken sich keine polymorphen Strukturen, daher wird die interne Liste von m2 jedes Mal neu erstellt, wenn sie aufgerufen wird, wohingegen m1 nicht.

Mokus
quelle
1
Das Spielen mit diesen in GHCi scheint auch von der Let-Floating-Transformation abhängig zu sein (einer der Optimierungsdurchläufe von GHC, der in GHCi nicht verwendet wird). Und natürlich kann der Optimierer beim Kompilieren dieser einfachen Funktionen dafür sorgen, dass sie sich trotzdem identisch verhalten (gemäß einigen Kriterientests, die ich ohnehin ausgeführt habe, mit den Funktionen in einem separaten Modul und gekennzeichnet mit NOINLINE-Pragmas). Vermutlich liegt das daran, dass die Listenerstellung und -indizierung sowieso zu einer super engen Schleife verschmolzen wird.
Mokus
1

Ich bin mir nicht sicher, weil ich selbst für Haskell noch ziemlich neu bin, aber es scheint, dass die zweite Funktion parametrisiert ist und die erste nicht. Die Art der Funktion ist, dass ihr Ergebnis vom Eingabewert abhängt und insbesondere im Funktionsparadigma NUR von der Eingabe abhängt. Offensichtliche Implikation ist, dass eine Funktion ohne Parameter immer den gleichen Wert zurückgibt, egal was passiert.

Anscheinend gibt es im GHC-Compiler einen Optimierungsmechanismus, der diese Tatsache ausnutzt, um den Wert einer solchen Funktion nur einmal für die gesamte Programmlaufzeit zu berechnen. Es tut es zwar träge, aber es tut es trotzdem. Ich habe es selbst bemerkt, als ich die folgende Funktion geschrieben habe:

primes = filter isPrime [2..]
    where isPrime n = null [factor | factor <- [2..n-1], factor `divides` n]
        where f `divides` n = (n `mod` f) == 0

Dann, um es zu testen, gab ich GHCI ein und schrieb : primes !! 1000. Es dauerte ein paar Sekunden, aber schließlich bekam ich die Antwort : 7927. Dann rief ich an primes !! 1001und bekam sofort die Antwort. In ähnlicher Weise erhielt ich sofort das Ergebnis für take 1000 primes, da Haskell die gesamte Liste mit tausend Elementen berechnen musste, um zuvor das 1001. Element zurückzugeben.

Wenn Sie also Ihre Funktion so schreiben können, dass sie keine Parameter akzeptiert, möchten Sie sie wahrscheinlich. ;)

Sventimir
quelle