Jakich optymalizacji można oczekiwać, aby GHC działał niezawodnie?

GHC ma wiele optymalizacji, które może wykonać, ale nie wiem, jakie są one wszystkie, ani jak prawdopodobne jest ich wykonanie i w jakich okolicznościach.

Moje pytanie brzmi: jakich przekształceń mogę się spodziewać za każdym razem, czy prawie tak? Jeśli często patrzę na fragment kodu, który będzie często wykonywany (oceniany), a moją pierwszą myślą jest „hmm, może powinienem to zoptymalizować”, w którym to przypadku powinna być moja druga myśl: „nawet o tym nie myśl, GHC ma to?

Czytałem gazetę Stream Fusion: od list do strumieni do niczego , a technika, którą zastosowali, przepisując przetwarzanie listy do innej formy, którą normalne optymalizacje GHC następnie niezawodnie zoptymalizowałyby do prostych pętli, była dla mnie nowością. Jak mogę sprawdzić, kiedy moje własne programy kwalifikują się do tego rodzaju optymalizacji?

W podręczniku GHC znajduje się kilka informacji , ale jest to tylko część odpowiedzi na pytanie.

EDYCJA: Zaczynam nagrodę. To, co chciałbym, to lista transformacji niższego poziomu, takich jak lambda / let / case-floating, specjalizacja argumentów typu / konstruktor / funkcja, analiza ścisłości i rozpakowywanie, pracownik / opakowanie i cokolwiek innego znaczącego GHC, które pominąłem , wraz z objaśnieniami i przykładami kodu wejściowego i wyjściowego oraz idealnie ilustruje sytuacje, w których całkowity efekt jest większy niż suma jego części. I najlepiej wspomnieć o tym, kiedy transformacje nie będązdarzyć. Nie oczekuję nowatorskich wyjaśnień każdej transformacji, wystarczy kilka zdań i przykłady kodu liniowego (lub link, jeśli nie jest to dwadzieścia stron artykułu naukowego), o ile duży obraz jest jasne do końca. Chcę być w stanie spojrzeć na fragment kodu i dobrze zgadywać, czy skompiluje się on do ciasnej pętli, dlaczego nie, lub co musiałbym zmienić, aby to zrobić. (Nie interesuje mnie tu tak bardzo duże ramy optymalizacji, takie jak synteza strumieniowa (po prostu przeczytałem o tym artykuł); bardziej wiedza, którą ludzie piszący te ramy mają).

Ta strona GHC Trac również dość dobrze wyjaśnia przejścia. Ta strona wyjaśnia kolejność optymalizacji, jednak, podobnie jak większość Wiki Trac, jest nieaktualna.

Jeśli chodzi o szczegóły, najlepiej jest sprawdzić, jak kompilowany jest określony program. Najlepszym sposobem, aby sprawdzić, jakie optymalizacje są przeprowadzane, jest kompilacja programu w trybie pełnym, przy użyciu -vflagi. Biorąc jako przykład pierwszy fragment Haskell, który mogłem znaleźć na moim komputerze:

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

Patrząc od pierwszego *** Simplifier:do ostatniego, gdzie zachodzą wszystkie fazy optymalizacji, widzimy całkiem sporo.

Po pierwsze, Simplifier działa pomiędzy prawie wszystkimi fazami. To znacznie ułatwia pisanie wielu podań. Na przykład przy wdrażaniu wielu optymalizacji po prostu tworzą reguły przepisywania w celu propagowania zmian zamiast konieczności ręcznego wykonywania tych zmian. Uproszczenie obejmuje szereg prostych optymalizacji, w tym wstawianie i łączenie. Głównym ograniczeniem tego, co wiem, jest to, że GHC odmawia wbudowania funkcji rekurencyjnych i że rzeczy muszą być poprawnie nazwane, aby fuzja zadziałała.

Następnie widzimy pełną listę wszystkich przeprowadzonych optymalizacji:

• Specjalizować

  Podstawową ideą specjalizacji jest usunięcie polimorfizmu i przeciążenia poprzez identyfikację miejsc, w których wywoływana jest funkcja, i tworzenie wersji funkcji, które nie są polimorficzne - są specyficzne dla typów, z którymi są wywoływane. Możesz także powiedzieć kompilatorowi, aby zrobił to z SPECIALISEpragmą. Jako przykład weź funkcję silni:

  fac :: (Num a, Eq a) => a -> a
  fac 0 = 1
  fac n = n * fac (n - 1)

  Ponieważ kompilator nie zna żadnych właściwości mnożenia, które ma być użyte, nie może go w ogóle zoptymalizować. Jeśli jednak zobaczy, że jest używany na Int, może teraz utworzyć nową wersję, różniącą się tylko typem:

  fac_Int :: Int -> Int
  fac_Int 0 = 1
  fac_Int n = n * fac_Int (n - 1)

  Następnie reguły wymienione poniżej mogą zostać odpalone, a ty skończysz z czymś, co działa na rozpakowanym Int s, co jest znacznie szybsze niż oryginał. Innym sposobem spojrzenia na specjalizację jest częściowe zastosowanie w słownikach klas typów i zmiennych typu.

  Tutaj źródło zawiera mnóstwo notatek.

