Un bon texte d'introduction à l'implémentation de GHC ?

Question

Lorsque je programme en Haskell (et en particulier lorsque je résous des problèmes du Projet Euler, où les solutions sous-optimales ont tendance à stresser le CPU ou les besoins en mémoire), je me demande souvent pourquoi le programme se comporte comme il le fait. Je regarde les profils, j'essaie d'introduire une certaine rigueur, je choisis une autre structure de données, ... mais la plupart du temps, je tâtonne dans le noir, car je n'ai pas une bonne intuition.

De plus, si je sais comment Lisp, Prolog et les langages impératifs sont généralement implémentés, je n'ai aucune idée de l'implémentation d'un langage paresseux. Je suis aussi un peu curieux.

J'aimerais donc en savoir plus sur l'ensemble de la chaîne, de la source du programme au modèle d'exécution.

Des choses que je me demande :

• quelles optimisations typiques sont appliquées ?

• quel est l'ordre d'exécution lorsqu'il y a plusieurs candidats à évaluer (même si je sais qu'il est déterminé par les résultats nécessaires, il peut y avoir de grandes différences de performance entre évaluer d'abord A et ensuite B, ou évaluer d'abord B pour détecter que vous n'avez pas du tout besoin de A)

• comment les thunks sont-ils représentés ?

• comment sont utilisés la pile et le tas ?

• qu'est-ce qu'un CAF ? (le profilage indique parfois que le hotspot est là, mais je n'en sais rien)

Answer 1

La majorité des informations techniques sur l'architecture et l'approche du système GHC se trouve dans leur wiki. Je vais créer des liens vers les éléments clés, ainsi que vers des documents connexes que les gens ne connaissent peut-être pas.

Quelles optimisations typiques sont appliquées ?

Le document clé à ce sujet est : Un optimiseur basé sur la transformation pour Haskell , SL Peyton Jones et A Santos, 1998, qui décrit le modèle utilisé par GHC pour appliquer des transformations préservant les types (refactorings) d'un langage de base de type Haskell pour améliorer le temps et l'utilisation de la mémoire. Ce processus est appelé "simplification".

Les opérations typiques d'un compilateur Haskell sont les suivantes :

• Inlining ;
• Réduction du bêta ;
• Élimination des codes morts ;
• Transformation des conditions : cas d'espèce, élimination des cas.
• Unboxing ;
• Retour du produit construit ;
• Transformation totale de la paresse ;
• Spécialisation ;
• Expansion d'Eta ;
• Levage de lambda ;
• Analyse de la rigueur.

Et parfois :

• La transformation de l'argument statique ;
• Construction/foldr ou fusion de flux ;
• Élimination des sous-expressions communes ;
• Spécialisation du constructeur.

Le document susmentionné est le point de départ essentiel pour comprendre la plupart de ces optimisations. Certaines des optimisations les plus simples sont données dans le livre précédent, Mise en œuvre des langages fonctionnels Simon Peyton Jones et David Lester.

Quel est l'ordre d'exécution lorsqu'il y a plusieurs candidats à évaluer ?

En supposant que vous êtes sur un uni-processeur, alors la réponse est "un ordre que le compilateur choisit statiquement en se basant sur l'heuristique et le modèle de demande du programme". Si vous utilisez l'évaluation spéculative par le biais de sparks, alors "un certain modèle d'exécution non déterministe, hors de l'ordre".

En général, pour savoir quel est l'ordre d'exécution, il faut regarder le noyau, avec, par exemple, l'élément ghc-core outil. Un site introduction à Core se trouve dans le chapitre de RWH sur les optimisations.

Comment les thunks sont-ils représentés ?

Les thunks sont représentés comme des données allouées au tas avec un pointeur de code.

Véase la disposition des objets du tas . Plus précisément, voir comment les thunks sont représentés .

Comment sont utilisés la pile et le tas ?

Tel que déterminé par la conception de la G-machine sans étiquette et sans spin. plus précisément, avec de nombreuses modifications depuis la publication de cet article. En gros, le modèle d'exécution :

• Les objets (encadrés) sont alloués sur le tas global ;
• cada l'objet thread a une pile qui consiste en des cadres ayant la même disposition que les objets du tas ;
• lorsque vous faites un appel de fonction, vous poussez les valeurs sur la pile et sautez à la fonction ;
• si le code doit allouer, par exemple, un constructeur, ces données sont placées sur le tas.

Pour comprendre en profondeur le modèle d'utilisation de la pile, voir "Pousser/Entrer versus Eval/Appliquer" .

Qu'est-ce qu'un CAF ?

Une "forme applicative constante". Par exemple, une constante de haut niveau dans votre programme, allouée pour toute la durée de l'exécution de votre programme. Puisqu'elles sont allouées de manière statique, elles doivent être traités spécialement par le ramasseur de déchets .

---

Références et lectures complémentaires :

• Le commentaire du CGH
• The Spinless Tagless G-machine (La machine G sans étiquette)
• Compilation par transformation
• Pousser/Entrer vs Eval/Appliquer
• Des valeurs décomplexées en tant que citoyens de première classe
• Les secrets de la doublure
• Support d'exécution pour Haskell Multicore

Answer 2

Ce n'est probablement pas ce que vous aviez en tête comme texte d'introduction, mais Edward Yang a publié une série de billets de blog sur le tas Haskell, la façon dont les thunks sont mis en œuvre, etc.

Il est divertissant, tant par ses illustrations que par le fait qu'il explique les choses sans trop entrer dans les détails pour un novice en Haskell. La série couvre un grand nombre de vos questions :

• Le tas Haskell et la façon dont les thunks sont stockés - le premier article de la série
• Liaisons et CAF
• Comment la monade IO est traduite en primitives

Sur un plan plus technique, il existe un certain nombre de documents qui couvrent (de concert avec d'autres choses), des parties de ce que vous voulez savoir.. :

• Un article de SPJ, Simon Marlow et al sur la GC en Haskell. - Je ne l'ai pas lu, mais comme GC représente souvent un bon porton du travail effectué par Haskell, il devrait donner un aperçu.
• Le rapport Haskell 2010 - Je suis sûr que vous en avez déjà entendu parler, mais c'est trop beau pour ne pas le mentionner. La lecture peut être aride par endroits, mais c'est l'un des meilleurs moyens de comprendre ce qui fait de Haskell ce qu'il est, du moins les parties que j'ai lues.
• Une histoire de Haskell - est plus technique que son nom ne le suggère, et offre des vues très intéressantes sur la conception de Haskell, et les décisions qui se cachent derrière cette conception. On ne peut que mieux comprendre la mise en œuvre de Haskell après l'avoir lu.