Quelles optimisations le GHC peut-il espérer effectuer de manière fiable?

GHC a beaucoup d'optimisations qu'il peut effectuer, mais je ne sais pas ce qu'ils sont tous, ni quelle est la probabilité qu'ils soient exécutés et dans quelles circonstances.

Ma question est la suivante: à quelles transformations puis-je m'attendre à ce qu'elle s'applique à chaque fois, ou presque? Si je regarde un morceau de code qui va être exécuté (évalué) fréquemment et que ma première pensée est "hmm, peut-être que je devrais l'optimiser", auquel cas ma deuxième pensée devrait être, "n'y pense même pas, GHC a compris "?

Je lisais l'article Stream Fusion: From Lists to Streams to Nothing at All , et la technique qu'ils utilisaient pour réécrire le traitement des listes sous une forme différente que les optimisations normales de GHC optimiseraient ensuite de manière fiable en de simples boucles était nouvelle pour moi. Comment puis-je savoir si mes propres programmes sont éligibles à ce type d'optimisation?

Il y a des informations dans le manuel du GHC, mais elles ne permettent qu'une partie de la réponse à la question.

EDIT: Je commence une prime. Ce que je voudrais, c'est une liste de transformations de niveau inférieur comme lambda / let / case-floating, la spécialisation d'argument de type / constructeur / fonction, l'analyse de rigueur et unboxing, worker / wrapper, et tout ce que GHC important fait que j'ai laissé de côté , avec des explications et des exemples de code d'entrée et de sortie, et idéalement des illustrations de situations où l'effet total est supérieur à la somme de ses parties. Et idéalement une mention du moment où les transformations ne seront passe produire. Je ne m'attends pas à des explications de longueur nouvelle de chaque transformation, quelques phrases et des exemples de code en ligne à une ligne pourraient suffire (ou un lien, s'il ne s'agit pas de vingt pages de papier scientifique), tant que la vue d'ensemble est clair à la fin. Je veux pouvoir regarder un morceau de code et être en mesure de faire une bonne estimation pour savoir s'il va se compiler en boucle serrée, ou pourquoi pas, ou ce que je devrais changer pour le faire. (Je ne suis pas tellement intéressé ici par les grands cadres d'optimisation comme la fusion de flux (je viens de lire un article à ce sujet); plus par le type de connaissances que les personnes qui écrivent ces cadres ont.)

Cette page GHC Trac explique également assez bien les passes. Cette page explique l'ordre d'optimisation, bien que, comme la plupart des Trac Wiki, elle est obsolète.

Pour les détails, 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 façon verbale, en utilisant l' -vindicateur. 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

À la recherche du premier *** Simplifier: à la dernière, là où toutes les phases d'optimisation se déroulent, nous en voyons beaucoup.

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 modifications au lieu d'avoir à 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'insérer des 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 dire au compilateur de le faire avec le SPECIALISEpragma. À 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 à utiliser, il ne peut pas du tout optimiser cela. Si toutefois, il voit qu'il est utilisé sur un 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 les Ints sans boîte , ce qui est beaucoup plus rapide que l'original. Une autre façon de voir la spécialisation est une application partielle sur les dictionnaires de classe de type et les variables de type.

  La source ici contient un tas de notes.

• Flotter

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

  L'idée de base 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, yest recalculée. Une meilleure fonction, que le flottement produit, est

  let y = expensive in \x -> x+y

  Pour faciliter le processus, d'autres transformations peuvent être appliquées. Par exemple, cela 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 enregistré.

  La source est très lisible dans ce cas.

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

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

  aller à

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

• Flotter vers l'intérieur

  Citant le code source,

  Le but principal de floatInwardsest de flotter dans les branches d'un cas, de sorte que nous n'allouons pas les choses, les sauvegardons sur la pile, puis découvrons qu'elles ne sont pas nécessaires dans la branche choisie.

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

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

  Si vévalue à False, alors en allouant x, ce qui est probablement un gros bruit, nous avons perdu du temps et de l'espace. Flottant vers l'intérieur corrige ce problème, 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 avec

  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, les flottants entrants et sortants ne sont pas dans une boucle infinie pour deux raisons:

  1. Float in floats laisse entrer des caseinstructions, tandis que float out traite des fonctions.
  2. Il y a un ordre fixe de passes, elles ne devraient donc pas alterner indéfiniment.

