GHC-Aufrufkonvention für Sum-Typ Funktionsargumente

Question

Entpackt GHC Sum-Typen, wenn sie an Funktionen übergeben werden? Zum Beispiel, sagen sie, dass wir den folgenden Typen haben:

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

Dann definiere ich eine Funktion, die in seinem Foo Argumente streng:

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

Zur Laufzeit, wenn ich consumeFoo nennen, was ich kann erwarten zu passieren? Das GHC calling convention soll Argumente in Registern übergeben (oder auf dem Stack, wenn es zu viele gibt). Ich kann auf zwei Arten sehen, dass die Argumentübergabe gehen könnte:

1. Ein Zeiger auf ein Foo auf dem Heap übergeben wird als ein Argument in.
2. Eine dreiargumentale Darstellung von Foo wird verwendet, wobei ein Argument den verwendeten Datenkonstruktor und die anderen beiden die möglichen Werte Int und Word im Datenkonstruktor darstellen.

Ich würde die zweite Darstellung bevorzugen, aber ich weiß nicht, ob es tatsächlich ist, was passiert. Ich bin mir bewusst, UnpackedSumTypes Landung in GHC 8.2, aber es ist unklar, ob es tut, was ich will. Hätte ich stattdessen die Funktion geschrieben als:

Dann würde ich erwarten, dass Auswertung (2) wäre was passiert. Und die Unpacking section der entpackten Summen Seite zeigt an, dass ich dies tun könnte auch:

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

Und das sollte auch die Darstellung habe ich möchte, glaube ich.

Also meine Frage ist, ohne Verwendung eines Wrappertyps oder einer unverpackten Summe, wie kann ich garantieren, dass eine Summe in Register (oder auf den Stapel) entpackt wird, wenn ich es als Argument an eine Funktion übergebe? Wenn es möglich ist, ist es etwas, das GHC 8.0 bereits kann, oder ist es etwas, das nur in GHC 8.2 verfügbar sein wird?

Answer 1

Erstens: Garantierte Optimierung und GHC vermischen sich nicht gut. Aufgrund des hohen Levels ist es sehr schwer vorherzusagen, welchen Code GHC in jedem Fall generieren wird. Der einzige Weg, um sicher zu sein, ist, auf den Kern zu schauen. Wenn Sie eine extrem leistungsabhängige Anwendung mit GHC entwickeln, müssen Sie sich mit Core I vertraut machen.

Mir ist keine Optimierung in GHC bekannt, die genau das tut, was Sie beschreiben. Hier ist ein Beispiel-Programm:

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) 

Lassen Sie uns zunächst einen Blick auf, was passiert, wenn wir nicht consumeSum Inline haben noch produceSum. Hier ist der Kern:

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

(hergestellt mit ghc-core test.hs -- -dsuppress-unfoldings -dsuppress-idinfo -dsuppress-module-prefixes -dsuppress-uniques)

Hier können wir sehen, dass GHC (8.0 in diesem Fall) unbox nicht die Summe Typen als Funktion Argument übergeben. Nichts ändert sich, wenn wir entweder consumeSum oder produceSum inline sind.

Wenn wir beide aber inline, dann wird der folgende Code generiert:

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

Was hier passiert, ist, dass durch inlining, GHC endet mit:

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

, die durch den Fall-of -Fall (if ist nur ein Spezial case) in eingeschaltet wird:

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

Nun, das ist ein Fall mit einem bekannten Konstruktor, so GHC den Fall bei der Kompilierung Ende mit reduzieren:

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

So ist es den Konstruktor vollständig eliminiert.

---

Zusammenfassend glaube ich, dass GHC hat kein Konzept eines „unboxed sum“ Typen vor Version 8.2, die auch Argumente für Funktion gilt. Die einzige Möglichkeit, "ungespeicherte" Summen zu erhalten, besteht darin, den Konstruktor durch Inlining vollständig zu eliminieren.

Answer 2

Wenn Sie eine solche Optimierung benötigen, ist Ihre einfachste Lösung, es selbst zu tun. Ich denke, es gibt tatsächlich viele Möglichkeiten, dies zu erreichen, aber man ist:

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

Das Entpacken aller Felder dieser Art auf die Frage der ‚Form der Darstellung‘ völlig irrelevant ist, das, was Sie fragen wirklich nach. Enumerationen sind bereits hoch optimiert - es wird immer nur ein Wert für jeden Konstruktor erstellt - daher wirkt sich die Hinzufügung dieses Felds nicht auf die Leistung aus. Die entpackte Darstellung dieses Typs ist genau das, was Sie wollen - ein Wort für Which Konstruktor und einen für jedes Feld.

Wenn Sie Ihre Funktionen in der richtigen Art und Weise zu schreiben, erhalten Sie den richtigen Code:

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 

Der erzeugte Kern ist ganz offensichtlich:

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)) 
    } 
    } 

jedoch für einfache Programme wie:

consumeFoos = foldl' (+) 0 . map consumeFoo 

Diese Optimierung macht keinen Unterschied. Wie in der anderen Antwort angezeigt wird, wird die innere Funktion consumeFoo nur 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 } 

gegen

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 } 

Which, jeden Fall in fast, wenn sie mit Low-Level arbeiten, Daten entpackt, ist die Ziel sowieso, da die meisten Ihrer Funktionen klein sind und wenig inline kosten.