178 votes

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

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

Ma question est: quelles transformations peut-on attendre d'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, je devrais peut-être optimiser qui", dans quel cas faut-ma deuxième pensée, "ne pense même pas à ce sujet, GHC eu ce"?

J'ai lu le papier Flux de Fusion: à Partir de Listes de cours d'eau, à Rien du Tout, et la technique de la réécriture de la liste de la transformation en une autre forme qui GHC est normal optimisations serait alors de manière fiable optimiser bas en simple boucle était nouveau pour moi. Comment puis-je savoir quand mon propre programme sont admissibles à ce type d'optimisation?

Il y a certaines informations dans le GHC manuel, mais il va seulement une partie du chemin vers la réponse à la question.

EDIT: je commence un bounty. Ce que je voudrais, c'est une liste de niveau inférieur transformations comme la lambda/let/cas-flottant, type/constructeur/argument de fonction de la spécialisation, la rigueur de l'analyse et de l'unboxing, travailleur/wrapper, et tout le reste importante GHC fait que j'ai laissé de côté, avec des explications et des exemples d'entrée et de sortie de code, et, idéalement, des illustrations de situations où l'effet total est plus que la somme de ses parties. Et, idéalement, de mentionner lors de transformations de ne pas se produire. Je ne suis pas attendre roman-longueur des explications de chaque transformation, un couple de phrases et inline one-liner exemples de code pourrait être assez (ou un lien, si ce n'est pas à une vingtaine de pages de document scientifique), tant que le tableau d'ensemble est claire par la fin de celui-ci. Je veux être en mesure de regarder un morceau de code et d'être en mesure de faire une bonne estimation sur la question de savoir si elle va compiler vers le bas pour une boucle serrée, ou pourquoi pas, ou ce que j'aurais à faire des changements. (Je ne m'intéresse pas tellement ici, dans la grande optimisation des infrastructures comme flux de fusion (je viens de lire un article sur ce sujet); de plus, dans le genre de connaissances que les personnes qui écrivent ces cadres ont.)

64voto

MathematicalOrchid Points 15354

La paresse

Ce n'est pas un "compilateur" optimisation, mais c'est quelque chose garantis par la spécification du langage, de sorte que vous pouvez toujours compter sur elle passe. Essentiellement, cela signifie que le travail n'est pas effectué jusqu'à ce que vous "faire quelque chose" avec le résultat. (Sauf si vous faites plusieurs choses à délibérément désactiver la paresse.)

Cela, évidemment, est l'ensemble d'un sujet dans son propre droit, et a DONC beaucoup de questions et de réponses à ce sujet déjà.

Dans mon expérience limitée, ce qui rend votre code trop paresseux ou trop stricts a considérablement plus large de la performance des sanctions (dans le temps et l'espace) que toutes les autres choses que je suis sur le point de parler...

La rigueur de l'analyse

La paresse est d'éviter de travailler sauf si c'est nécessaire. Si le compilateur peut déterminer qu'un résultat donné "toujours" être nécessaire, alors il ne sera pas pris la peine de ranger le calcul et l'exécution plus tard, il va juste l'exécuter directement, parce que c'est plus efficace. C'est ce qu'on appelle "la rigueur de l'analyse".

La chasse aux sorcières, de toute évidence, c'est que le compilateur ne peut pas toujours détecter le moment où quelque chose pourrait être faite stricte. Parfois, vous avez besoin pour donner le compilateur peu de conseils. (Je ne suis pas au courant de tout moyen facile de déterminer si la rigueur de l'analyse a fait ce que vous pensez qu'il a, autres que de patauger dans le Cœur de sortie.)

Inline

Si vous appelez une fonction, et le compilateur peut dire quelle est la fonction que vous l'appelez, il peut essayer de "inline", que la fonction qui est, pour remplacer l'appel de la fonction avec une copie de la fonction elle-même. La surcharge d'un appel de fonction est généralement assez petites, mais inline permet souvent d'autres optimisations pour produire qui ne serait pas arrivé le contraire, si l'in-lining peut être une grande victoire.

Les fonctions ne sont inline si ils sont "assez petit" (ou si vous ajoutez un pragma demandant explicitement pour inline). Aussi, les fonctions ne peuvent être inline si le compilateur ne peut pas savoir quelle est la fonction que vous appelez. Il y a deux façons principales que le compilateur pourrait être incapable de dire:

  • Si la fonction que vous appelez est transmis à partir de quelque part d'autre. E. g., lorsque l' filter fonction est compilé, vous ne pouvez pas insérer le prédicat de filtre, parce que c'est l'utilisateur a fourni l'argument.

  • Si la fonction que vous appelez est une méthode de la classe et le compilateur ne sait pas de quel type est impliqué. E. g., lorsque l' sum fonction est compilé, le compilateur ne peut pas inline l' + de la fonction, parce qu' sum travaille avec plusieurs différents types de numéro, dont chacune est différente + fonction.

Dans ce dernier cas, vous pouvez utiliser l' {-# SPECIALIZE #-} pragma pour générer des versions de fonction qui sont codés en dur pour un type particulier. E. g., {-# SPECIALIZE sum :: [Int] -> Int #-} serait de compiler une version de sum codées en dur pour l' Int type, ce qui signifie qu' + peuvent être intégrées dans cette version.

Notez, cependant, que notre nouveau hors-sum fonction ne sera appelée lorsque le compilateur ne peut pas savoir que nous travaillons avec Int. Sinon l'original, polymorphe sum est appelée. Ici encore, l'appel de fonction, les frais généraux est assez petite. C'est le supplémentaire des optimisations qui inline pouvez activer qui sont bénéfiques.

L'élimination des sous-expressions redondantes

Si un certain bloc de code calcule la même valeur à deux reprises, le compilateur peut remplacer qu'avec une seule instance de la même calcul. Par exemple, si vous ne

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

ensuite, le compilateur peut optimiser ce

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

Vous pourriez penser que le compilateur aurait toujours le faire. Cependant, apparemment, dans certaines situations, cela peut entraîner une dégradation des performances, pas mieux, donc GHC n'est pas toujours le faire. Franchement, je ne comprends pas vraiment les détails derrière celui-ci. Mais la ligne du bas est, si cette transformation est important pour vous, il n'est pas difficile de le faire manuellement. (Et si ce n'est pas important, pourquoi vous inquiéter?)

Cas des expressions

Considérez les points suivants:

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

Les trois premières équations de vérifier si la liste est non-vide (entre autres choses). Mais la vérification de la même chose trois fois, c'est du gaspillage. Heureusement, il est très facile pour le compilateur d'optimiser ce dans plusieurs imbriquée cas des expressions. 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 beaucoup moins intuitif, mais plus efficace. Parce que le compilateur peut facilement faire cette transformation, vous n'avez pas à vous inquiéter à ce sujet. Il suffit d'écrire votre pattern matching dans la manière la plus intuitive possible; le compilateur est très bon à la réorganisation et de réorganiser ce pour le rendre aussi vite que possible.

La Fusion

La norme Haskell, un langage pour le traitement de liste est pour la chaîne d'ensemble des fonctions qui prennent un liste et de produire une nouvelle liste. L'exemple canonique étant

map g . map f

Malheureusement, alors que la paresse des garanties de sauter élément de travail, toutes les allocations et deallocations par l'intermédiaire de la liste de sap performance. "Fusion" ou "déforestation" est l'endroit où le compilateur essaie d'éliminer ces étapes intermédiaires.

Le problème est, la plupart de ces fonctions sont récursives. Sans la récursivité, il serait un élémentaire de l'exercice en inline pour écraser toutes les fonctions dans un seul gros bloc de code, exécutez la simplifier et produire un code optimal sans aucun intermédiaire des listes. Mais à cause de la récursivité, qui ne fonctionne pas.

Vous pouvez utiliser {-# RULE #-} pragmas de résoudre certains de cela. 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é à l' map, il squishes en un seul passage sur la liste, en éliminant l'intermédiaire de la liste.

La difficulté est, cela ne fonctionne qu' map suivie par map. Il existe de nombreuses autres possibilités - map suivie par filter, filter suivie par map, etc. Plutôt que de la main-code une solution pour chacun d'eux, dites de "flux " fusion" a été inventé. C'est un plus compliqué astuce que je ne vais pas décrire ici.

Le long et à court de celui-ci est: Ils sont tous spéciaux optimisation des trucs écrit par le programmeur. GHC lui-même ne sait rien à propos de la fusion; tout est dans la liste de la bibliothèque et d'autres contenant des bibliothèques. Donc, ce que optimisations cela dépend comment votre conteneur des bibliothèques sont écrites (ou, de façon plus réaliste, des bibliothèques que vous choisissez d'utiliser).

Par exemple, si vous travaillez avec Haskell '98 tableaux, ne pas s'attendre à une fusion de tout genre. Mais je comprends que l' vector bibliothèque possède une vaste fonctions de fusion. Il est tout au sujet des bibliothèques; le compilateur fournit simplement l' RULES pragma. (Ce qui est extrêmement puissant, par la manière. En tant que bibliothèque de l'auteur, vous pouvez l'utiliser pour réécrire le code du client!)


Meta:

  • Je suis d'accord avec les gens qui disent "le premier code, le profil de seconde, une optimisation de la troisième".

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

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

8voto

Daniel Points 41

Si une liaison let v = rhs est utilisé dans un seul endroit, vous pouvez compter sur le compilateur de l'inclure, même si le membre de droite est grand.

L'exception ("presque" n'est pas dans le contexte actuel de la question) est lambdas risquer le travail en double. Considérer:

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

il y inline v serait dangereux parce que l'un (syntaxique) utilisation de traduire en 99 supplémentaire évaluations de l'ers. Toutefois, dans ce cas, il serait très peu probable que de vouloir l'inclure manuellement. Donc, essentiellement, vous pouvez utiliser la règle:

Si vous devez envisager d'inlining un nom qui n'apparaît qu'une fois, le compilateur va le faire de toute façon.

Comme un heureux corollaire, à l'aide d'une liaison let simplement pour décomposer une longue déclaration (avec l'espoir d'obtenir plus de clarté) est essentiellement gratuit.

Cela vient de community.haskell.org/~simonmar/documents/inline.pdf qui comprend beaucoup plus d'informations à propos de l'in-lining.

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X