Spécialisation avec contraintes

156

J'ai des problèmes pour que GHC spécialise une fonction avec une contrainte de classe. J'ai ici un exemple minimal de mon problème: Foo.hs et Main.hs . Les deux fichiers se compilent (GHC 7.6.2, ghc -O3 Main) et s'exécutent.

REMARQUE: Foo.hs est vraiment dépouillé. Si vous voulez voir pourquoi la contrainte est nécessaire, vous pouvez voir un peu plus de code ici . Si je mets le code dans un seul fichier ou que j'apporte de nombreux autres changements mineurs, GHC intègre simplement l'appel à plusFastCyc. Cela ne se produira pas dans le code réel car il plusFastCycest trop volumineux pour que GHC puisse être intégré, même lorsqu'il est marqué INLINE. Le but est de spécialiser l'appel à plusFastCyc, et non pas en ligne. plusFastCycest appelé à de nombreux endroits dans le code réel, donc dupliquer une fonction aussi volumineuse ne serait pas souhaitable même si je pouvais forcer GHC à le faire.

Le code d'intérêt est le plusFastCycin Foo.hs, reproduit ici:

{-# 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

Le Main.hsfichier a deux pilotes:, vtTestqui s'exécute en ~ 3 secondes, et fcTest, qui s'exécute en ~ 83 secondes lorsqu'il est compilé avec -O3 en utilisant la forallspécialisation 'd.

Le noyau montre que pour le vtTesttest, le code d'addition est spécialisé dans les Unboxedvecteurs sur Ints, etc., tandis que le code vectoriel générique est utilisé pour fcTest. À la ligne 10, vous pouvez voir que GHC écrit une version spécialisée de plusFastCyc, par rapport à la version générique à la ligne 167. La règle de spécialisation est à la ligne 225. Je crois que cette règle devrait être déclenchée à la ligne 270. ( main6appelle iterate main8 y, il en main8est de même où plusFastCycdevrait être spécialisé.)

Mon objectif est de faire fcTestaussi vite qu'en se vtTestspécialisant plusFastCyc. J'ai trouvé deux façons de procéder:

  1. Appel Explicity inlinede GHC.Extsdans fcTest.
  2. Supprimez la Factored m Intcontrainte sur plusFastCyc.

L'option 1 n'est pas satisfaisante car la base de code réelle plusFastCycest une opération fréquemment utilisée et une très grande fonction, elle ne doit donc pas être intégrée à chaque utilisation. Au contraire, GHC devrait appeler une version spécialisée de plusFastCyc. L'option 2 n'est pas vraiment une option car j'ai besoin de la contrainte dans le code réel.

J'ai essayé une variété d'options en utilisant (et non à l' aide) INLINE, INLINABLEet SPECIALIZE, mais rien ne semble fonctionner. ( EDIT : j'ai peut-être trop supprimé plusFastCycpour rendre mon exemple petit, donc cela INLINEpourrait entraîner l'inclusion de la fonction. Cela ne se produit pas dans mon vrai code car il plusFastCycest si grand.) Dans cet exemple particulier, je ne suis pas obtenir des avertissements match_co: needs more casesou RULE: LHS too complicated to desugar(et ici ), même si je recevais de nombreux match_coavertissements avant de minimiser l'exemple. Vraisemblablement, le «problème» est la Factored m Intcontrainte de la règle; si j'apporte des modifications à cette contrainte, fcTests'exécute aussi vite que vtTest.

Est-ce que je fais quelque chose que GHC n'aime tout simplement pas? Pourquoi GHC ne se spécialise-t-il pas plusFastCycet comment puis-je le faire?

METTRE À JOUR

Le problème persiste dans GHC 7.8.2, donc cette question est toujours d'actualité.

crockeea
la source
3
J'ai juste essayé de me spécialiser dans un domaine spécifique m , à savoir M. Cela a fait le travail, mais je ne peux pas me spécialiser pour des types fantômes spécifiques dans le programme réel car ils sont réifiés.
crockeea
J'ai également soumis un rapport de bogue GHC ghc.haskell.org/trac/ghc/ticket/8668 mais le problème est toujours ouvert. Le processus de rapport de bogue m'a aidé à clarifier un peu la question, donc j'espère qu'il sera plus facile de comprendre ce qui se passe.
crockeea
@monojohnny Désolé d'entendre cela, je pense que vous pouvez le signaler comme tel. Je pense que je demande à GHC de faire quelque chose d'assez raisonnable, et il ne le fera pas. Je ne sais pas si je le fais mal ou s'il s'agit d'une idiosyncrasie avec le compilateur qui pourrait avoir une solution de contournement. J'ai vu des solutions de contournement pour la spécialisation et les règles dans une bibliothèque spécifique sur le piratage qui m'échappe pour le moment, alors j'espère que quelqu'un dans la communauté avec plus d'expérience GHC que moi pourrait savoir comment se spécialiser.
crockeea
1
Je m'excuse pour le ton de mon commentaire - ce n'est pas ma meilleure contribution à ce site - il n'y a vraiment rien de mal avec votre message (c'est mon manque de compréhension qui a été la source de mon ennui je suppose!)
monojohnny
@monojohnny Excuses acceptées, mais c'est dommage que le vote négatif soit verrouillé maintenant ;-)
crockeea

Réponses:

5

GHC donne également une option à SPECIALIZEune déclaration d'instance de classe de type. J'ai essayé cela avec le code (développé) de Foo.hs, en mettant ce qui suit:

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

Ce changement, cependant, n'a pas atteint l'accélération souhaitée. Ce qui a permis d'améliorer les performances a été d' ajouter manuellement une instance spécialisée pour le type VT U.Vector m Intavec les mêmes définitions de fonction, comme suit:

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

Cela nécessite l' ajout OverlappingInstanceset FlexibleInstancesdans LANGUAGE.

Fait intéressant, dans le programme d'exemple, l'accélération obtenue avec l'instance qui se chevauche reste même si vous supprimez tous les SPECIALIZEet INLINABLEpragma.

Diego E. Alonso-Blas
la source
Certainement pas optimale, mais c'est la première solution qui atteint réellement l'objectif, donc je suppose que je vais la prendre pour l'instant ...
crockeea