Transitivität der Auto-Spezialisierung in GHC

392

Aus den Dokumenten für GHC 7.6:

[Y] Oft brauchen Sie gar nicht erst das Pragma SPEZIALISIEREN. Beim Kompilieren eines Moduls M berücksichtigt der Optimierer von GHC (mit -O) automatisch jede in M ​​deklarierte überladene Funktion der obersten Ebene und ist auf die verschiedenen Typen spezialisiert, bei denen es in M ​​aufgerufen wird. Der Optimierer berücksichtigt auch jede importierte INLINABLE überladene Funktion. und spezialisiert es auf die verschiedenen Typen, bei denen es in M ​​genannt wird.

und

Darüber hinaus erstellt GHC bei einem SPECIALIZE-Pragma für eine Funktion f automatisch Spezialisierungen für alle von f aufgerufenen Funktionen, die von Typklassen überladen sind, wenn sie sich im selben Modul wie das SPECIALIZE-Pragma befinden oder INLINABLE sind. und so weiter, transitiv.

Daher sollte GHC einige / die meisten / alle (?) Funktionen, die INLINABLE ohne Pragma markiert sind, automatisch spezialisieren. Wenn ich ein explizites Pragma verwende, ist die Spezialisierung transitiv. Meine Frage ist: Ist die Auto- Spezialisierung transitiv?

Hier ist ein kleines Beispiel:

Main.hs:

import Data.Vector.Unboxed as U
import Foo

main =
    let y = Bar $ Qux $ U.replicate 11221184 0 :: Foo (Qux Int)
        (Bar (Qux ans)) = iterate (plus y) y !! 100
    in putStr $ show $ foldl1' (*) ans

Foo.hs:

module Foo (Qux(..), Foo(..), plus) where

import Data.Vector.Unboxed as U

newtype Qux r = Qux (Vector r)
-- GHC inlines `plus` if I remove the bangs or the Baz constructor
data Foo t = Bar !t
           | Baz !t

