Kiedy zapamiętywanie jest automatyczne w GHC Haskell?

106

Nie mogę zrozumieć, dlaczego m1 najwyraźniej jest zapamiętywany, podczas gdy m2 nie znajduje się w następującym:

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

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

m1 10000000 zajmuje około 1,5 sekundy przy pierwszym połączeniu i ułamek tego czasu przy kolejnych (przypuszczalnie buforuje listę), natomiast m2 10000000 zawsze zajmuje tyle samo czasu (odbudowywanie listy przy każdym połączeniu). Masz jakiś pomysł, co się dzieje? Czy są jakieś praktyczne zasady, czy i kiedy GHC zapamięta funkcję? Dzięki.

haskell ghc memoization Jordania
źródło

Odpowiedzi:

112

GHC nie zapamiętuje funkcji.

Jednak wylicza dowolne wyrażenie w kodzie co najwyżej raz na raz, gdy zostało wprowadzone otaczające je wyrażenie lambda, lub co najwyżej raz, jeśli znajduje się na najwyższym poziomie. Ustalenie, gdzie są wyrażenia lambda, może być trochę trudne, gdy używasz cukru składniowego, jak w przykładzie, więc przekonwertujmy je na równoważną składnię pozbawioną cukru:

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

(Uwaga: raport Haskell 98 faktycznie opisuje lewą sekcję operatora, podobną (a %)do \b -> (%) a b, ale GHC usuwa cukier (%) a. Są one technicznie różne, ponieważ można je rozróżnić seq. Myślę, że mogłem przesłać zgłoszenie GHC Trac na ten temat.)

Biorąc to pod uwagę, możesz zobaczyć, że w m1', wyrażenie filter odd [1..]nie jest zawarte w żadnym wyrażeniu lambda, więc zostanie obliczone tylko raz na uruchomienie twojego programu, podczas gdy in m2', filter odd [1..]zostanie obliczone za każdym razem, gdy zostanie wprowadzone wyrażenie lambda, tj. przy każdym wywołaniu m2'. To wyjaśnia różnicę w czasie, który widzisz.

W rzeczywistości niektóre wersje GHC, z pewnymi opcjami optymalizacji, będą miały więcej wspólnych wartości, niż wskazuje powyższy opis. W niektórych sytuacjach może to być problematyczne. Na przykład rozważmy funkcję

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

GHC może zauważyć, że ynie zależy od funkcji xi nie przepisuje jej na

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

W tym przypadku nowa wersja jest znacznie mniej wydajna, ponieważ będzie musiała odczytać około 1 GB z pamięci, w której yjest przechowywana, podczas gdy wersja oryginalna działałaby na stałej przestrzeni i mieściłaby się w pamięci podręcznej procesora. W rzeczywistości w GHC 6.12.1 funkcja fjest prawie dwa razy szybsza, gdy jest kompilowana bez optymalizacji, niż jest kompilowana z -O2.

Reid Barton
źródło
1
Koszt oszacowania (filter odd [1 ..]) wyrażenie i tak jest bliski zeru - w końcu jest to leniwa lista, więc rzeczywisty koszt jest w aplikacji (x !! 10000000), gdy lista jest faktycznie obliczana. Poza tym zarówno m1, jak i m2 wydaje się być oceniane tylko raz z -O2 i -O1 (na moim ghc 6.12.3) przynajmniej w ramach następującego testu: (test = m1 10000000 seqm1 10000000). Istnieje jednak różnica, gdy nie określono flagi optymalizacji. Nawiasem mówiąc, oba warianty twojego "f" mają maksymalną rezystancję 5356 bajtów niezależnie od optymalizacji (z mniejszą całkowitą alokacją, gdy używane jest -O2).
Ed'ka
1
@ Ed'ka: Spróbuj tego programu testowego, z powyższej definicji f: main = interact $ unlines . (show . map f . read) . lines; kompilować z lub bez -O2; wtedy echo 1 | ./main. Jeśli napiszesz test typu main = print (f 5), ymoże być zbierany jako śmieci, ponieważ jest używany i nie ma różnicy między tymi dwoma f.
Reid Barton,
eee, tak powinno być map (show . f . read), oczywiście. A teraz, gdy pobrałem GHC 6.12.3, widzę te same wyniki, co w GHC 6.12.1. I tak, masz rację co do oryginału m1i m2: wersje GHC, które wykonują ten rodzaj podnoszenia z włączonymi optymalizacjami, zmienią się m2w m1.
Reid Barton
Tak, teraz widzę różnicę (-O2 jest zdecydowanie wolniejsze). Dziękuję za ten przykład!
Ed'ka
29

m1 jest obliczane tylko raz, ponieważ jest stałą formą aplikacyjną, podczas gdy m2 nie jest CAF, więc jest obliczane dla każdej oceny.

