Options RTS de GHC pour le ramassage des ordures

Question

J'ai un programme Haskell qui traite un fichier texte et construit un Map (avec plusieurs millions d'éléments). Le tout peut fonctionner pendant 2 à 3 minutes. J'ai trouvé que le fait de modifier les H et les options de fait une grande différence dans la course du temps.

Il y a de la documentation à propos de cette fonctionnalité de la RTS, mais il est difficile à lire pour moi, car je ne connais pas les algorithmes et les conditions de GC théorie. Je suis à la recherche d'un moindre explication technique, de préférence spécifique pour Haskell/GHC. Existe-il des références sur le choix judicieux des valeurs de ces options?

EDIT: C'est le code, il construit un trie une liste de mots.

buildTrie :: [B.ByteString] -> MyDFA 
buildTrie l = fst3 $ foldl' step (emptyDFA, B.empty, 1) $ sort $ map B.reverse l where
    step :: (MyDFA , B.ByteString, Int) -> B.ByteString -> (MyDFA , B.ByteString, Int)
    step (dfa, lastWord, newIndex) newWord = (insertNewStates, newWord, newIndex + B.length newSuffix) where            
        (pref, lastSuffix, newSuffix) = splitPrefix lastWord newWord
        branchPoint = transStar dfa pref

        --new state labels for the newSuffix path
        newStates = [newIndex .. newIndex + B.length newSuffix - 1]
        --insert newStates
        insertNewStates = (foldl' (flip insertTransition) dfa $ zip3 (branchPoint:init newStates) (B.unpack newSuffix) newStates)

Answer 1

En règle générale, la collecte des ordures est un espace/temps de compromis. Donner la GC de plus d'espace, et cela prendra moins de temps. Il y a (beaucoup) d'autres facteurs en jeu, cache en particulier, mais de l'espace/temps des compromis est le plus important.

Le compromis fonctionne comme ceci: le programme alloue de la mémoire jusqu'à ce qu'il atteint une certaine limite (décidé par le conseil d'administration automatique des paramètres de réglage, ou explicitement par la RTS options). Lorsque la limite est atteinte, le GC traces de toutes les données que le programme est en cours d'utilisation, et libère la mémoire utilisée par les données qui ne sont plus nécessaires. Le plus vous pouvez retarder ce processus, plus les données seront devenus inaccessible ("mort") dans l'intervalle, de sorte que le GC évite la vectorisation de données. Le seul moyen de retarder un GC est pour libérer de la mémoire à allouer en; par conséquent, plus la mémoire est égale à moins de GCs, est égale à une baisse GC frais généraux. Grosso modo, GHC l'option-H permet de définir une limite inférieure sur la quantité de mémoire utilisée par le GC, donc peut réduire le GC frais généraux.

GHC utilise un générationnelle GC, qui est une optimisation pour le régime de base, dans lequel le segment de mémoire est divisé en deux générations ou plus. Les objets sont répartis dans la "jeune" génération, et ceux qui vivent assez longtemps à obtenir une promotion dans la "vieille" génération (dans un 2-génération de l'installation). La jeune génération est recueilli beaucoup plus fréquemment que l'ancienne génération, l'idée étant que "la plupart des objets mourir jeune", si jeune génération collections sont bon marché (ils n'ont pas trace de la quantité de données), mais ils récupérer beaucoup de mémoire. Grosso modo, l'option-A permet de définir la taille de la jeune génération - qui est, la quantité de mémoire qui vous seront attribués avant la jeune génération est recueillie.

La valeur par défaut pour -Un est 512k: c'est une bonne idée de garder la jeune génération plus petit que le cache L2, et les performances en général gouttes si vous dépassez la taille du cache L2. Mais le fait de travailler dans la direction opposée est la GC de l'espace/temps de compromis: à l'aide d'un très grand jeune génération de la taille, peut dépasser le cache, en réduisant la quantité de travail que le GC a à faire. Cela n'arrive pas toujours, cela dépend de la dynamique de l'application, ce qui rend difficile pour la GC pour syntoniser automatiquement lui-même. L'option-H augmente également la jeune génération de la taille, peut donc également avoir un effet négatif sur l'utilisation du cache.

La ligne de fond est: jouer avec les options et voir ce qui fonctionne. Si vous avez une quantité de mémoire importante, vous pourriez bien être en mesure d'obtenir une augmentation de la performance en utilisant Un ou-H, mais pas nécessairement.

Answer 2

Il est probablement possible de reproduire le problème pour les petits ensembles de données, où il sera plus facile de voir ce qui se passe. En particulier, je suggère d'acquérir une certaine familiarité avec le profilage:

• le profilage chapitre dans le Monde Réel Haskell livre fournit une bonne vue d'ensemble, y compris les questions qui l'on peut rencontrer
• le profilage chapitre dans GHC manuel des documents de la fonctionnalité disponible

Ensuite, vérifiez si la mémoire de profils que vous voyez correspond à vos attentes (vous n'avez pas besoin de connaître tous les profilage des options pour obtenir des graphiques utiles). La combinaison de la stricte foldl' , avec une non-stricte tuple comme l'accumulateur serait la première chose que je regarde: si les éléments du tuple ne sont pas obligés, que la récursivité est la construction des expressions non évaluées.

Btw, vous pouvez construire une bonne intuition de ce genre de choses en essayant d'évaluer votre code à la main pour vraiment minuscule ensembles de données. Quelques itérations suffisent pour voir si les expressions sont évaluées ou ne sont pas évalués de la manière qui convient à votre application.