Spécialisation avec contraintes

Question

Je vais avoir des problèmes pour obtenir GHC spécialiser une fonction avec une contrainte de classe. J'ai un exemple minimal de mon problème ici: Foo.hs et Principal.hs. Les deux fichiers de compilation (GHC 7.6.2, ghc -O3 Main) et de l'exécuter.

NOTE: 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 j'ai mis le code dans un seul fichier ou plusieurs autres modifications mineures, GHC simplement inlines l'appel à plusFastCyc. Cela ne se produira pas dans le code réel, car plusFastCyc est trop grand pour le GHC à la volée, même quand elle est marquée INLINE. Le point est de se spécialiser à l'appel d' plusFastCyc, de ne pas l'inclure. plusFastCyc est appelée à de nombreux endroits dans le code réel, de sorte que la duplication d'une telle grande fonction ne serait pas souhaitable, même si j'ai pu la force de GHC pour le faire.

Le code de l'intérêt est l' plusFastCyc en 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

L' Main.hs le fichier dispose de deux pilotes: vtTest, qui s'exécute dans ~3 secondes, et fcTest, qui s'exécute dans ~83 secondes lorsqu'il est compilé avec-O3 à l'aide de l' forall'd la spécialisation.

Le noyau montre que, pour l' vtTest test, l'ajout du code est en cours spécialisés, Unboxed vecteurs sur Ints, etc, alors que les génériques vecteur code est utilisé pour fcTest. Sur la ligne 10, vous pouvez voir que GHC ne fait qu'écrire une version spécialisée d' plusFastCyc, par rapport à la version générique sur la ligne 167. La règle de la spécialisation est sur la ligne 225. Je crois que cette règle doit le feu sur la ligne de 270. (main6 des appels iterate main8 y, alors main8 est où plusFastCyc doit être spécialisée.)

Mon but est de faire fcTest aussi vite qu' vtTest en se spécialisant plusFastCyc. J'ai trouvé deux façons de le faire:

1. Explicitement appel inline de GHC.Exts en fcTest.
2. Supprimer l' Factored m Int contrainte sur plusFastCyc.

L'Option 1 n'est pas satisfaisante parce que dans le code de base plusFastCyc est un des plus fréquemment utilisés fonctionnement et d'une très grande fonction, de sorte qu'il ne devrait pas être incorporé à chaque utilisation. Plutôt, GHC doit appeler une version spécialisée d' plusFastCyc. L'Option 2 n'est pas vraiment une option, parce que j'ai besoin de la contrainte dans le code réel.

J'ai essayé une variété d'options à l'aide (et ne pas l'utiliser) INLINE, INLINABLE, et SPECIALIZE, mais rien ne semble fonctionner. (EDIT: j'ai peut être dépouillé trop de plusFastCyc pour prendre mon exemple, les petits, alors INLINE pourrait provoquer la fonction inline. Cela n'arrive pas dans mon vrai code, car plusFastCyc est si grande.) Dans cet exemple particulier, je ne suis pas d'obtenir l' match_co: needs more cases ou RULE: LHS too complicated to desugar (et ici) mises en garde, même si j'ai été d'obtenir beaucoup d' match_co avertissements avant d'en minimisant l'exemple. Sans doute, le "problème" est l' Factored m Int de la contrainte à la règle; si je apporter des modifications à cette contrainte, fcTest court aussi vite que vtTest.

Suis-je en train de faire quelque chose de GHC juste n'aime pas? Pourquoi ne pas GHC spécialiser l' plusFastCyc, et comment puis-je faire?

Mise à JOUR

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

Answer 1

GHC donne également une option d' SPECIALIZE d'un type de classe de l'instance de déclaration. J'ai essayé cela avec l' (élargie) du code de l' Foo.hs, en mettant les suivantes:

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, bien que, ne pas parvenir à l'accélération. Ce qui fait que l'amélioration de la performance a été manuellement l'ajout d'une instance spécialisée pour le type VT U.Vector m Int avec 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 d' OverlappingInstances et FlexibleInstances en LANGUAGE.

Il est intéressant de noter, dans le programme d'exemple, l'accélération obtenue avec le chevauchement de l'instance demeure même si vous supprimez tous les SPECIALIZE et INLINABLE pragma.