• Analyse de la demande

  L'analyse de la demande, ou analyse de rigueur, est moins une transformation et plus, comme son nom l'indique, une passe de collecte d'informations. Le compilateur trouve des fonctions qui évaluent toujours leurs arguments (ou au moins certains d'entre eux) et transmet ces arguments en utilisant l'appel par valeur, au lieu de l'appel par besoin. Puisque vous évitez les frais généraux des thunks, c'est souvent beaucoup plus rapide. De nombreux problèmes de performances dans Haskell proviennent soit de l'échec de cette réussite, soit d'un code qui n'est tout simplement pas assez strict. Un exemple simple est la différence entre l'utilisationfoldr ,foldl etfoldl'pour additionner une liste d'entiers - le premier provoque un débordement de pile, le second provoque un débordement de tas et le dernier s'exécute correctement, en raison de la rigueur. C'est probablement le plus facile à comprendre et le mieux documenté de tous ces éléments. Je crois que le polymorphisme et le code CPS vont souvent à l'encontre de cela.

• Liaisons de Worker Wrapper

  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 Intdans 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 ait également pu être réalisé par SpecConstr, la transformation worker / wrapper est très générale dans les choses qu'elle peut faire.

• Sous-expression commune

  Il s'agit d'une autre optimisation très simple et très efficace, comme l'analyse de rigueur. L'idée de base est que si vous avez deux expressions identiques, elles auront la même valeur. Par exemple, s'il fibs'agit d'un calculateur de nombres de Fibonacci, CSE transformera

  fib x + fib x

  dans

  let fib_x = fib x in fib_x + fib_x

  ce qui coupe 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, et non identiques en valeur. Par exemple, 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 ces éléments combinés, en raison de sa numérotation par valeur globale.

• Libérer le cas

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

  Ce module parcourt Coreet recherche casedes variables libres. Le critère est le suivant: s'il y a un casesur une variable libre sur la route vers 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'intérieur fest remplacé. 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 le besoin d'ombrage. Simplifier, nous obtenons

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

  C'est un meilleur code, car il aest libre à l'intérieur letrec, plutôt que d'avoir besoin d'une projection depuis v. Notez que cela concerne des variables libres , contrairement à SpecConstr, qui traite des arguments de forme connue.

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

• SpecConstr - cela transforme des programmes comme

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

  dans

  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 le 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 boxons pas et ne déballons pas à plusieurs reprises le début de la liste. Notez également que l'inlining est crucial, car il permet d'utiliser les nouvelles définitions plus efficaces, ainsi que d'améliorer les définitions récursives.

  SpecConstr est contrôlé par un certain nombre d'heuristiques. Ceux mentionnés dans l'article sont en tant que tels:

  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 la partie droite.
  4. Tous les arguments de la fonction sont présents.
  5. Au moins un des arguments est une application constructeur.
  6. Cet argument est analysé en cas de cas quelque part dans la fonction.

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

  Sur un argument Spécialisez xque si xon ne scruté par un case, et n'est pas passé à une fonction ordinaire, ou retourné dans le cadre du résultat.

C'était un très petit fichier (12 lignes) et donc peut-être n'a pas déclenché autant d'optimisations (même si je pense que cela les a toutes faites). Cela ne vous dit pas non plus pourquoi il a choisi ces laissez-passer 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 ce qu'il se produise. Essentiellement, cela signifie que le travail n'est pas effectué tant que vous n'avez pas "fait quelque chose" avec le résultat. (Sauf si vous faites une ou plusieurs choses pour désactiver délibérément la paresse.)

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

D'après mon expérience limitée, rendre votre code trop paresseux ou trop strict entraîne des pénalités de performances beaucoup plus importantes (dans le temps et dans l' espace) que toutes les autres choses dont je vais parler ...

Analyse de rigueur

La paresse consiste à éviter le travail sauf si c'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'exécuter plus tard; il l'exécutera directement, car c'est plus efficace. C'est ce qu'on appelle une «analyse de rigueur».

