[Optimization] Quelles optimisations GHC peut-il réaliser de manière fiable?


Answers

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 qui se passe. 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 une de plusieurs choses pour désactiver délibérément la paresse.)

Ceci, évidemment, est un sujet entier en soi, et SO a déjà beaucoup de questions et de réponses à ce sujet.

Dans mon expérience limitée, rendre votre code trop paresseux ou trop strict a des pénalités de performance beaucoup plus grandes (dans le temps et l' espace) que n'importe quelle autre chose dont je vais parler ...

Analyse de rigueur

La paresse consiste à éviter le travail à moins que cela ne soit nécessaire. Si le compilateur peut déterminer qu'un résultat donné sera "toujours" nécessaire, il ne prendra pas la peine de stocker le calcul et de l'exécuter plus tard; ça va juste le faire directement, parce que c'est plus efficace. C'est ce que l'on appelle "l'analyse de rigueur".

Le gotcha, évidemment, est que le compilateur ne peut pas toujours détecter quand quelque chose pourrait être rendu strict. Parfois, vous devez donner quelques astuces au compilateur. (Je ne suis pas au courant d'un moyen simple de déterminer si l'analyse de rigueur a fait ce que vous pensez qu'elle a, autre que de patauger dans la sortie Core.)

Inline

Si vous appelez une fonction, et que le compilateur peut indiquer quelle fonction vous appelez, il peut essayer de "aligner" cette fonction, c'est-à-dire de remplacer l'appel de fonction par une copie de la fonction elle-même. Le surcoût 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'inline peut être une grande victoire.

Les fonctions ne sont inline que si elles sont "assez petites" (ou si vous ajoutez un pragma demandant spécifiquement l'inlining). En outre, les fonctions ne peuvent être intégrées que si le compilateur peut indiquer quelle fonction vous appelez. Il y a deux manières principales que le compilateur pourrait être incapable de dire:

  • Si la fonction que vous appelez est transmise d'ailleurs. Par exemple, lorsque la fonction de filter est compilée, vous ne pouvez pas intégrer 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 le compilateur ne sait pas quel type est impliqué. Par exemple, lorsque la fonction sum est compilée, le compilateur ne peut pas aligner la fonction + , car sum fonctionne avec plusieurs types de nombres différents, chacun ayant une fonction + différente.

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

Notez, cependant, que notre nouvelle fonction de sum spéciale ne sera appelée que lorsque le compilateur peut dire que nous travaillons avec Int . Sinon, la sum polymorphe originale est appelée. Encore une fois, l'en-tête d'appel de fonction réel est assez petit. Ce sont les optimisations supplémentaires que l'inline peut permettre qui sont bénéfiques.

Élimination commune de la sous-expression

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

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

alors le compilateur pourrait optimiser cela à

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

Vous pourriez vous attendre à ce que le compilateur le fasse toujours . 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 le faire manuellement. (Et si ce n'est pas important, pourquoi vous en inquiétez-vous?)

Les 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 est non-vide (entre autres choses). Mais vérifier la même chose trois fois est inutile. Heureusement, il est très facile pour le compilateur d'optimiser ceci 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. Parce que le compilateur peut facilement faire cette transformation, vous n'avez pas à vous en préoccuper. Il suffit d'écrire votre correspondance de motif de la manière la plus intuitive possible; le compilateur est très bon pour réorganiser et réarranger cela pour le rendre aussi rapide que possible.

La fusion

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

map g . map f

Malheureusement, alors que la paresse permet de sauter un 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 tente 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 grand bloc de code, lancer le simplificateur dessus et produire du code vraiment optimal sans listes intermédiaires. Mais à cause de la récursivité, ça ne marchera pas.

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

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

Chaque fois que GHC voit la map appliquée à la map , elle l'écrase en un seul passage sur la liste, éliminant ainsi la liste intermédiaire.

Le problème est, cela ne fonctionne que pour la map suivie par la map . Il y a beaucoup d'autres possibilités - map suivie d'un filter , filter suivi d'une map , etc. Plutôt que de coder à la main une solution pour chacun d'entre eux, on a inventé la «fusion de flux». C'est une astuce plus compliquée que je ne décrirai pas ici.

Le long et court de celui-ci est: Ce sont tous 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, quelles optimisations se produisent dépend 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 baies Haskell 98, ne vous attendez pas à une fusion quelconque. Mais je comprends que la bibliothèque de vector a des capacités de fusion étendues. Tout est dans les bibliothèques. le compilateur fournit simplement le pragma RULES. (Ce qui est extrêmement puissant, en passant .. En tant qu'auteur de bibliothèque, vous pouvez l'utiliser pour réécrire le code client!)

Meta:

  • Je suis d'accord avec les gens qui disent "code 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 déterminer le coût d'une décision de conception donnée».

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

Question

GHC a beaucoup d'optimisations qu'il peut effectuer, mais je ne sais pas ce qu'ils sont tous, ni comment ils sont susceptibles d'être effectués et dans quelles circonstances.

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

Je lisais l'article Stream Fusion: des listes aux streams à rien du tout , et la technique qu'ils utilisaient pour réécrire le traitement des listes sous une forme différente que les optimisations normales de GHC optimisaient ensuite en boucles simples était pour moi nouvelle. Comment puis-je savoir quand mes propres programmes sont éligibles à ce type d'optimisation?

Il y a quelques informations dans le manuel de GHC, mais cela ne fait qu'une partie du chemin pour répondre à 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, spécialisation de type / constructeur / fonction, analyse de rigueur et unboxing, worker / wrapper, et tout ce que GHC fait de plus significatif , avec des explications et des exemples de code d'entrée et de sortie, et idéalement des illustrations de situations lorsque l'effet total est plus que la somme de ses parties. Et idéalement une certaine mention de quand les transformations ne se produiront pas . Je ne m'attends pas à des explications inédites de chaque transformation, quelques phrases et des exemples de code en un seul interligne peuvent suffire (ou un lien, si ce n'est pas à vingt pages de document scientifique), tant que la situation clair à la fin de celui-ci. Je veux être capable de regarder un morceau de code et être capable de faire une bonne estimation pour savoir s'il va compiler vers une boucle serrée, ou pourquoi pas, ou ce que je devrais changer pour le faire. (Je ne m'intéresse pas tellement ici aux grands cadres d'optimisation comme la fusion de flux (je viens de lire un article à ce sujet), plus au genre de connaissances que les personnes qui écrivent ces frameworks ont.)




Links