Curieux au sujet des problèmes de performance Hashtable

Question

Je lis que les tables de hachage dans Haskell avaient des problèmes de performance (sur le Haskell -Cafe en 2006 et volant blog Frog Conseil en 2009), et depuis que je Haskell comme il me inquiète.

C'était il y a un an, quel est le statut maintenant (Juin 2010)? A été corrigé dans le GHC « problème de table de hachage »?

Answer 1

Le problème était que le garbage collector est nécessaire pour parcourir les tableaux mutables de pointeurs ( « tableaux encadrés ») à la recherche de pointeurs vers les données qui pourraient être prêts à désaffecter. tableaux Boxed, mutables sont le principal mécanisme pour la mise en œuvre d'une table de hachage, de sorte que la structure particulière a montré la question GC traversal. Cette situation est commune à de nombreuses langues. Le symptôme est la collecte des ordures excessive (jusqu'à 95% du temps passé en GC).

Le correctif était mettre en œuvre dans le GC « marquage carte » pour les tableaux mutables de pointeurs, qui sont apparus à la fin de 2009. Vous ne devriez pas voir GC excessive lors de l'utilisation des tableaux mutables de pointeurs dans Haskell maintenant. Sur les points de repère simples, l'insertion Hashtable pour les grandes hash améliorée par 10x.

Notez que la question de la marche GC n'affecte pas structures purement fonctionnelles , ni des réseaux sans emballage ( comme la plupart des données réseaux parallèles ou vecteur -comme les tableaux, en Haskell. elle n'affecte pas hashtables stockées sur le tas de C (comme judy). ce qui signifie que cela n'a pas affecté Haskellers au jour le jour de ne pas utiliser des tables de hachage impératif.

Si vous utilisez hashtables dans Haskell, vous ne devriez pas observer toute question maintenant. Ici, par exemple, est un programme simple Hashtable qui insère 10 millions ints dans un hachage. Je ferai l'analyse comparative, étant donné que la citation originale ne présente pas de code ou de référence.

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 10M ints:

$ time ./A 10000000 +RTS -s
...
47s.

Avec GHC 6.13, après le correctif:

./A 10000000 +RTS -s 
...
8s

L'augmentation de la zone de segment par défaut:

./A +RTS -s -A2G
...
2.3s

Éviter hashage et en utilisant 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 nous obtenons:

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

Ou, alternativement, en utilisant un tableau judy (qui est un wrapper Haskell appelant code C via l'interface fonction étrangère):

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

L'exécution de ce,

$ time ./A 10000000 +RTS -s
...
2.1s

Donc, comme vous pouvez le voir, la question de GC avec hashage est fixe , et il y a toujours été d'autres bibliothèques et structures de données qui étaient parfaitement adaptés. En résumé, c'est pas un problème.

Note: à partir de 2013, vous devriez probablement utiliser le package hashtables, qui soutient < a href = "http://gregorycollins.net/posts/2011/06/11/announcing-hashtables" rel = "noreferrer"> un ensemble de tables de hachage mutables natif.

Answer 2

Une question comme cela peut vraiment être réglé que par l'expérience. Mais si vous n'avez pas le temps ou l'argent pour faire des expériences, vous devez demander aux autres ce qu'ils pensent. Lorsque vous le faites, vous voudrez peut-être considérer la source et déterminer si les informations données ont été examinées ou étudiées à fond aucune façon.

Jon Harrop a avancé des demandes intéressantes au sujet de Haskell. Permettez-moi de suggérer que vous effectuez une recherche sur Google Groupes et ailleurs des preuves de l'expertise de Harrop dans Haskell, Lisp, et d'autres langages fonctionnels. Vous pouvez également lire le travail de Chris Okasaki et Andy Gill sur les arbres Patricia en Haskell, voir comment leur savoir-faire est considérée. Vous pouvez également trouver dont la demande, le cas échéant, ont été vérifiés par un tiers. Ensuite, vous pouvez faire votre propre idée du sérieux de prendre différentes demandes des gens sur les performances des différentes langues fonctionnelles.

Oh, et ne pas nourrir le troll.

---

P.S. Il serait tout à fait raisonnable pour vous de faire vos propres expériences, mais peut-être pas nécessaire, puisque les fidèles présente Don Stewart quelques belles microbenchmarks dans sa réponse fine. Voici un addendum à la réponse de Don:

---

Addendum: En utilisant le code de Don Stewart sur un processeur AMD Phenom 9850 Black Edition cadencé à 2,5 GHz avec 4 Go de RAM, en mode 32 bits, avec ghc -O,

• Avec le tas par défaut, le IntMap est 40% plus rapide que la table de hachage.
• Avec le tas 2G, la table de hachage est 40% plus rapide que le IntMap.
• Si je vais à dix millions d'éléments avec le tas par défaut, le IntMap est quatre fois plus rapide que la table de hachage (temps CPU) ou deux fois plus rapide par mur- horloge temps.

Je suis un peu surpris par ce résultat, mais que les structures de rassurent données fonctionnelles effectuent des assez bien. Et confirmé dans ma conviction qu'il est vraiment rentable de votre code de référence dans les conditions réelles dans lesquelles il va être utilisé.

Answer 3

En bref, même avec le correctif dans le dernier GHC, Haskell est toujours incapable de fournir un dictionnaire (mutable ou immuable) qui est concurrentielle efficace.

Les tables de hachage Haskell étaient 32 × plus lent que des alternatives comme C ++ et .NET avec GHC 6.10. Cela était dû en partie à un problème de performance dans le garbage collector GHC qui a été fixé pour GHC 6.12.2 . Mais les résultats de Simon Marlow il ne montrent qu'une amélioration de 5 × performances qui laisse encore les tables de hachage de Haskell plusieurs fois plus lent que la plupart des solutions de rechange.

alternatives sont également fonctionnelles Purement beaucoup plus lent que d'une table de hachage décent. Par exemple, IntMap Haskell est 10 × plus lent que la table de hachage .NET .

En utilisant F # 2010 et la dernière plate-forme Haskell 2010.2.0.0 (publié hier!) avec GHC 6.12.3 sur ce 2.0GHz Xeon E5405 exécutant des liaisons 32 bits de Windows Vista pour insérer 20M int> int dans une table de hachage vide nous constatons que Haskell est encore plus lent que 29 × F # en temps réel et plus de 200 × plus lent en termes de temps CPU parce que le Haskell brûle tous les cœurs:

GHC 6.12.3 Data.HashTable: 42.8s (new!)
.NET hash table:            1.47s

Pourvu que vous ne diffusez que microbenchmarks de courte durée, vous pouvez désactiver le garbage collector GHC comme Don Stewart suggère ci-dessus. En demandant une génération de pépinière si grand que ce programme ne sera jamais le remplir, il a le temps de la table de hachage Haskell jusqu'à seulement 1.5s ici. Cependant, cela mine complètement le point entier d'avoir une génération de pépinière et dégradera massivement les performances des autres codes parce que les valeurs seront désormais toujours froid fraîchement alloués dans le cache (ce qui explique pourquoi la génération maternelle est généralement la taille du cache L2, ordres de grandeur que celui-ci).