Skip to content

Quelles optimisations peut-on attendre de GHC qu'il effectue de manière fiable ?

Bonjour, nous avons trouvé la solution à votre question, glissez et vous l'aurez un peu plus bas.

Solution :

Cette page du Trac GHC explique également assez bien les passes. Cette page explique l'ordonnancement des optimisations, bien que, comme la majorité du Wiki Trac, elle soit périmée.

Pour les spécificités, la meilleure chose à faire est probablement de regarder comment un programme spécifique est compilé. La meilleure façon de voir quelles optimisations sont effectuées est de compiler le programme de manière verbale, en utilisant la commande -v le drapeau -v. En prenant comme exemple le premier morceau de Haskell que j'ai pu trouver sur mon ordinateur :

Glasgow Haskell Compiler, Version 7.4.2, stage 2 booted by GHC version 7.4.1
Using binary package database: /usr/lib/ghc-7.4.2/package.conf.d/package.cache
wired-in package ghc-prim mapped to ghc-prim-0.2.0.0-7d3c2c69a5e8257a04b2c679c40e2fa7
wired-in package integer-gmp mapped to integer-gmp-0.4.0.0-af3a28fdc4138858e0c7c5ecc2a64f43
wired-in package base mapped to base-4.5.1.0-6e4c9bdc36eeb9121f27ccbbcb62e3f3
wired-in package rts mapped to builtin_rts
wired-in package template-haskell mapped to template-haskell-2.7.0.0-2bd128e15c2d50997ec26a1eaf8b23bf
wired-in package dph-seq not found.
wired-in package dph-par not found.
Hsc static flags: -static
*** Chasing dependencies:
Chasing modules from: *SleepSort.hs
Stable obj: [Main]
Stable BCO: []
Ready for upsweep
  [NONREC
      ModSummary {
         ms_hs_date = Tue Oct 18 22:22:11 CDT 2011
         ms_mod = main:Main,
         ms_textual_imps = [import (implicit) Prelude, import Control.Monad,
                            import Control.Concurrent, import System.Environment]
         ms_srcimps = []
      }]
*** Deleting temp files:
Deleting: 
compile: input file SleepSort.hs
Created temporary directory: /tmp/ghc4784_0
*** Checking old interface for main:Main:
[1 of 1] Compiling Main             ( SleepSort.hs, SleepSort.o )
*** Parser:
*** Renamer/typechecker:
*** Desugar:
Result size of Desugar (after optimization) = 79
*** Simplifier:
Result size of Simplifier iteration=1 = 87
Result size of Simplifier iteration=2 = 93
Result size of Simplifier iteration=3 = 83
Result size of Simplifier = 83
*** Specialise:
Result size of Specialise = 83
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = False}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = False}) = 95
*** Float inwards:
Result size of Float inwards = 95
*** Simplifier:
Result size of Simplifier iteration=1 = 253
Result size of Simplifier iteration=2 = 229
Result size of Simplifier = 229
*** Simplifier:
Result size of Simplifier iteration=1 = 218
Result size of Simplifier = 218
*** Simplifier:
Result size of Simplifier iteration=1 = 283
Result size of Simplifier iteration=2 = 226
Result size of Simplifier iteration=3 = 202
Result size of Simplifier = 202
*** Demand analysis:
Result size of Demand analysis = 202
*** Worker Wrapper binds:
Result size of Worker Wrapper binds = 202
*** Simplifier:
Result size of Simplifier = 202
*** Float out(FOS {Lam = Just 0, Consts = True, PAPs = True}):
Result size of Float out(FOS {Lam = Just 0,
                              Consts = True,
                              PAPs = True}) = 210
*** Common sub-expression:
Result size of Common sub-expression = 210
*** Float inwards:
Result size of Float inwards = 210
*** Liberate case:
Result size of Liberate case = 210
*** Simplifier:
Result size of Simplifier iteration=1 = 206
Result size of Simplifier = 206
*** SpecConstr:
Result size of SpecConstr = 206
*** Simplifier:
Result size of Simplifier = 206
*** Tidy Core:
Result size of Tidy Core = 206
writeBinIface: 4 Names
writeBinIface: 28 dict entries
*** CorePrep:
Result size of CorePrep = 224
*** Stg2Stg:
*** CodeGen:
*** CodeOutput:
*** Assembler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-I.' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' 'SleepSort.o'
Upsweep completely successful.
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_0.c /tmp/ghc4784_0/ghc4784_0.s
Warning: deleting non-existent /tmp/ghc4784_0/ghc4784_0.c
link: linkables are ...
LinkableM (Sat Sep 29 20:21:02 CDT 2012) main:Main
   [DotO SleepSort.o]