Zobacz wiki GHC na temat CAF: http://www.haskell.org/haskellwiki/Constant_applicative_form

sclv
źródło
1
Wyjaśnienie „m1 jest obliczane tylko raz, ponieważ jest to stała forma aplikacyjna” nie ma dla mnie sensu. Ponieważ przypuszczalnie zarówno m1, jak i m2 są zmiennymi najwyższego poziomu, myślę, że te funkcje są obliczane tylko raz, bez względu na to, czy są to CAF, czy nie. Różnica polega na tym, czy lista [1 ..]jest obliczana tylko raz podczas wykonywania programu, czy też jest obliczana raz na aplikację funkcji, ale czy jest związana z CAF?
Tsuyoshi Ito
1
Z połączonej strony: „CAF ... można skompilować do wykresu, który będzie współdzielony przez wszystkie zastosowania, lub do jakiegoś wspólnego kodu, który nadpisuje się jakimś wykresem przy pierwszej ocenie”. Ponieważ m1jest to CAF, druga ma zastosowanie i filter odd [1..](nie tylko [1..]!) Jest obliczana tylko raz. GHC może również zauważyć, że m2odnosi filter odd [1..]się do tego samego elementu, w którym jest używany, i umieścić do niego łącze m1, ale byłby to zły pomysł: w niektórych sytuacjach może to prowadzić do dużych wycieków pamięci.
Alexey Romanov
@Alexey: Dziękuję za korektę dotyczącą [1..]i filter odd [1..]. Co do reszty, nadal nie jestem przekonany. Jeśli się nie mylę, CAF ma znaczenie tylko gdy chcemy twierdzić, że kompilator mógłby zastąpić filter odd [1..]w m2przez globalną thunk (którym może być nawet takie same thunk, który wykorzystano w m1). Ale w sytuacji pytającego kompilator nie dokonał tej „optymalizacji” i nie widzę jej związku z pytaniem.
Tsuyoshi Ito
2
Jest to istotne, że może zastąpić go w m1 , i to robi.
Alexey Romanov
13

Istnieje zasadnicza różnica między tymi dwiema postaciami: ograniczenie monomorfizmu dotyczy m1, ale nie m2, ponieważ m2 wyraźnie podał argumenty. Więc typ m2 jest ogólny, ale m1 jest specyficzny. Przypisane im typy to:

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

Większość kompilatorów i interpreterów Haskell (wszystkie, które znam) nie zapamiętuje struktur polimorficznych, więc wewnętrzna lista m2 jest odtwarzana za każdym razem, gdy jest wywoływana, a m1 nie.

mokus
źródło
1
Wydaje się, że gra z nimi w GHCi zależy również od transformacji let-floating (jednego z przebiegów optymalizacji GHC, które nie jest używane w GHCi). I oczywiście, kompilując te proste funkcje, optymalizator i tak jest w stanie sprawić, by zachowywały się identycznie (zgodnie z niektórymi testami kryterialnymi, które zrealizowałem i tak, z funkcjami w osobnym module i oznaczonymi pragmami NOINLINE). Prawdopodobnie dzieje się tak dlatego, że generowanie i indeksowanie listy i tak zostaje połączone w bardzo wąską pętlę.
mokus
1

Nie jestem pewien, ponieważ sam jestem całkiem nowy w Haskellu, ale wydaje się, że to dlatego, że druga funkcja jest sparametryzowana, a pierwsza nie. Charakter funkcji polega na tym, że jej wynik zależy od wartości wejściowej, aw paradygmacie funkcjonalnym, w szczególności TYLKO od wejścia. Oczywistą implikacją jest to, że funkcja bez parametrów zwraca zawsze tę samą wartość, bez względu na wszystko.

Najwyraźniej w kompilatorze GHC istnieje mechanizm optymalizujący, który wykorzystuje ten fakt do obliczenia wartości takiej funkcji tylko raz dla całego czasu wykonywania programu. Z pewnością robi to leniwie, ale mimo to robi to. Sam to zauważyłem, pisząc następującą funkcję:

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

Następnie przetestować go, wszedłem GHCI i napisał: primes !! 1000. Minęło kilka sekund, ale w końcu dostałem odpowiedź: 7927. Potem zadzwoniłem primes !! 1001i natychmiast otrzymałem odpowiedź. Podobnie w jednej chwili otrzymałem wynik dla take 1000 primes, ponieważ Haskell musiał obliczyć całą listę tysięcy elementów, aby wcześniej zwrócić 1001 element.

Tak więc, jeśli możesz napisać swoją funkcję w taki sposób, że nie przyjmuje parametrów, prawdopodobnie tego chcesz. ;)

Sventimir
źródło