Le problème était que le ramasseur d'ordures doit parcourir des tableaux mutables de pointeurs ("tableaux encadrés") à la recherche de pointeurs vers des données qui pourraient être prêtes à être désallouées. Les tableaux mutables en boîte sont le principal mécanisme d'implémentation d'une table de hachage, et cette structure particulière a donc révélé le problème de traversée du GC. Ce problème est commun à de nombreux langages. Le symptôme est une collecte excessive de déchets (jusqu'à 95 % du temps passé en GC).
La solution consistait à mettre en œuvre le "marquage des cartes" dans le CG pour les tableaux mutables de pointeurs, qui a eu lieu fin 2009. Vous ne devriez plus voir de GC excessive lorsque vous utilisez des tableaux de pointeurs mutables en Haskell. Sur les benchmarks simples, l'insertion de table de hachage pour les grands hachages a été améliorée de 10x.
Notez que le problème de la marche de la GC n'affecte pas les structures purement fonctionnelles ni les tableaux non encapsulés (comme la plupart des données). réseaux parallèles o vecteur -comme des tableaux, en Haskell. Cela n'affecte pas non plus les hashtables stockés sur le tas C (comme judy ). Ce qui signifie que cela n'a pas affecté les Haskellers quotidiens n'utilisant pas de tables de hachage impératives.
Si vous utilisez des hashtables en Haskell, vous ne devriez pas rencontrer de problème maintenant. Voici, par exemple, un programme simple de hashtable qui insère 10 millions d'ints dans un hash. Je vais faire le benchmarking, puisque la citation originale ne présente aucun code ou benchmarking.
import Control.Monad
import qualified Data.HashTable as H
import System.Environment
main = do
[size] <- fmap (fmap read) getArgs
m <- H.new (==) H.hashInt
forM_ [1..size] $ \n -> H.insert m n n
v <- H.lookup m 100
print v
Avec GHC 6.10.2, avant le correctif, l'insertion de 10M ints :
$ time ./A 10000000 +RTS -s
...
47s.
Avec GHC 6.13, après le correctif :
./A 10000000 +RTS -s
...
8s
Augmentation de la zone du tas par défaut :
./A +RTS -s -A2G
...
2.3s
Éviter les hashtables et utiliser un IntMap :
import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment
main = do
[size] <- fmap (fmap read) getArgs
let k = foldl' (\m n -> I.insert n n m) I.empty [1..size]
print $ I.lookup 100 k
Et on obtient :
$ time ./A 10000000 +RTS -s
./A 10000000 +RTS -s
6s
Ou, alternativement, en utilisant un tableau judy (qui est un wrapper Haskell appelant du code C via l'interface foreign-function) :
import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J
main = do
[size] <- fmap (fmap read) getArgs
j <- J.new :: IO (J.JudyL Int)
forM_ [1..size] $ \n -> J.insert (fromIntegral n) n j
print =<< J.lookup 100 j
Je fais ça,
$ time ./A 10000000 +RTS -s
...
2.1s
Donc, comme vous pouvez le voir, le problème de GC avec les hashtables est Correction de et il y a il y a toujours eu d'autres bibliothèques et structures de données qui convenaient parfaitement. En résumé, ce n'est pas un problème.
Remarque : à partir de 2013, vous devriez probablement vous contenter d'utiliser la fonction hashtables qui prend en charge une gamme de hashtables mutables nativement.