Konwencja wywoływania GHC dla argumentów funkcji typu suma

Question

Czy GHC kiedykolwiek rozpakowuje typy sum, przekazując je do funkcji? Na przykład, powiedzmy, że mamy następujące rodzaje:

data Foo 
    = Foo1 {-# UNPACK #-} !Int {-# UNPACK #-} !Word 
    | Foo2 {-# UNPACK #-} !Int 
    | Foo3 {-# UNPACK #-} !Word 

Potem zdefiniować funkcję, która jest straszny w swojej Foo argumentu:

consumeFoo :: Foo -> Int 
consumeFoo x = case x of ... 

w czasie wykonywania, gdy zgłoszę consumeFoo, co mogę spodziewać się? GHC calling convention ma przekazywać argumenty w rejestrach (lub na stosie, gdy jest ich zbyt dużo). Widzę dwa sposoby na to, aby argument przemijał:

1. Wskaźnik na Foo na stercie zostaje przekazany jako jeden argument.
2. Stosuje się trzyargumentową reprezentację Foo, jeden argument reprezentujący użyty konstruktor danych i dwa pozostałe reprezentujące możliwe wartości Int i Word w konstruktorze danych.

Wolałbym drugą reprezentację, ale nie wiem, czy tak naprawdę to się dzieje. Jestem świadomy lądowania w GHC 8.2, ale nie jest jasne, czy robi to, co chcę. Gdybym zamiast tego napisał funkcję jako:

consumeFooAlt :: (# (# Int#, Word# #) | Int# | Word# #) -> Int 

Wtedy oczekiwałbym, że ocena (2) będzie tym, co się stanie. A Unpacking section strony sum niespakowanego wskazuje, że mogę to zrobić również:

data Wrap = Wrap {-# UNPACK #-} !Foo 
consumeFooAlt2 :: Wrap -> Int 

i że powinien również mieć reprezentację chcę, myślę.

Moje pytanie brzmi: bez użycia typu opakowania lub surowej rozpakowanej sumy, w jaki sposób mogę zagwarantować, że suma zostanie rozpakowana do rejestrów (lub na stos), gdy przekazuję ją jako argument do funkcji? Jeśli jest to możliwe, czy jest to coś, co GHC 8.0 może już zrobić, czy jest to coś, co będzie dostępne tylko w GHC 8.2?

Answer 1

Po pierwsze: gwarantowana optymalizacja i GHC nie mieszają się dobrze. Ze względu na wysoki poziom bardzo trudno jest przewidzieć kod generowany przez GHC w każdym przypadku. Jedynym sposobem, aby się upewnić, jest spojrzenie na Rdzeń. Jeśli opracowujesz niezwykle zależną od wydajności aplikację z GHC, musisz się dowiedzieć z Core I.

Nie jestem świadomy żadnej optymalizacji w GHC, która robi dokładnie to, co opisujesz. Oto przykładowy program: pierwsze spojrzenie

module Test where 

data Sum = A {-# UNPACK #-} !Int | B {-# UNPACK #-} !Int 

consumeSum :: Sum -> Int 
consumeSum x = case x of 
    A y -> y + 1 
    B y -> y + 2 

{-# NOINLINE consumeSumNoinline #-} 
consumeSumNoinline = consumeSum 

{-# INLINE produceSumInline #-} 
produceSumInline :: Int -> Sum 
produceSumInline x = if x == 0 then A x else B x 

{-# NOINLINE produceSumNoinline #-} 
produceSumNoinline :: Int -> Sum 
produceSumNoinline x = if x == 0 then A x else B x 

test :: Int -> Int 
--test x = consumeSum (produceSumInline x) 
test x = consumeSumNoinline (produceSumNoinline x) 

Miejmy na to, co się dzieje, jeśli nie inline consumeSum ani produceSum. Oto rdzeń:

test :: Int -> Int 
test = \ (x :: Int) -> consumeSumNoinline (produceSumNoinline x) 

(produkowany z ghc-core test.hs -- -dsuppress-unfoldings -dsuppress-idinfo -dsuppress-module-prefixes -dsuppress-uniques)

tutaj widzimy, że GHC (8,0 w tym przypadku) nie unbox typ suma przekazywana jako argument funkcji. Nic się nie zmieni, jeśli wstawimy albo consumeSum lub produceSum.

Jeśli inline obie jednak wtedy następujący kod generowany jest:

test :: Int -> Int 
test = 
    \ (x :: Int) -> 
    case x of _ { I# x1 -> 
    case x1 of wild1 { 
     __DEFAULT -> I# (+# wild1 2#); 
     0# -> lvl1 
    } 
    } 

Co tu się stało jest to, że przez inline, GHC kończy się:

\x -> case (if x == 0 then A x else B x) of 
    A y -> y + 1 
    B y -> y + 2 

który poprzez sprawy-of -case (if jest tylko specjalny case) zostaje przekształcony:

\x -> if x == 0 then case (A x) of ... else case (B x) of ... 

Teraz jest to przypadek znanego konstruktora, więc GHC może zmniejszyć sprawę w czasie kompilacji kończąc:

\x -> if x == 0 then x + 1 else x + 2 

więc całkowicie wyeliminowane konstruktora.

---

Podsumowując, uważam, że GHC nie ma żadnego pojęcia o „rozpakowanych Sum” typu wcześniejszej do wersji 8.2, która ma zastosowanie również funkcjonować argumenty. Jedynym sposobem na uzyskanie kwot "unboxed" jest całkowite wyeliminowanie konstruktora za pomocą inliningu.

Answer 2

Jeśli potrzebujesz takiej optymalizacji, najprostszym rozwiązaniem jest zrobienie tego samemu. Myślę, że istnieje rzeczywiście wiele sposobów, aby to osiągnąć, ale jeden jest:

data Which = Left | Right | Both 
data Foo = Foo Which Int Word 

rozpakowywanie wszelkich polach tego typu jest całkowicie bez znaczenia dla kwestii „kształtu reprezentacji”, która jest, co naprawdę o to pytają. Wyliczenia są już wysoce zoptymalizowane - zawsze tworzona jest tylko jedna wartość dla każdego konstruktora - więc dodanie tego pola nie ma wpływu na wydajność. Rozpakowana reprezentacja tego typu jest dokładnie tym, czego potrzebujesz - jedno słowo dla konstruktora Which i po jednym dla każdego pola.

Jeśli piszesz swoje funkcje w odpowiedni sposób, można uzyskać prawidłowego kodu:

data Which = Lft | Rgt | Both 
data Foo = Foo Which {-# UNPACK #-} !Int {-# UNPACK #-} !Word 

consumeFoo :: Foo -> Int 
consumeFoo (Foo w l r) = 
    case w of 
    Lft -> l 
    Rgt -> fromIntegral r 
    Both -> l + fromIntegral r 

Wygenerowany rdzeń jest dość oczywista:

consumeFoo :: Foo -> Int 
consumeFoo = 
    \ (ds :: Foo) -> 
    case ds of _ { Foo w dt dt1 -> 
    case w of _ { 
     Lft -> I# dt; 
     Rgt -> I# (word2Int# dt1); 
     Both -> I# (+# dt (word2Int# dt1)) 
    } 
    } 

Jednak dla prostych programów, takich jak:

consumeFoos = foldl' (+) 0 . map consumeFoo 

Ta optymalizacja nie ma znaczenia. Jak wskazano w drugiej odpowiedzi, wewnętrzna funkcja consumeFoo właśnie inlined:

Rec { 
$wgo :: [Foo] -> Int# -> Int# 
$wgo = 
    \ (w :: [Foo]) (ww :: Int#) -> 
    case w of _ { 
     [] -> ww; 
     : y ys -> 
     case y of _ { 
      Lft dt -> $wgo ys (+# ww dt); 
      Rgt dt -> $wgo ys (+# ww (word2Int# dt)); 
      Both dt dt1 -> $wgo ys (+# ww (+# dt (word2Int# dt1))) 
     } 
    } 
end Rec } 

vs.

Rec { 
$wgo :: [Foo] -> Int# -> Int# 
$wgo = 
    \ (w :: [Foo]) (ww :: Int#) -> 
    case w of _ { 
     [] -> ww; 
     : y ys -> 
     case y of _ { Foo w1 dt dt1 -> 
     case w1 of _ { 
      Lft -> $wgo ys (+# ww dt); 
      Rgt -> $wgo ys (+# ww (word2Int# dt1)); 
      Both -> $wgo ys (+# ww (+# dt (word2Int# dt1))) 
     } 
     } 
    } 
end Rec } 

, który w prawie każdym przypadku, gdy pracuje przy niskim poziomie, rozpakowane dane, jest w każdym razie, ponieważ większość twoich funkcji jest niewielkich rozmiarów i niewiele kosztuje.