Paresse
Il ne s'agit pas d'une "optimisation du compilateur", mais d'un élément garanti par les spécifications du langage, de sorte que vous pouvez toujours compter sur sa présence. Essentiellement, cela signifie que le travail n'est pas effectué tant que vous n'avez pas "fait 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).
Il s'agit évidemment d'un sujet à part entière, qui a déjà fait l'objet de nombreuses questions et réponses de la part de SO.
Dans mon expérience limitée, rendre votre code trop paresseux ou trop strict a largement des pénalités de performance plus importantes (en temps y ) que toutes les autres choses dont je vais parler...
Analyse de la rigueur
La paresse consiste à éviter le travail à moins qu'il ne soit 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, évidemment, est que le compilateur ne peut pas toujours détecter quand quelque chose pourrait être rendu strict. Parfois, vous devez donner de petits indices au compilateur. (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 est en mesure de savoir quelle fonction vous appelez, il peut essayer de "mettre en ligne" 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 pour le compilateur d'être incapable de le faire :
-
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 du filtre, car il s'agit d'un argument fourni par l'utilisateur.
-
Si la fonction que vous appelez est une méthode de classe y le compilateur ne sait pas quel type est impliqué. Par exemple, lorsque le sum est compilée, le compilateur ne peut pas mettre en ligne la fonction + car sum fonctionne avec plusieurs types de nombres différents, chacun d'entre eux ayant une différente + fonction.
Dans ce dernier cas, vous pouvez utiliser l'option {-# SPECIALIZE #-} pragma pour générer des versions d'une fonction qui sont codées en dur pour un type particulier. Par exemple, {-# SPECIALIZE sum :: [Int] -> Int #-} compilerait une version de sum codé en dur pour le Int ce qui signifie que + peuvent ê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, l'original, polymorphe sum est appelé. Là encore, la surcharge réelle des appels de fonction est relativement 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 le remplacer 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)
On pourrait s'attendre à ce que le compilateur toujours le faire. Cependant, apparemment, dans certaines situations, cela peut entraîner une baisse des performances, et non une amélioration. toujours faire ça. Franchement, je ne comprends pas vraiment les détails de cette opération. 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 préoccupez vous ?)
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"
Cette méthode est moins intuitive, mais plus efficace. Comme le compilateur peut facilement effectuer cette transformation, vous n'avez pas à vous en soucier. Il suffit d'écrire votre filtrage de la manière la plus intuitive possible ; le compilateur est très doué pour réordonner et réarranger tout cela afin de le rendre aussi rapide que possible.
Fusion
L'idiome Haskell standard pour le traitement des listes consiste à enchaîner des fonctions qui prennent une liste et en produisent une nouvelle. L'exemple canonique étant
map g . map f
Malheureusement, si la paresse permet de sauter les tâches inutiles, 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 #-} 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 #-}
Maintenant, chaque fois que GHC voit map appliqué à map il le comprime en un seul passage sur la liste, en éliminant la liste intermédiaire.
Le problème est que cela ne fonctionne que pour map suivi par map . Il existe de nombreuses autres possibilités - map suivi par filter , filter suivi par map etc. Plutôt que de coder manuellement une solution pour chacun d'entre eux, on a inventé ce qu'on appelle la "fusion de flux". Il s'agit d'une astuce plus compliquée, que je ne décrirai pas ici.
Le long et le court de la chose est : 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 façon dont vos bibliothèques de conteneurs sont écrites (ou, de façon plus réaliste, des bibliothèques que vous choisissez d'utiliser).
Par exemple, si vous travaillez avec des tableaux Haskell '98, ne vous attendez pas à une quelconque fusion. Mais je comprends que le vector possède des capacités de fusion étendues. Tout repose sur les bibliothèques ; le compilateur ne fait que fournir la RULES pragma. (Ce qui est extrêmement puissant, soit dit en passant. En tant qu'auteur de bibliothèque, vous pouvez l'utiliser pour réécrire le code du client).
Méta :
-
Je suis d'accord avec ceux 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 du coût d'une décision de conception donnée".
L'équilibre en toutes choses, et tout ça...
12 votes
C'est une question très intéressante. Écrire une réponse valable est... délicat.
1 votes
Voici un très bon point de départ : aosabook.org/fr/ghc.html
8 votes
Dans n'importe quelle langue, si votre première pensée est "je devrais peut-être optimiser cela", votre deuxième pensée devrait être "je vais d'abord le profiler".
4 votes
Bien que le type de connaissance que vous recherchez soit utile, et donc c'est toujours une bonne question, je pense que vous êtes mieux servi en essayant de faire comme petit optimisation que possible. Écrivez ce que vous voulez dire, et seulement quand il devient évident que vous devez puis pensez à rendre le code moins simple pour des raisons de performances. Plutôt que de regarder le code et de se dire "cela va être exécuté fréquemment, je devrais peut-être l'optimiser", ce n'est que lorsque vous observez un code qui s'exécute trop lentement que vous devriez vous dire "je devrais trouver ce qui est exécuté fréquemment et l'optimiser".
14 votes
Je m'attendais à ce que cette partie appelle des exhortations à "le profiler" :). Mais je suppose que le revers de la médaille est, si je le profile et qu'il est lent, peut-être que je peux le réécrire ou juste le modifier dans une forme qui est toujours de haut niveau mais que GHC peut mieux optimiser, au lieu de l'optimiser à la main moi-même ? Ce qui requiert le même type de connaissances. Et si j'avais eu cette connaissance en premier lieu, j'aurais pu m'épargner un cycle d'édition de profil.
1 votes
J'aurais aimé que la prime soit offerte pour améliorer la réponse sur un wiki Haskell quelque part où elle a sa place et où on peut la retrouver. Cela dit, j'ai tendance à optimiser le code Haskell en faisant attention aux timings et en imaginant ce qui pourrait se passer. Je ne vois pas en quoi le fait de savoir que j'ai raison pourrait être utile, c'est le timing lui-même qui compte.