• Wypłynąć

  EDYCJA: Najwyraźniej wcześniej to źle zrozumiałem. Moje wyjaśnienie całkowicie się zmieniło.

  Podstawową ideą tego jest przeniesienie obliczeń, których nie należy powtarzać poza funkcjami. Załóżmy na przykład, że mieliśmy:

  \x -> let y = expensive in x+y

  W powyższej lambda za każdym razem, gdy funkcja jest wywoływana, yjest przeliczana. Lepszą funkcją, którą tworzy wypływanie, jest

  let y = expensive in \x -> x+y

  Aby ułatwić ten proces, można zastosować inne transformacje. Na przykład dzieje się tak:

   \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

  Ponownie, wielokrotne obliczenia są zapisywane.

  źródło tym przypadku jest bardzo czytelne.

  W tej chwili wiązania między dwoma sąsiednimi lambdami nie są unoszone. Na przykład tak się nie dzieje:

  \x y -> let t = x+x in ...

  zamierzam

   \x -> let t = x+x in \y -> ...

• Unoszą się do wewnątrz

  Cytując kod źródłowy,

  Głównym celem floatInwardsjest przestawienie się na gałęzie skrzynki, abyśmy nie przydzielali rzeczy, zapisywali je na stosie, a następnie odkrywali, że nie są one potrzebne w wybranej gałęzi.

  Jako przykład załóżmy, że mamy takie wyrażenie:

  let x = big in
      case v of
          True -> x + 1
          False -> 0

  Jeśli voceni to False, to przydzielając x, co jest prawdopodobnie jakaś wielka gratka, zmarnowaliśmy czas i przestrzeń. Pływające do wewnątrz naprawia to, powodując:

  case v of
      True -> let x = big in x + 1
      False -> let x = big in 0

  , który jest następnie zastępowany przez uproszczenie za pomocą

  case v of
      True -> big + 1
      False -> 0

  Ten artykuł , choć obejmuje inne tematy, daje dość jasne wprowadzenie. Zauważ, że pomimo ich nazw, wypływanie i wypływanie nie wchodzi w nieskończoną pętlę z dwóch powodów:

  1. Float w float pozwala na caseinstrukcje, a float zajmuje się funkcjami.
  2. Istnieje ustalona kolejność podań, więc nie powinny się one zmieniać naprzemiennie.

• Analiza popytu

  Analiza popytu lub analiza ścisłości jest mniej transformacją, a bardziej, jak sugeruje nazwa, przepustką do gromadzenia informacji. Kompilator znajduje funkcje, które zawsze oceniają ich argumenty (lub przynajmniej niektóre z nich), i przekazuje te argumenty przy użyciu funkcji call-by-value zamiast call-by-need. Ponieważ możesz uniknąć ogólnych obciążeń, jest to często znacznie szybsze. Wiele problemów z wydajnością w Haskell wynika albo z tego błędu, albo kodu po prostu nie jest wystarczająco rygorystyczny. Prostym przykładem jest różnica między używaniem foldr,foldl ifoldl'podsumowując listę liczb całkowitych - pierwsza powoduje przepełnienie stosu, druga powoduje przepełnienie sterty, a ostatnia działa poprawnie, ze względu na ścisłość. Jest to prawdopodobnie najłatwiejszy do zrozumienia i najlepiej udokumentowany ze wszystkich. Uważam, że polimorfizm i kod CPS często to pokonują.

• Worker Wrapper wiąże

  Podstawową ideą transformacji pracownik / opakowanie jest wykonanie ciasnej pętli na prostej strukturze, przekształcając ją do i z tej struktury na końcach. Weźmy na przykład tę funkcję, która oblicza silnię liczby.

  factorial :: Int -> Int
  factorial 0 = 1
  factorial n = n * factorial (n - 1)

  Używając definicji Intw GHC, mamy

  factorial :: Int -> Int
  factorial (I# 0#) = I# 1#
  factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
      I# down# -> down#)

  Zauważ, jak kod jest objęty I#s? Możemy je usunąć, wykonując następujące czynności:

  factorial :: Int -> Int
  factorial (I# n#) = I# (factorial# n#)
  
  factorial# :: Int# -> Int#
  factorial# 0# = 1#
  factorial# n# = n# *# factorial# (n# -# 1#)

  Chociaż ten konkretny przykład mógł być również wykonany przez SpecConstr, transformacja proces roboczy / otoki jest bardzo ogólna pod względem możliwości.

• Wspólne podwyrażenie

  Jest to kolejna naprawdę prosta optymalizacja, która jest bardzo skuteczna, podobnie jak analiza ścisłości. Podstawową ideą jest to, że jeśli masz dwa takie same wyrażenia, będą miały tę samą wartość. Na przykład, jeśli fibkalkulator liczb Fibonacciego, CSE przekształci się

  fib x + fib x

  w

  let fib_x = fib x in fib_x + fib_x

  co zmniejsza obliczenia o połowę. Niestety może to czasami przeszkadzać w innych optymalizacjach. Innym problemem jest to, że oba wyrażenia muszą znajdować się w tym samym miejscu i muszą być składniowo takie same, a nie takie same pod względem wartości. Na przykład CSE nie uruchomi się w następującym kodzie bez szeregu wstawiania:

  x = (1 + (2 + 3)) + ((1 + 2) + 3)
  y = f x
  z = g (f x) y

  Jednakże, jeśli kompilujesz za pomocą llvm, możesz uzyskać część tego łącznie, ze względu na przepustkę Global Value Numbering.

• Uwolnij sprawę

  To wydaje się być strasznie udokumentowaną transformacją, poza tym, że może powodować eksplozję kodu. Oto przeformatowana (i nieco przepisana) wersja małej dokumentacji, którą znalazłem:

  Ten moduł podchodzi Corei szuka casewolnych zmiennych. Kryterium jest takie: jeśli casena drodze do wywołania rekurencyjnego znajduje się wolna zmienna, wówczas wywołanie rekurencyjne zostanie zastąpione rozwijaniem. Na przykład w

  f = \ t -> case v of V a b -> a : f t

  wewnętrzna fjest wymieniona. robić

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> case v of V a b -> a : f t in f) t

  Zwróć uwagę na potrzebę zacienienia. Upraszczamy, rozumiemy

  f = \ t -> case v of V a b -> a : (letrec f = \ t -> a : f t in f t)

  To jest lepszy kod, ponieważ ajest wolny w środku letrec, niż wymaga projekcji v. Zauważ, że dotyczy to wolnych zmiennych , w przeciwieństwie do SpecConstr, który zajmuje się argumentami o znanej formie.

  Zobacz poniżej, aby uzyskać więcej informacji o SpecConstr.

• SpecConstr - przekształca programy takie jak

  f (Left x) y = somthingComplicated1
  f (Right x) y = somethingComplicated2

  w

  f_Left x y = somethingComplicated1
  f_Right x y = somethingComplicated2
  
  {-# INLINE f #-}
  f (Left x) = f_Left x
  f (Right x) = f_Right x

  Jako rozszerzony przykład weź tę definicję last:

  last [] = error "last: empty list"
  last (x:[]) = x
  last (x:x2:xs) = last (x2:xs)

  Najpierw przekształcamy to w

  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

  Następnie działa uproszcznik i mamy

  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

  Zauważ, że program jest teraz szybszy, ponieważ nie boksujemy i nie rozpakowujemy na początku listy. Należy również pamiętać, że wstawianie jest kluczowe, ponieważ pozwala na faktyczne stosowanie nowych, bardziej wydajnych definicji, a także na ulepszanie definicji rekurencyjnych.

  SpecConstr jest kontrolowany przez szereg heurystyk. Te wymienione w artykule to:

  1. Jagnięta są wyraźne, a arsenał jest a.
  2. Prawa strona jest „wystarczająco mała”, coś kontrolowanego przez flagę.
  3. Ta funkcja jest rekurencyjna, a po prawej stronie używane jest specjalne wywołanie.
  4. Wszystkie argumenty funkcji są obecne.
  5. Co najmniej jeden z argumentów to aplikacja konstruktora.
  6. Argument ten jest analizowany gdzieś w funkcji.

  Jednak heurystyka prawie na pewno się zmieniła. W rzeczywistości w artykule wspomniano o alternatywnej szóstej heurystyce:

  Specjalizujemy się w argumentach xtylko wtedy, gdy xjest on analizowany tylko przez casei nie jest przekazywany do zwykłej funkcji lub zwracany jako część wyniku.

To był bardzo mały plik (12 linii), więc prawdopodobnie nie spowodował tak wielu optymalizacji (choć myślę, że to wszystko zrobił). To również nie mówi ci, dlaczego wybrał te podania i dlaczego ustawił je w tej kolejności.

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 ...

Jeśli używane jest wiązanie let v = rhs tylko w jednym miejscu, możesz liczyć na kompilator, aby wstawić go, nawet jeśli rhs jest duży.

Wyjątkiem (który prawie nie jest jednym w kontekście bieżącego pytania) jest lambdas ryzykujący powielanie pracy. Rozważać:

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

tam wstawianie v byłoby niebezpieczne, ponieważ jedno (syntaktyczne) użycie przełożyłoby się na 99 dodatkowych ocen rh. Jednak w tym przypadku jest mało prawdopodobne, aby wstawić go ręcznie. Zasadniczo możesz użyć reguły:

Jeśli rozważysz wstawienie nazwy, która pojawia się tylko raz, kompilator i tak to zrobi.

Jako szczęśliwy wniosek, użycie wiązania let po prostu w celu rozłożenia długiego stwierdzenia (z nadzieją na uzyskanie przejrzystości) jest zasadniczo bezpłatne.

Pochodzi z community.haskell.org/~simonmar/papers/inline.pdf, który zawiera o wiele więcej informacji na temat wstawiania.