Linking SleepSort ...
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.c' '-o' '/tmp/ghc4784_0/ghc4784_0.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** C Compiler:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-c' '/tmp/ghc4784_0/ghc4784_0.s' '-o' '/tmp/ghc4784_0/ghc4784_1.o' '-DTABLES_NEXT_TO_CODE' '-I/usr/lib/ghc-7.4.2/include'
*** Linker:
'/usr/bin/gcc' '-fno-stack-protector' '-Wl,--hash-size=31' '-Wl,--reduce-memory-overheads' '-o' 'SleepSort' 'SleepSort.o' '-L/usr/lib/ghc-7.4.2/base-4.5.1.0' '-L/usr/lib/ghc-7.4.2/integer-gmp-0.4.0.0' '-L/usr/lib/ghc-7.4.2/ghc-prim-0.2.0.0' '-L/usr/lib/ghc-7.4.2' '/tmp/ghc4784_0/ghc4784_0.o' '/tmp/ghc4784_0/ghc4784_1.o' '-lHSbase-4.5.1.0' '-lHSinteger-gmp-0.4.0.0' '-lgmp' '-lHSghc-prim-0.2.0.0' '-lHSrts' '-lm' '-lrt' '-ldl' '-u' 'ghczmprim_GHCziTypes_Izh_static_info' '-u' 'ghczmprim_GHCziTypes_Czh_static_info' '-u' 'ghczmprim_GHCziTypes_Fzh_static_info' '-u' 'ghczmprim_GHCziTypes_Dzh_static_info' '-u' 'base_GHCziPtr_Ptr_static_info' '-u' 'base_GHCziWord_Wzh_static_info' '-u' 'base_GHCziInt_I8zh_static_info' '-u' 'base_GHCziInt_I16zh_static_info' '-u' 'base_GHCziInt_I32zh_static_info' '-u' 'base_GHCziInt_I64zh_static_info' '-u' 'base_GHCziWord_W8zh_static_info' '-u' 'base_GHCziWord_W16zh_static_info' '-u' 'base_GHCziWord_W32zh_static_info' '-u' 'base_GHCziWord_W64zh_static_info' '-u' 'base_GHCziStable_StablePtr_static_info' '-u' 'ghczmprim_GHCziTypes_Izh_con_info' '-u' 'ghczmprim_GHCziTypes_Czh_con_info' '-u' 'ghczmprim_GHCziTypes_Fzh_con_info' '-u' 'ghczmprim_GHCziTypes_Dzh_con_info' '-u' 'base_GHCziPtr_Ptr_con_info' '-u' 'base_GHCziPtr_FunPtr_con_info' '-u' 'base_GHCziStable_StablePtr_con_info' '-u' 'ghczmprim_GHCziTypes_False_closure' '-u' 'ghczmprim_GHCziTypes_True_closure' '-u' 'base_GHCziPack_unpackCString_closure' '-u' 'base_GHCziIOziException_stackOverflow_closure' '-u' 'base_GHCziIOziException_heapOverflow_closure' '-u' 'base_ControlziExceptionziBase_nonTermination_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnMVar_closure' '-u' 'base_GHCziIOziException_blockedIndefinitelyOnSTM_closure' '-u' 'base_ControlziExceptionziBase_nestedAtomically_closure' '-u' 'base_GHCziWeak_runFinalizzerBatch_closure' '-u' 'base_GHCziTopHandler_flushStdHandles_closure' '-u' 'base_GHCziTopHandler_runIO_closure' '-u' 'base_GHCziTopHandler_runNonIO_closure' '-u' 'base_GHCziConcziIO_ensureIOManagerIsRunning_closure' '-u' 'base_GHCziConcziSync_runSparks_closure' '-u' 'base_GHCziConcziSignal_runHandlers_closure'
link: done
*** Deleting temp files:
Deleting: /tmp/ghc4784_0/ghc4784_1.o /tmp/ghc4784_0/ghc4784_0.s /tmp/ghc4784_0/ghc4784_0.o /tmp/ghc4784_0/ghc4784_0.c
*** Deleting temp dirs:
Deleting: /tmp/ghc4784_0

