Transitivité de l'auto-spécialisation en GHC

392

De la documentation pour GHC 7.6:

[V] ous n'avez souvent même pas besoin du pragma SPECIALIZE en premier lieu. Lors de la compilation d'un module M, l'optimiseur de GHC (avec -O) considère automatiquement chaque fonction surchargée de niveau supérieur déclarée dans M, et la spécialise pour les différents types auxquels il est appelé dans M. L'optimiseur considère également chaque fonction surchargée INLINABLE importée, et le spécialise pour les différents types auxquels il est appelé en M.

et

De plus, étant donné un pragma SPECIALIZE pour une fonction f, GHC créera automatiquement des spécialisations pour toutes les fonctions surchargées de classe de type appelées par f, si elles sont dans le même module que le pragma SPECIALIZE, ou si elles sont INLINABLE; et ainsi de suite, de manière transitoire.

Ainsi, GHC devrait spécialiser automatiquement certaines fonctions / la plupart / toutes (?) Marquées INLINABLE sans pragma, et si j'utilise un pragma explicite, la spécialisation est transitive. Ma question est: l' auto- spécialisation est- elle transitive?

Plus précisément, voici un petit exemple:

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 spécialise l'appel à plus, mais ne se spécialise pas(+) dans l' Qux Numinstance qui tue les performances.

Cependant, un pragma explicite

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

se traduit par une spécialisation transitive comme l'indiquent les documents, il (+)est donc spécialisé et le code est 30 fois plus rapide (tous deux compilés avec -O2). Est-ce un comportement attendu? Dois-je seulement m'attendre (+)à être spécialisé de manière transitoire avec un pragma explicite?


MISE À JOUR

Les documents pour 7.8.2 n'ont pas changé, et le comportement est le même, donc cette question est toujours d'actualité.

crockeea
la source
33
Je ne connais pas la réponse, mais il semble que cela pourrait être lié à: ghc.haskell.org/trac/ghc/ticket/5928 Cela vaut probablement la peine d'ouvrir un nouveau ticket ou d'y ajouter vos informations si vous pensez que cela est probablement lié au 5928
jberryman
6
@jberryman Il semble y avoir deux différences entre ce ticket et ma question: 1) Dans le ticket, l'équivalent de plusn'était pas marqué comme INLINABLE et 2) simonpj a indiqué qu'il y avait un certain alignement en cours avec le code du ticket, mais le noyau de mon exemple montre qu'aucune des fonctions n'était en ligne (en particulier, je ne pouvais pas me débarrasser du deuxième Fooconstructeur, sinon les choses en ligne de GHC).
crockeea
5
Ah ok. Que se passe-t-il lorsque vous définissez plus (Bar v1) = \(Bar v2)-> Bar $ v1 + v2, afin que le LHS soit pleinement appliqué sur le site d'appel? Est-il aligné puis la spécialisation se déclenche-t-elle?
jberryman
3
@jberryman Drôle, vous devriez demander. J'ai été sur cette voie avec cette question qui a conduit à ce rapport Trac . Au départ, j'avais l'appel à plusappliquer pleinement en raison de ces liens, mais en fait j'ai eu moins de spécialisation: l'appel à plusn'était pas spécialisé non plus. Je n'ai aucune explication à cela, mais j'avais l'intention de le laisser pour une autre question, ou j'espère que cela sera résolu dans une réponse à celle-ci.
crockeea
11
De ghc.haskell.org/trac/ghc/wiki/ReportABug : "En cas de doute, signalez simplement votre bug." Vous ne devriez pas vous sentir mal, d'autant plus qu'un nombre suffisant de haskellers vraiment expérimentés ici ne savent pas comment répondre à votre question. Des cas de test comme celui-ci sont probablement très utiles pour les développeurs GHC. De toute façon bonne chance! Mise à jour de la question si vous déposez un ticket
jberryman

Réponses:

4

Réponses courtes:

Si je comprends bien, les points clés de la question sont les suivants:

  • "L'auto-spécialisation est-elle transitive?"
  • Dois-je seulement m'attendre à ce que (+) soit spécialisé de manière transitoire avec un pragma explicite?
  • (apparemment prévu) Est-ce un bug de GHC? Est-ce incompatible avec la documentation?

AFAIK, les réponses sont non, surtout oui mais il y a d'autres moyens, et non.

L'intégration de code et la spécialisation d'application de type est un compromis entre la vitesse (temps d'exécution) et la taille du code. Le niveau par défaut obtient une certaine vitesse sans gonfler le code. Le choix d'un niveau plus exhaustif est laissé à la discrétion du programmeur via SPECIALISEpragma.

Explication:

L'optimiseur considère également chaque fonction surchargée INLINABLE importée et la spécialise pour les différents types auxquels elle est appelée en M.

Supposons que fsoit une fonction dont le type inclut une variable de type acontrainte par une classe de type C a. GHC se spécialise par défaut en ce fqui concerne une application de type (en remplacement ade t) si elle fest appelée avec cette application de type dans le code source de (a) n'importe quelle fonction du même module, ou (b) si elle fest marquée INLINABLE, alors tout autre module qui importe f de B. Ainsi, l'auto-spécialisation n'est pas transitive, elle ne touche que les INLINABLEfonctions importées et demandées dans le code source de A.

Dans votre exemple, si vous réécrivez l'instance Numcomme suit:

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

quxAdd (Qux x) (Qux y) = Qux $ U.zipWith (+) x y
  • quxAddn'est pas spécifiquement importé par Main. Mainimporte le dictionnaire d'instances de Num (Qux Int), et ce dictionnaire contient quxAdddans l'enregistrement de (+). Cependant, bien que le dictionnaire soit importé, le contenu utilisé dans le dictionnaire ne l'est pas.
  • plusn'appelle pas quxAdd, il utilise la fonction stockée pour l' (+)enregistrement dans le dictionnaire d'instances de Num t. Ce dictionnaire est défini sur le site d'appel (en Main) par le compilateur.
Diego E. Alonso-Blas
la source