Spezialisierung mit Einschränkungen

156

Ich habe Probleme, GHC dazu zu bringen, eine Funktion mit einer Klassenbeschränkung zu spezialisieren. Ich habe ein minimales Beispiel für mein Problem hier: Foo.hs und Main.hs . Die beiden Dateien werden kompiliert (GHC 7.6.2 ghc -O3 Main) und ausgeführt.

HINWEIS: Foo.hs ist wirklich reduziert. Wenn Sie sehen möchten, warum die Einschränkung benötigt wird, können Sie hier etwas mehr Code sehen . Wenn ich den Code in eine einzelne Datei einfüge oder viele andere kleinere Änderungen vornehme, leitet GHC den Aufruf einfach an plusFastCyc. Dies wird im realen Code nicht passieren, da plusFastCycGHC zu groß ist, um inline zu sein, selbst wenn es markiert ist INLINE. Es geht darum , den Anruf zu spezialisieren plusFastCycund nicht zu inline. plusFastCycwird an vielen Stellen im realen Code aufgerufen, so dass das Duplizieren einer so großen Funktion nicht wünschenswert wäre, selbst wenn ich GHC dazu zwingen könnte.

Der Code von Interesse ist der plusFastCycin Foo.hs, hier wiedergegebene:

{-# INLINEABLE plusFastCyc #-}
{-# SPECIALIZE plusFastCyc :: 
         forall m . (Factored m Int) => 
              (FastCyc (VT U.Vector m) Int) -> 
                   (FastCyc (VT U.Vector m) Int) -> 
                        (FastCyc (VT U.Vector m) Int) #-}

-- Although the next specialization makes `fcTest` fast,
-- it isn't useful to me in my real program because the phantom type M is reified
-- {-# SPECIALIZE plusFastCyc :: 
--          FastCyc (VT U.Vector M) Int -> 
--               FastCyc (VT U.Vector M) Int -> 
--                    FastCyc (VT U.Vector M) Int #-}

plusFastCyc :: (Num (t r)) => (FastCyc t r) -> (FastCyc t r) -> (FastCyc t r)
plusFastCyc (PowBasis v1) (PowBasis v2) = PowBasis $ v1 + v2

Die Main.hsDatei hat zwei Treiber: vtTestdie in ~ 3 Sekunden ausgeführt werden und fcTestdie in ~ 83 Sekunden ausgeführt werden, wenn sie mit -O3 unter Verwendung der forallSpezialisierung 'd kompiliert werden .

Der Kern zeigt, dass für den vtTestTest der Additionscode auf UnboxedVektoren über Ints usw. spezialisiert ist, während für generischen Vektorcode verwendet wird fcTest. In Zeile 10 können Sie sehen , dass GHC eine spezielle Version von schreibt plusFastCyc, im Vergleich zu der generischen Version auf Linie 167. Die Regel für die Spezialisierung auf der Leitung 225. ich diese Regel glaube , auf der Linie 270. (Feuer soll main6Anrufe iterate main8 y, so main8ist wo plusFastCycsollte spezialisiert werden.)

Mein Ziel ist es, fcTestso schnell wie möglich zu vtTestspezialisieren plusFastCyc. Ich habe zwei Möglichkeiten gefunden, dies zu tun:

  1. Explicity Call inlinevon GHC.Extsin fcTest.
  2. Entfernen Sie die Factored m IntEinschränkung auf plusFastCyc.

Option 1 ist unbefriedigend, da es sich bei der eigentlichen Codebasis plusFastCycum eine häufig verwendete Operation und eine sehr große Funktion handelt, sodass sie nicht bei jeder Verwendung eingefügt werden sollte. Vielmehr sollte GHC eine spezielle Version von aufrufen plusFastCyc. Option 2 ist nicht wirklich eine Option, da ich die Einschränkung im realen Code benötige.

Ich habe eine Vielzahl von Optionen versucht , mit (und nicht mit ) INLINE, INLINABLEund SPECIALIZE, aber nichts scheint zu funktionieren. ( BEARBEITEN : Ich habe möglicherweise zu viel entfernt plusFastCyc, um mein Beispiel klein zu machen, sodass INLINEdie Funktion möglicherweise inline ist. Dies geschieht in meinem realen Code nicht, weil er plusFastCycso groß ist.) In diesem speziellen Beispiel bin ich es nicht Erhalten von match_co: needs more casesoder RULE: LHS too complicated to desugar(und hier ) Warnungen, obwohl ich viele match_coWarnungen erhalten habe, bevor ich das Beispiel minimiert habe. Vermutlich ist das "Problem" die Factored m IntEinschränkung in der Regel; Wenn ich Änderungen an dieser Einschränkung vornehme, fcTestläuft sie so schnell wie vtTest.

Mache ich etwas, das GHC einfach nicht mag? Warum wird GHC das nicht spezialisieren plusFastCycund wie kann ich es machen?

AKTUALISIEREN

Das Problem besteht weiterhin in GHC 7.8.2, daher ist diese Frage immer noch relevant.

Crockeea
quelle
3
Ich habe gerade versucht, mich auf ein bestimmtes zu spezialisieren m , nämlich M. Dies hat die Arbeit erledigt, aber ich kann mich nicht auf bestimmte Phantomtypen im realen Programm spezialisieren, da diese bestätigt werden.
Crockeea
Ich habe auch einen GHC-Fehlerbericht ghc.haskell.org/trac/ghc/ticket/8668 eingereicht, aber das Problem ist noch offen. Der Fehlerberichtsprozess hat mir geholfen, die Frage ein wenig zu bereinigen, sodass es hoffentlich einfacher ist, herauszufinden, was los ist.
Crockeea
@monojohnny Tut mir leid das zu hören, ich glaube du kannst es als solches kennzeichnen. Ich glaube, ich bitte GHC, etwas ziemlich Vernünftiges zu tun, und es wird es nicht tun. Ich bin nicht sicher, ob ich es falsch mache oder ob dies eine Eigenart mit dem Compiler ist, die möglicherweise eine Problemumgehung hat. Ich habe Problemumgehungen für Spezialisierung und Regeln in einer bestimmten Bibliothek zum Thema Hackage gesehen, die mir derzeit entgeht. Daher hoffe ich, dass jemand in der Community mit mehr GHC-Erfahrung als ich selbst weiß, wie man Spezialisierung erreicht.
Crockeea
1
Ich entschuldige mich für den Ton meines Kommentars - es ist nicht mein bester Beitrag zu dieser Seite - es ist wirklich nichts Falsches an Ihrem Beitrag (Es ist mein Unverständnis, das die Quelle meines Ärgers war, denke ich!)
Monojohnny
@monojohnny Entschuldigung akzeptiert, aber es ist schade, dass Downvote jetzt gesperrt ist
;-)

Antworten:

5

GHC bietet auch eine Option für SPECIALIZEeine Instanzdeklaration der Typklasse. Ich habe dies mit dem (erweiterten) Code von Foo.hsversucht, indem ich Folgendes eingegeben habe:

instance (Num r, V.Vector v r, Factored m r) => Num (VT v m r) where 
    {-# SPECIALIZE instance ( Factored m Int => Num (VT U.Vector m Int)) #-}
    VT x + VT y = VT $ V.zipWith (+) x y

Diese Änderung erreichte jedoch nicht die gewünschte Beschleunigung. Durch diese Leistungsverbesserung wurde manuell eine spezielle Instanz für den Typ VT U.Vector m Intmit denselben Funktionsdefinitionen wie folgt hinzugefügt :

instance (Factored m Int) => Num (VT U.Vector m Int) where 
    VT x + VT y = VT $ V.zipWith (+) x y

Dies erfordert das Hinzufügen OverlappingInstancesund FlexibleInstancesin LANGUAGE.

Interessanterweise bleibt im Beispielprogramm die mit der überlappenden Instanz erzielte Beschleunigung erhalten, auch wenn Sie alle SPECIALIZEund INLINABLEPragma entfernen .

Diego E. Alonso-Blas
quelle
Auf jeden Fall nicht optimal, aber es ist die erste Lösung, die das Ziel tatsächlich erreicht, also nehme ich es wohl
erstmal an