Le problème, évidemment, est que le compilateur ne peut pas toujours détecter quand quelque chose pourrait être rendu strict. Parfois, vous devez donner de petits conseils au compilateur. (Je ne connais aucun moyen simple de déterminer si l'analyse de rigueur a fait ce que vous pensez avoir, autre que de parcourir la sortie Core.)

Inlining

Si vous appelez une fonction, et que le compilateur peut dire quelle fonction vous appelez, il peut essayer de "incorporer" cette fonction - c'est-à-dire de remplacer l'appel de fonction par une copie de la fonction elle-même. La surcharge d'un appel de fonction est généralement assez faible, mais l'inlining permet souvent à d'autres optimisations de se produire qui ne se seraient pas produites autrement, donc l'inlining peut être une grande victoire.

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

• Si la fonction que vous appelez est transmise ailleurs. Par exemple, lorsque la filterfonction est compilée, vous ne pouvez pas insérer le prédicat de filtre, car il s'agit d'un argument fourni par l'utilisateur.

• Si la fonction que vous appelez est une méthode de classe et que le compilateur ne sait pas quel type est impliqué. Par exemple, lorsque la sumfonction est compilée, le compilateur ne peut pas intégrer la +fonction, car il sumfonctionne avec plusieurs types de nombres différents, chacun ayant une +fonction différente .

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

Notez, cependant, que notre nouvelle sumfonction spéciale ne sera appelée que lorsque le compilateur pourra dire que nous travaillons avec Int. Sinon, l'original polymorphe sumest appelé. Encore une fois, la surcharge réelle des appels 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 courantes

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

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

alors le compilateur pourrait optimiser cela pour

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

Vous pouvez vous attendre à ce que le compilateur fasse toujours cela. Cependant, apparemment dans certaines situations, cela peut entraîner des performances moins bonnes, pas meilleures, donc GHC ne le fait pas toujours . Franchement, je ne comprends pas vraiment les détails derrière celui-ci. Mais l'essentiel est que si cette transformation est importante pour vous, il n'est pas difficile de la faire manuellement. (Et si ce n'est pas important, pourquoi vous en souciez-vous?)

Expressions de cas

Considérer 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 n'est pas vide (entre autres). Mais vérifier la même chose trois fois 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 plutôt moins intuitif, mais plus efficace. Étant donné que le compilateur peut facilement effectuer cette transformation, vous n'avez pas à vous en soucier. Écrivez simplement votre correspondance de motif de la manière la plus intuitive possible; le compilateur est très bon pour réorganiser et réorganiser cela pour le rendre aussi rapide que possible.

La fusion

L'idiome standard de Haskell pour le traitement de liste est d'enchaîner les 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. «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écursion, ce serait un exercice élémentaire d'inlining pour écraser toutes les fonctions dans un gros bloc de code, exécuter le simplificateur dessus et produire un code vraiment optimal sans listes intermédiaires. Mais à cause de la récursivité, cela ne fonctionnera pas.

Vous pouvez utiliser des {-# 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 #-}

Désormais, chaque fois que GHC voit mapappliqué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 mapsuivi de map. Il existe de nombreuses autres possibilités - mapsuivies de filter, filtersuivies demap , etc. Plutôt que de coder manuellement une solution pour chacune d'elles, la soi-disant «fusion de flux» a été inventée. C'est une astuce plus compliquée, que je ne décrirai pas ici.

En résumé, 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. Ainsi, les optimisations qui se produisent dépendent de la manière dont vos bibliothèques de conteneurs sont écrites (ou, plus réaliste, des bibliothèques que vous choisissez d'utiliser).

Par exemple, si vous travaillez avec des tableaux Haskell '98, ne vous attendez à aucune fusion d'aucune sorte. Mais je comprends que la vectorbibliothèque dispose de capacités de fusion étendues. Tout tourne autour des bibliothèques; le compilateur fournit juste le RULESpragma. (Ce qui est extrêmement puissant, au fait. 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 "coder d'abord, profil deuxième, optimiser troisième".

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

Équilibre en toutes choses, et tout ça ...

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

L'exception (qui n'en est presque pas une dans le contexte de la question actuelle) est que les lambdas risquent la duplication du travail. Considérer:

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 est très peu probable que vous souhaitiez l'incrémenter manuellement. Donc, essentiellement, vous pouvez utiliser la règle:

Si vous envisagez d'insérer un nom qui n'apparaît qu'une seule fois, le compilateur le fera quand même.

En guise de corollaire heureux, utiliser une liaison let simplement pour décomposer une longue déclaration (avec l'espoir de gagner en clarté) est essentiellement gratuit.

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