instance (Num r, Unbox r) => Num (Qux r) where
    {-# INLINABLE (+) #-}
    (Qux x) + (Qux y) = Qux $ U.zipWith (+) x y

{-# INLINABLE plus #-}
plus :: (Num t) => (Foo t) -> (Foo t) -> (Foo t)
plus (Bar v1) (Bar v2) = Bar $ v1 + v2

GHC ist auf den Aufruf von spezialisiert plus, jedoch nicht auf (+)die Qux NumInstanz, die die Leistung beeinträchtigt.

Ein explizites Pragma

{-# SPECIALIZE plus :: Foo (Qux Int) -> Foo (Qux Int) -> Foo (Qux Int) #-}

führt zu einer transitiven Spezialisierung, wie in den Dokumenten angegeben, (+)ist also spezialisiert und der Code ist 30x schneller (beide kompiliert mit -O2). Ist das erwartetes Verhalten? Sollte ich nur erwarten (+), mich transitiv mit einem expliziten Pragma zu spezialisieren?


AKTUALISIEREN

Die Dokumente für 7.8.2 haben sich nicht geändert, und das Verhalten ist dasselbe, sodass diese Frage weiterhin relevant ist.

Crockeea
quelle
33
Ich kenne die Antwort nicht, aber es hört sich so an, als ob sie mit Folgendes zusammenhängt: ghc.haskell.org/trac/ghc/ticket/5928 Es lohnt sich wahrscheinlich, ein neues Ticket zu eröffnen oder Ihre Informationen dort hinzuzufügen, wenn Sie der Meinung sind, dass es wahrscheinlich mit 5928 zusammenhängt
Jberryman
6
@jberryman Es scheint zwei Unterschiede zu sein zwischen diesem Ticket und meiner Frage: 1) In dem Ticket, das äquivalent pluswurde nicht als INLINABLE markiert und 2) simonpj angegeben , dass es einige inlining los mit dem Ticket - Code, aber der Kern aus Mein Beispiel zeigt, dass keine der Funktionen inline war (insbesondere konnte ich den zweiten FooKonstruktor nicht loswerden , sonst GHC inlined).
Crockeea
5
Ah, okay. Was passiert, wenn Sie definieren plus (Bar v1) = \(Bar v2)-> Bar $ v1 + v2, dass die LHS am Anrufort vollständig angewendet wird? Wird es inline und setzt dann die Spezialisierung ein?
Jberryman
3
@jberryman Lustig solltest du fragen. Ich war mit dieser Frage auf diesem Weg , die zu diesem Trac-Bericht führte . Ich hatte ursprünglich den Aufruf plus, mich aufgrund dieser Links vollständig zu bewerben, aber tatsächlich wurde ich weniger spezialisiert: Der Anruf an pluswar auch nicht spezialisiert. Ich habe keine Erklärung dafür, wollte es aber für eine andere Frage belassen oder hoffe, dass es in einer Antwort auf diese Frage gelöst wird.
Crockeea
11
Von ghc.haskell.org/trac/ghc/wiki/ReportABug : "Wenn Sie Zweifel haben, melden Sie einfach Ihren Fehler." Sie sollten sich nicht schlecht fühlen, zumal eine ausreichende Anzahl wirklich erfahrener Haskeller hier nicht weiß, wie Sie Ihre Frage beantworten sollen. Testfälle wie diese sind für die GHC-Entwickler wahrscheinlich sehr wertvoll. Wie auch immer - Viel Glück! Die Frage wurde aktualisiert, wenn Sie ein Ticket
einreichen

Antworten:

4

Kurze Antworten:

Die wichtigsten Punkte der Frage sind nach meinem Verständnis die folgenden:

  • "Ist die automatische Spezialisierung transitiv?"
  • Sollte ich nur erwarten, dass (+) transitiv mit einem expliziten Pragma spezialisiert ist?
  • (anscheinend beabsichtigt) Ist das ein Fehler von GHC? Ist es nicht mit der Dokumentation vereinbar?

AFAIK, die Antworten sind Nein, meistens ja, aber es gibt andere Mittel und Nein.

Code-Inlining und Typanwendungsspezialisierung sind ein Kompromiss zwischen Geschwindigkeit (Ausführungszeit) und Codegröße. Die Standardstufe wird etwas beschleunigt, ohne den Code aufzublähen. Die Wahl eines umfassenderen Levels liegt im Ermessen des Programmierers über SPECIALISEPragma.

Erläuterung:

Der Optimierer berücksichtigt auch jede importierte INLINABLE-überladene Funktion und spezialisiert sie auf die verschiedenen Typen, bei denen sie in M ​​aufgerufen wird.

Angenommen, es fhandelt sich um eine Funktion, deren Typ eine Typvariable enthält, adie durch eine Typklasse eingeschränkt wird C a. GHC standardmäßig spezialisiert fin Bezug auf eine Art Anwendung (Substitution afür t) , wenn fmit dieser Art Anwendung in dem Quellcode (a) jede Funktion in dem gleichen Modul oder (b) aufgerufen wird , wenn fgekennzeichnet wird INLINABLE, dann andere Modul , das Einfuhren f von B. Die automatische Spezialisierung ist also nicht transitiv, sondern berührt nur INLINABLEFunktionen, die im Quellcode von importiert und aufgerufen werden A.

Wenn Sie in Ihrem Beispiel die Instanz Numwie folgt umschreiben :

instance (Num r, Unbox r) => Num (Qux r) where
    (+) = quxAdd

quxAdd (Qux x) (Qux y) = Qux $ U.zipWith (+) x y
  • quxAddwird nicht speziell von importiert Main. Mainimportiert das Instanzwörterbuch von Num (Qux Int), und dieses Wörterbuch enthält quxAddim Datensatz für (+). Obwohl das Wörterbuch importiert wird, werden die im Wörterbuch verwendeten Inhalte nicht importiert.
  • plusruft nicht auf quxAdd, es verwendet die Funktion, die für den (+)Datensatz im Instanzwörterbuch von gespeichert ist Num t. Dieses Wörterbuch wird Mainvom Compiler an der Aufrufstelle (in ) festgelegt.
Diego E. Alonso-Blas
quelle