Comment écrivez-vous des structures de données aussi efficaces que possible dans le GHC?

Donc, parfois, j’ai besoin d’écrire une structure de données que je ne trouve pas sur Hackage, ou ce que je trouve n’est pas testé ou de qualité suffisante pour que je puisse avoir confiance, ou bien c’est quelque chose que je ne veux pas être une dépendance. Je suis en train de lire le livre d’Okasaki en ce moment, et c’est plutôt bien d’expliquer comment concevoir des structures de données asymptotiquement rapides.

Cependant, je travaille spécifiquement avec GHC. Des facteurs constants sont un gros problème pour mes applications. L’utilisation de la mémoire est aussi un gros problème pour moi. J’ai donc des questions spécifiques sur le GHC.

En particulier

  • Comment maximiser le partage des nœuds
  • Comment réduire l’empreinte mémoire
  • Comment éviter les fuites d’espace dues à une rigidité / paresse inappropriée
  • Comment faire en sorte que GHC produise des boucles internes serrées pour des sections importantes du code

J’ai parcouru différents endroits sur le Web et j’ai une vague idée de la façon de travailler avec GHC, par exemple, en examinant les principaux résultats, en utilisant les UNPACK UNPACK, etc. Mais je ne suis pas sûr de l’avoir.

J’ai donc ouvert ma bibliothèque de structures de données préférée, mes conteneurs, et j’ai regardé le module Data.Sequence. Je ne peux pas dire que je comprends beaucoup de ce qu’ils font pour rendre Seq rapide.

La première chose qui attire mon attention est la définition de FingerTree a . Je suppose que c’est juste que je ne suis pas familier avec les arbres de doigt cependant. La deuxième chose qui attire mon attention est tous les pragmas SPECIALIZE . Je n’ai aucune idée de ce qui se passe ici, et je suis très curieux, car ils sont éparpillés dans tout le code.

De nombreuses fonctions sont également associées à un pragma INLINE . Je peux deviner ce que cela signifie, mais comment puis-je porter un jugement sur les fonctions INLINE ?

Les choses deviennent vraiment intéressantes autour de la ligne 475, une section intitulée «Construction Applicative». Ils définissent un wrapper newtype pour représenter la monade d’identité, ils écrivent leur propre copie de la monade à état ssortingct, et ils ont une fonction définie par l’ applicativeTree Je n’ai aucune idée de ce qui se passe ici. Quelle sorcellerie est utilisée pour augmenter le partage?

Quoi qu’il en soit, je ne suis pas sûr qu’il y ait beaucoup à apprendre de Data.Sequence. Existe-t-il d’autres «programmes modèles» que je peux lire pour acquérir de la sagesse? J’aimerais vraiment savoir comment faire évoluer mes structures de données lorsque j’aurais vraiment besoin d’eux pour aller plus vite. Une chose en particulier consiste à écrire des structures de données qui facilitent la fusion et à rédiger de bonnes règles de fusion.

C’est un gros sujet! La plupart ont été expliquées ailleurs, alors je n’essaierai pas d’écrire un chapitre de livre ici. Au lieu:

  • Real World Haskell, ch 25, ” Performance ” – discute du profilage, de la spécialisation simple et du déballage, de la lecture de Core et de certaines optimisations.

Johan Tibell écrit beaucoup sur ce sujet:

  • Calcul de la taille d’une structure de données
  • Empreintes mémoire de types de données communs
  • Structures persistantes plus rapides grâce au hachage
  • Raisonnement sur la paresse

Et quelques choses d’ici:

  • Lire GHC Core
  • Comment GHC fait de l’optimisation
  • Profilage pour la performance
  • Réglage des parameters GC
  • Améliorations générales
  • Plus sur le déballage
  • Déballage et rigueur

Et d’autres choses:

  • Introduction à la spécialisation du code et des données
  • Indicateurs d’amélioration du code

applicativeTree est assez sophistiqué, mais surtout en ce qui concerne les FingerTrees en particulier, qui sont eux-mêmes une structure de données très sophistiquée. Nous avons discuté des subtilités de la théorie . Notez que applicativeTree est écrit pour fonctionner sur n’importe quel applicatif. Il se trouve que lorsqu’il est spécialisé dans les Id il peut partager des nœuds d’une manière qui ne le serait pas autrement. Vous pouvez travailler vous-même sur la spécialisation en insérant les méthodes d’ Id et en observant ce qui se passe. Notez que cette spécialisation est utilisée dans un seul endroit – la fonction de replicate O (log n). Le fait que la fonction plus générale se spécialise clairement dans le cas constant est une réutilisation de code très intelligente, mais c’est vraiment tout.

En général, Sequence enseigne plus sur la conception de structures de données persistantes que sur toutes les astuces pour améliorer les performances, je pense. Les suggestions de Dons sont bien sûr excellentes. Je voudrais aussi parcourir la source des IntMap vraiment canoniques et optimisées – Map , IntMap , Set et IntSet en particulier. Parallèlement à ceux-ci, il convient de jeter un coup d’œil sur l’ article de Milan sur ses améliorations apscopes aux conteneurs .