Lenistwo
Nie jest to „optymalizacja kompilatora”, ale jest to gwarantowane przez specyfikację języka, więc zawsze możesz na to liczyć. Zasadniczo oznacza to, że praca nie jest wykonywana, dopóki „nie zrobisz czegoś” z wynikiem. (Chyba że zrobisz jedną z kilku rzeczy, aby celowo wyłączyć lenistwo).
To oczywiście cały temat sam w sobie, a SO ma już wiele pytań i odpowiedzi na ten temat.
Z mojego ograniczonego doświadczenia wynika, że uczynienie twojego kodu zbyt leniwym lub zbyt surowym ma znacznie większe kary wydajnościowe (w czasie i przestrzeni) niż jakikolwiek inny materiał, o którym zamierzam mówić ...
Analiza ścisłości
Lenistwo polega na unikaniu pracy, chyba że jest to konieczne. Jeśli kompilator może ustalić, że dany wynik będzie „zawsze” potrzebny, to nie będzie kłopotał się zapisaniem obliczeń i wykonaniem go później; po prostu wykona to bezpośrednio, ponieważ jest to bardziej wydajne. Jest to tak zwana „analiza ścisłości”.
Oczywiście, kompilator polega na tym, że kompilator nie zawsze może wykryć, kiedy coś może zostać zaostrzone. Czasami musisz dać kompilatorowi małe wskazówki. (Nie znam żadnego łatwego sposobu na ustalenie, czy analiza ścisłości zrobiła to, co według ciebie, inne niż przebranie przez rdzeń).
Inlining
Jeśli wywołujesz funkcję, a kompilator może stwierdzić, którą funkcję wywołujesz, może spróbować „wstawić” tę funkcję - to znaczy zastąpić wywołanie funkcji kopią samej funkcji. Narzut wywołania funkcji jest zwykle dość niewielki, ale wstawianie często pozwala na inne optymalizacje, które inaczej by się nie wydarzyły, więc wstawianie może być dużą wygraną.
Funkcje są wstawiane tylko wtedy, gdy są „wystarczająco małe” (lub jeśli dodasz pragmę z prośbą o wstawianie). Funkcje można również wstawiać tylko wtedy, gdy kompilator może powiedzieć, którą funkcję wywołujesz. Istnieją dwa główne sposoby, za pomocą których kompilator może nie być w stanie stwierdzić:
Jeśli wywoływana funkcja jest przekazywana z innego miejsca. Na przykład po filterskompilowaniu funkcji nie można wstawić predykatu filtru, ponieważ jest to argument podany przez użytkownika.
Jeśli wywoływana funkcja jest metodą klasową, a kompilator nie wie, jaki typ jest zaangażowany. Na przykład, gdy sumfunkcja jest kompilowana, kompilator nie może wstawić +funkcji, ponieważ sumdziała z kilkoma różnymi typami liczb, z których każdy ma inną +funkcję.
W tym drugim przypadku możesz użyć {-# SPECIALIZE #-}pragmy do wygenerowania wersji funkcji, które są zakodowane na stałe dla określonego typu. Na przykład {-# SPECIALIZE sum :: [Int] -> Int #-}skompilowałbym wersję na sumstałe dla tego Inttypu, co oznacza, że +można wstawić w tej wersji.
Zauważ jednak, że nasza nowa sumfunkcja specjalna zostanie wywołana tylko wtedy, gdy kompilator będzie w stanie stwierdzić, że pracujemy Int. W przeciwnym razie sumwywoływana jest oryginalna, polimorficzna . Ponownie, faktyczny narzut wywołania funkcji jest dość mały. Korzystne są dodatkowe optymalizacje, które może włączyć wbudowanie.
Wspólna eliminacja podwyrażeń
Jeśli określony blok kodu oblicza dwukrotnie tę samą wartość, kompilator może zastąpić ją jednym wystąpieniem tego samego obliczenia. Na przykład jeśli tak
(sum xs + 1) / (sum xs + 2)
wtedy kompilator może to zoptymalizować
let s = sum xs in (s+1)/(s+2)
Można się spodziewać, że kompilator zawsze to zrobi. Jednak najwyraźniej w niektórych sytuacjach może to skutkować gorszą wydajnością, a nie lepszą, więc GHC nie zawsze to robi. Szczerze mówiąc, tak naprawdę nie rozumiem szczegółów tego. Ale sedno jest takie, że jeśli transformacja jest dla ciebie ważna, nie jest to trudne ręcznie. (A jeśli to nie jest ważne, dlaczego się o to martwisz?)
Wyrażenia przypadków
Rozważ następujące:
foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo ( []) = "end"
Wszystkie trzy pierwsze równania sprawdzają, czy lista nie jest pusta (między innymi). Ale sprawdzanie tego samego trzy razy jest marnotrawstwem. Na szczęście kompilator bardzo łatwo zoptymalizuje to do kilku wyrażeń zagnieżdżonych. W tym przypadku coś takiego
foo xs =
case xs of
y:ys ->
case y of
0 -> "zero"
1 -> "one"
_ -> foo ys
[] -> "end"
Jest to raczej mniej intuicyjne, ale bardziej wydajne. Ponieważ kompilator może łatwo wykonać tę transformację, nie musisz się tym martwić. Po prostu napisz swój wzór pasujący w najbardziej intuicyjny możliwy sposób; kompilator bardzo dobrze radzi sobie z porządkowaniem i porządkowaniem, aby był tak szybki, jak to możliwe.
Połączenie
Standardowym idiomem Haskella do przetwarzania list jest łączenie ze sobą funkcji, które pobierają jedną listę i tworzą nową listę. Przykładem kanonicznym
map g . map f
Niestety, podczas gdy lenistwo gwarantuje pominięcie niepotrzebnej pracy, wszystkie alokacje i zwolnienia dla wydajności sap listy pośredniej. „Fusion” lub „wylesianie” to miejsce, w którym kompilator próbuje wyeliminować te pośrednie kroki.
Problem w tym, że większość z tych funkcji ma charakter rekurencyjny. Bez rekurencji byłoby to elementarne ćwiczenie polegające na ściśnięciu wszystkich funkcji w jednym dużym bloku kodu, uruchomieniu nad nim prostownika i wygenerowaniu naprawdę optymalnego kodu bez list pośrednich. Ale z powodu rekurencji to nie zadziała.
Możesz użyć {-# RULE #-}pragmy, aby naprawić niektóre z tych problemów. Na przykład,
{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}
Teraz za każdym razem, gdy GHC widzi mapwniosek map, ściska go w jednym przejściu nad listą, eliminując listę pośrednią.
Problem w tym, że działa to tylko w przypadku, gdy mapnastępuje map. Istnieje wiele innych możliwości - mappo których następuje filter, filtera następnie mapitd. Zamiast ręcznego kodowania opracowano rozwiązanie dla każdej z nich, tak zwane „połączenie strumieniowe”. To bardziej skomplikowana sztuczka, której nie będę tutaj opisywał.
Krótko mówiąc: są to wszystkie specjalne sztuczki optymalizacyjne napisane przez programistę . Sam GHC nic nie wie o fuzji; wszystko to znajduje się na liście bibliotek i innych bibliotek kontenerów. Tak więc, jakie są optymalizacje, zależy od tego, jak są napisane biblioteki kontenerów (lub, bardziej realistycznie, z jakich bibliotek zdecydujesz się korzystać).
Na przykład, jeśli pracujesz z tablicami Haskell '98, nie spodziewaj się żadnego fuzji. Ale rozumiem, że vectorbiblioteka ma szerokie możliwości łączenia. Chodzi o biblioteki; kompilator po prostu zapewnia RULESpragmę. (Nawiasem mówiąc, co jest niezwykle potężne. Jako autor biblioteki możesz go użyć do przepisania kodu klienta!)
Meta:
Zgadzam się z ludźmi mówiącymi: „najpierw kod, drugi profil, trzeci optymalizuj”.
Zgadzam się również z ludźmi mówiącymi: „warto mieć model mentalny, ile kosztują dane decyzje projektowe”.
Równowaga we wszystkich rzeczach i to wszystko ...