En regardant à partir du premier *** Simplifier: à la dernière, où toutes les phases d'optimisation se produisent, on voit pas mal de choses.

Tout d'abord, le simplificateur fonctionne entre presque toutes les phases. Cela rend l'écriture de nombreuses passes beaucoup plus facile. Par exemple, lors de la mise en œuvre de nombreuses optimisations, ils créent simplement des règles de réécriture pour propager les changements au lieu de devoir le faire manuellement. Le simplificateur englobe un certain nombre d'optimisations simples, notamment l'inlining et la fusion. La principale limitation de ceci que je connais est que GHC refuse d'inliner les fonctions récursives, et que les choses doivent être nommées correctement pour que la fusion fonctionne.

Ensuite, nous voyons une liste complète de toutes les optimisations effectuées :

  • Spécialiser

    L'idée de base de la spécialisation est de supprimer le polymorphisme et la surcharge en identifiant les endroits où la fonction est appelée et en créant des versions de la fonction qui ne sont pas polymorphes - elles sont spécifiques aux types avec lesquels elles sont appelées. Vous pouvez également demander au compilateur de le faire avec l'option SPECIALISE pragma. À titre d'exemple, prenons une fonction factorielle :

    fac :: (Num a, Eq a) => a -> a
    fac 0 = 1
    fac n = n * fac (n - 1)
    

    Comme le compilateur ne connaît aucune propriété de la multiplication qui va être utilisée, il ne peut absolument pas l'optimiser. En revanche, s'il voit qu'elle est utilisée sur un programme de type Int, il peut maintenant créer une nouvelle version, ne différant que par le type :

    fac_Int :: Int -> Int
    fac_Int 0 = 1
    fac_Int n = n * fac_Int (n - 1)
    

    Ensuite, les règles mentionnées ci-dessous peuvent se déclencher, et vous vous retrouvez avec quelque chose qui fonctionne sur unboxed Intqui est beaucoup plus rapide que l'original. Une autre façon de voir la spécialisation est l'application partielle sur les dictionnaires de classe de type et les variables de type.

    La source ici a une charge de notes en elle.

  • Sortie du flotteur

    EDIT : J'ai apparemment mal compris ceci avant. Mon explication a complètement changé.

    L'idée de base de ceci est de déplacer les calculs qui ne devraient pas être répétés hors des fonctions. Par exemple, supposons que nous ayons ceci :

    x -> let y = expensive in x+y
    

    Dans le lambda ci-dessus, à chaque fois que la fonction est appelée, y est recalculé. Une meilleure fonction, qui flotte produit, est

    let y = expensive in x -> x+y
    

    Pour faciliter le processus, d'autres transformations peuvent être appliquées. Par exemple, ceci se produit :

     x -> x + f 2
     x -> x + let f_2 = f 2 in f_2
     x -> let f_2 = f 2 in x + f_2
     let f_2 = f 2 in x -> x + f_2
    

    Encore une fois, le calcul répété est économisé.

    La source est très lisible dans ce cas.

    Pour le moment, les liaisons entre deux lambdas adjacentes ne sont pas flottantes. Par exemple, cela ne se produit pas :

    x y -> let t = x+x in ...
    

    allant à

     x -> let t = x+x in y -> ...
    
  • Flotter vers l'intérieur

    En citant le code source,

    Le but principal de floatInwards est de flotter dans les branches d'un cas, afin de ne pas allouer des choses, les enregistrer sur la pile, et ensuite découvrir qu'elles ne sont pas nécessaires dans la branche choisie.

    A titre d'exemple, supposons que nous ayons cette expression :

    let x = big in
        case v of
            True -> x + 1
            False -> 0
    

    Si v est évalué à Falsealors en allouant xqui est vraisemblablement un gros thunk, nous avons perdu du temps et de l'espace. Le flottement vers l'intérieur corrige cela, produisant ceci :

    case v of
        True -> let x = big in x + 1
        False -> let x = big in 0
    

    qui est ensuite remplacé par le simplificateur par

    case v of
        True -> big + 1
        False -> 0
    

    Cet article, bien que couvrant d'autres sujets, donne une introduction assez claire. Notez que malgré leurs noms, le flottement vers l'intérieur et le flottement vers l'extérieur n'aboutissent pas à une boucle infinie pour deux raisons :

    1. Le flottement en entrée laisse dans case déclarations, tandis que le float out traite des fonctions.
    2. Il y a un ordre fixe de passage, donc ils ne devraient pas alterner à l'infini.
  • Analyse de la demande

    L'analyse de la demande, ou analyse de la rigueur est moins une transformation et plus, comme son nom l'indique, une passe de collecte d'informations. Le compilateur trouve les fonctions qui évaluent toujours leurs arguments (ou au moins certains d'entre eux), et passe ces arguments en utilisant le call-by-value, au lieu du call-by-need. Comme vous pouvez éviter les frais généraux des thunks, cette méthode est souvent beaucoup plus rapide. De nombreux problèmes de performance en Haskell proviennent soit de l'échec de ce passage, soit d'un code qui n'est tout simplement pas assez strict. Un exemple simple est la différence entre l'utilisation de foldr, foldlet foldl' pour additionner une liste d'entiers - le premier provoque un débordement de pile, le second un débordement de tas, et le dernier fonctionne bien, en raison de la rigueur. C'est probablement le plus facile à comprendre et le mieux documenté de tous. Je crois que le polymorphisme et le code CPS défient souvent cela.

  • Le Worker Wrapper lie

    L'idée de base de la transformation worker/wrapper est de faire une boucle serrée sur une structure simple, en convertissant vers et depuis cette structure aux extrémités. Par exemple, prenez cette fonction, qui calcule la factorielle d'un nombre.

    factorial :: Int -> Int
    factorial 0 = 1
    factorial n = n * factorial (n - 1)
    

    En utilisant la définition de Int dans GHC, nous avons

    factorial :: Int -> Int
    factorial (I# 0#) = I# 1#
    factorial (I# n#) = I# (n# *# case factorial (I# (n# -# 1#)) of
        I# down# -> down#)
    

    Remarquez comment le code est couvert dans I#s ? Nous pouvons les supprimer en faisant ceci :

    factorial :: Int -> Int
    factorial (I# n#) = I# (factorial# n#)
    
    factorial# :: Int# -> Int#
    factorial# 0# = 1#
    factorial# n# = n# *# factorial# (n# -# 1#)
    

    Bien que cet exemple spécifique aurait également pu être fait par SpecConstr, la transformation worker/wrapper est très générale dans les choses qu'elle peut faire.

  • Sous-expression commune

    C'est une autre optimisation vraiment simple qui est très efficace, comme l'analyse de la rigueur. L'idée de base est que si vous avez deux expressions qui sont les mêmes, elles auront la même valeur. Par exemple, si fib est un calculateur de nombre de Fibonacci, CSE transformera

    fib x + fib x
    

    en

    let fib_x = fib x in fib_x + fib_x
    

    ce qui réduit le calcul de moitié. Malheureusement, cela peut parfois gêner d'autres optimisations. Un autre problème est que les deux expressions doivent être au même endroit et qu'elles doivent être... syntaxiquement identiques, mais pas identiques par valeur. Par exemple, le CSE ne se déclenchera pas dans le code suivant sans un tas d'inlining :

    x = (1 + (2 + 3)) + ((1 + 2) + 3)
    y = f x
    z = g (f x) y
    

    Cependant, si vous compilez via llvm, vous pouvez obtenir une partie de ce combiné, en raison de sa passe de numérotation globale des valeurs.

  • Libérer le cas

    Cela semble être une transformation terriblement documentée, outre le fait qu'elle peut provoquer une explosion du code. Voici une version reformatée (et légèrement réécrite) de la petite documentation que j'ai trouvée :

    Ce module marche sur Coreet cherche case sur les variables libres. Le critère est le suivant : s'il existe un case sur une variable libre sur le chemin de l'appel récursif, alors l'appel récursif est remplacé par un dépliage. Par exemple, dans

    f =  t -> case v of V a b -> a : f t
    

    l'appel interne f est remplacé. pour faire

    f =  t -> case v of V a b -> a : (letrec f =  t -> case v of V a b -> a : f t in f) t
    

    Notez la nécessité de l'ombrage. En simplifiant, on obtient

    f =  t -> case v of V a b -> a : (letrec f =  t -> a : f t in f t)
    

    C'est un meilleur code, car a est libre à l'intérieur du letrecinterne, plutôt que de nécessiter une projection de v. Notez que cela concerne variables libres, contrairement à SpecConstr, qui traite des arguments qui sont de forme connue.

    Voir ci-dessous pour plus d'informations sur SpecConstr.

  • SpecConstr - cela transforme les programmes tels que

    f (Left x) y = somthingComplicated1
    f (Right x) y = somethingComplicated2
    

    en

    f_Left x y = somethingComplicated1
    f_Right x y = somethingComplicated2
    
    {-# INLINE f #-}
    f (Left x) = f_Left x
    f (Right x) = f_Right x
    

    Comme exemple étendu, prenez cette définition de last:

    last [] = error "last: empty list"
    last (x:[]) = x
    last (x:x2:xs) = last (x2:xs)
    

    Nous la transformons d'abord en

    last_nil = error "last: empty list"
    last_cons x [] = x
    last_cons x (x2:xs) = last (x2:xs)
    
    {-# INLINE last #-}
    last [] = last_nil
    last (x : xs) = last_cons x xs
    

    Ensuite, le simplificateur s'exécute, et nous avons

    last_nil = error "last: empty list"
    last_cons x [] = x
    last_cons x (x2:xs) = last_cons x2 xs
    
    {-# INLINE last #-}
    last [] = last_nil
    last (x : xs) = last_cons x xs
    

    Notez que le programme est maintenant plus rapide, car nous ne sommes pas répétitivement en train de boxer et unboxer le début de la liste. Notez également que l'inlining est crucial, car il permet aux nouvelles définitions plus efficaces d'être réellement utilisées, ainsi que d'améliorer les définitions récursives.

    SpecConstr est contrôlé par un certain nombre d'heuristiques. Celles qui sont mentionnées dans l'article sont les suivantes :

    1. Les lambdas sont explicites et l'arité est... a.
    2. Le côté droit est "suffisamment petit", quelque chose contrôlé par un drapeau.
    3. La fonction est récursive, et l'appel spécialisable est utilisé dans le côté droit.
    4. Tous les arguments de la fonction sont présents.
    5. Au moins un des arguments est une application du constructeur.
    6. Cet argument fait l'objet d'une analyse de cas quelque part dans la fonction.

    Cependant, les heuristiques ont presque certainement changé. En fait, le document mentionne une sixième heuristique alternative :

    Se spécialiser sur un argument x seulement si x est seulement examinée par un caseet n'est pas transmis à une fonction ordinaire, ni renvoyé comme partie du résultat.

Il s'agit d'un très petit fichier (12 lignes) et il est donc possible qu'il n'ait pas déclenché autant d'optimisations (bien que je pense qu'il les ait toutes effectuées). Cela ne vous dit pas non plus pourquoi il a fait ces passages et pourquoi il les a mis dans cet ordre.

Paresse

Ce n'est pas une "optimisation du compilateur", mais c'est quelque chose de garanti par la spécification du langage, donc vous pouvez toujours compter sur le fait que cela se produise. Essentiellement, cela signifie que le travail n'est pas effectué jusqu'à ce que vous "fassiez quelque chose" avec le résultat. (À moins que vous ne fassiez l'une des nombreuses choses pour désactiver délibérément la paresse).

Ceci, évidemment, est un sujet entier à part entière, et SO a beaucoup de questions et de réponses à ce sujet déjà.

Dans mon expérience limitée, rendre votre code trop paresseux ou trop strict a... largement pénalités de performance plus importantes (en temps et espace) que toutes les autres choses dont je vais parler...

Analyse de la rigueur

La paresse consiste à éviter le travail sauf s'il est nécessaire. Si le compilateur peut déterminer qu'un résultat donné sera "toujours" nécessaire, alors il ne prendra pas la peine de stocker le calcul et de l'effectuer plus tard ; il l'effectuera directement, car c'est plus efficace. C'est ce qu'on appelle "l'analyse de la rigueur".

Le problème est que le compilateur ne peut pas... toujours détecter quand quelque chose pourrait être rendu strict. Parfois, vous devez donner au compilateur de petits indices. (Je ne connais pas de moyen facile de déterminer si l'analyse de la rigueur a fait ce que vous pensez qu'elle a fait, autre que de patauger dans la sortie du Core).

Inlining

Si vous appelez une fonction, et que le compilateur peut dire quelle fonction vous appelez, il peut essayer d'"inliner" cette fonction - c'est-à-dire de remplacer l'appel de fonction par une copie de la fonction elle-même. L'overhead d'un appel de fonction est généralement assez faible, mais l'inlining permet souvent d'autres optimisations qui n'auraient pas eu lieu autrement, donc l'inlining peut être une grande victoire.

Les fonctions ne sont inlined que si elles sont "suffisamment petites" (ou si vous ajoutez un pragma demandant spécifiquement l'inlining). De plus, les fonctions ne peuvent être inlined que si le compilateur peut savoir quelle fonction vous appelez. Il y a deux façons principales dont le compilateur pourrait être incapable de le dire :

  • Si la fonction que vous appelez est passée depuis un autre endroit. Par exemple, lorsque la fonction filter est compilée, vous ne pouvez pas mettre en ligne le prédicat de filtre, car c'est un argument fourni par l'utilisateur.

  • Si la fonction que vous appelez est une méthode de classe... et le compilateur ne sait pas quel type est impliqué. Par exemple, lorsque la fonction sum est compilée, le compilateur ne peut pas mettre en ligne la fonction + car la fonction

    fonctionne avec plusieurs types de nombres différents, chacun d'entre eux ayant une fonction + différente.

Dans ce dernier cas, vous pouvez utiliser la fonction {-# SPECIALIZE #-} pragma pour générer des versions d'une fonction qui sont codées en dur à un type particulier. Par exemple , {-# SPECIALIZE sum :: [Int] -> Int #-} compilerait une version de sum codée en dur pour le type Int ce qui signifie que + peut être inlined dans cette version.

Notez, cependant, que notre nouveau spécial- sum ne sera appelée que lorsque le compilateur peut dire que nous travaillons avec Int. Sinon, la fonction originale et polymorphe sum est appelée. Encore une fois, la surcharge réelle d'appel de fonction est assez faible. Ce sont les optimisations supplémentaires que l'inlining peut permettre qui sont bénéfiques.

Élimination des sous-expressions communes

Si un certain bloc de code calcule deux fois la même valeur, le compilateur peut remplacer cela par une seule instance du même calcul. Par exemple, si vous faites

(sum xs + 1) / (sum xs + 2)

alors le compilateur pourrait l'optimiser en

let s = sum xs in (s+1)/(s+2)

Vous pourriez vous attendre à ce que le compilateur toujours le fasse. Cependant, apparemment, dans certaines situations, cela peut entraîner des performances plus mauvaises, et non meilleures, donc GHC ne fait pas de toujours le faire. Franchement, je ne comprends pas vraiment les détails derrière celle-ci. Mais la ligne de fond est, si cette transformation est importante pour vous, il n'est pas difficile de le faire manuellement. (Et si ce n'est pas important, pourquoi vous en préoccuper ?).

Expressions de cas

Considérez ce qui suit :

foo (0:_ ) = "zero"
foo (1:_ ) = "one"
foo (_:xs) = foo xs
foo (  []) = "end"

Les trois premières équations vérifient toutes si la liste est non vide (entre autres choses). Mais vérifier trois fois la même chose est un gaspillage. Heureusement, il est très facile pour le compilateur d'optimiser cela en plusieurs expressions de cas imbriquées. Dans ce cas, quelque chose comme

foo xs =
  case xs of
    y:ys ->
      case y of
        0 -> "zero"
        1 -> "one"
        _ -> foo ys
    []   -> "end"

C'est un peu moins intuitif, mais plus efficace. Comme le compilateur peut facilement effectuer cette transformation, vous n'avez pas à vous en soucier. Il suffit d'écrire votre correspondance de motifs de la manière la plus intuitive possible.e; le compilateur est très bon pour réordonner et réarranger cela pour le rendre aussi rapide que possible.

Fusion

L'idiome Haskell standard pour le traitement des listes est de chaîner ensemble des fonctions qui prennent une liste et produisent une nouvelle liste. L'exemple canonique étant

map g . map f

Malheureusement, alors que la paresse garantit de sauter le travail inutile, toutes les allocations et désallocations pour la liste intermédiaire sapent les performances. La "fusion" ou "déforestation" est l'endroit où le compilateur essaie d'éliminer ces étapes intermédiaires.

Le problème est que la plupart de ces fonctions sont récursives. Sans la récursivité, ce serait un exercice élémentaire d'inlining que d'écraser toutes les fonctions en un seul gros bloc de code, de faire tourner le simplificateur dessus et de produire un code vraiment optimal sans listes intermédiaires. Mais à cause de la récursivité, cela ne fonctionnera pas.

Vous pouvez utiliser {-# RULE #-} pragmas pour résoudre certains de ces problèmes. Par exemple,

{-# RULES "map/map" forall f g xs. map f (map g xs) = map (f.g) xs #-}

Maintenant, chaque fois que GHC voit map appliqué à map, il l'écrase en un seul passage sur la liste, éliminant la liste intermédiaire.

Le problème est que cela ne fonctionne que pour map suivi de map. Il y a beaucoup d'autres possibilités - map suivi de filter, filter suivi de mapetc. Plutôt que de coder à la main une solution pour chacun d'entre eux, ce qu'on appelle la "fusion de flux" a été inventé. Il s'agit d'une astuce plus compliquée, que je ne décrirai pas ici.

En bref : Ce sont toutes des astuces d'optimisation spéciales écrites par le programmeur. GHC lui-même ne sait rien de la fusion ; tout est dans les bibliothèques de listes et autres bibliothèques de conteneurs. Donc, les optimisations qui se produisent dépendent de la façon dont vos bibliothèques de conteneurs sont écrites (ou, de façon plus réaliste, quelles bibliothèques vous choisissez d'utiliser).

Par exemple, si vous travaillez avec des tableaux Haskell '98, ne vous attendez pas à une fusion d'aucune sorte. Mais je comprends que le vector a des capacités de fusion étendues. Tout est dans les bibliothèques ; le compilateur fournit juste le fichier RULES pragma. (Qui est extrêmement puissant, d'ailleurs. En tant qu'auteur de bibliothèque, vous pouvez l'utiliser pour réécrire le code client).


Méta :

  • Je suis d'accord avec les gens qui disent "codez d'abord, profilez ensuite, optimisez ensuite".

  • Je suis également d'accord avec les personnes qui disent "il est utile d'avoir un modèle mental pour le coût d'une décision de conception donnée".

L'équilibre en toutes choses, et tout ça...

Si une liaison let v = rhs n'est utilisée qu'à un seul endroit, vous pouvez compter sur le compilateur pour l'inliner, même si rhs est grand.

L'exception (qui n'en est presque pas une dans le contexte de la question actuelle) est celle des lambdas risquant la duplication du travail. Considérez :

let v = rhs
    l = x-> v + x
in map l [1..100]

là inlining v serait dangereux parce que la seule utilisation (syntaxique) se traduirait par 99 évaluations supplémentaires de rhs. Cependant, dans ce cas, il serait très peu probable que vous vouliez l'inliner manuellement non plus. Donc, essentiellement, vous pouvez utiliser la règle :

Si vous envisagez d'inliner un nom qui n'apparaît qu'une fois, le compilateur le fera de toute façon.

Comme un corollaire heureux, l'utilisation d'une liaison let simplement pour décomposer une longue déclaration (avec l'espoir de gagner en clarté) est essentiellement libre.

Ceci vient de
community.haskell.org/~simonmar/papers/inline.pdf
qui comprend beaucoup plus d'informations sur l'inlining.

Section des critiques et des évaluations

Nous vous invitons à soutenir notre travail en publiant un commentaire ou en laissant une évaluation, nous vous en sommes reconnaissants.



Utilisez notre moteur de recherche

Ricerca
Generic filters

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée.