50 votes

Curieux de connaître les problèmes de performance des tables de hachage.

J'ai lu que les tables de hachage en Haskell avaient des problèmes de performance (sur le Haskell-Cafe en 2006 et Le blog de Flying Frog Consultancy en 2009), et comme j'aime Haskell, cela m'a inquiété.

C'était il y a un an, quel est le statut actuel (juin 2010) ? Le "problème des tables de hachage" a-t-il été résolu dans GHC ?

136voto

Don Stewart Points 94361

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.

27voto

Norman Ramsey Points 115730

Une question comme celle-ci ne peut vraiment être réglée que par l'expérience. Mais si vous n'avez pas le temps ou l'argent pour faire des expériences, vous devez demander à d'autres personnes ce qu'elles pensent. Lorsque vous le faites, vous devez tenir compte de la source et vous demander si les informations données ont été examinées ou vérifiées d'une manière ou d'une autre.

Jon Harrop a avancé quelques affirmations intéressantes sur Haskell. Permettez-moi de vous suggérer de rechercher sur Google Groups et ailleurs des preuves de l'expertise de Harrop en Haskell, Lisp et autres langages fonctionnels. Vous pouvez également lire les travaux de Chris Okasaki et Andy Gill sur les arbres Patricia en Haskell, pour voir comment leur expertise est considérée. Vous pouvez également trouver les affirmations qui, le cas échéant, ont été vérifiées par une tierce partie. Vous pourrez alors vous faire votre propre opinion sur le sérieux à accorder aux affirmations des uns et des autres concernant les performances des différents langages fonctionnels.

Oh, et ne nourrissez pas le troll.


P.S. Il serait tout à fait raisonnable que vous fassiez vos propres expériences, mais peut-être pas nécessaire, puisque la fidèle Don Stewart présente quelques microbenchmarks intéressants. dans sa belle réponse. Voici un addendum à la réponse de Don :


Addendum : En utilisant le code de Don Stewart sur un AMD Phenom 9850 Black Edition cadencé à 2.5GHz avec 4GB de RAM, en mode 32-bit, avec ghc -O ,

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

Je suis un peu surpris par ce résultat, mais rassuré par le fait que les structures de données fonctionnelles se comportent plutôt bien. Et confirmé dans ma conviction qu'il est vraiment payant d'évaluer son code dans les conditions réelles dans lesquelles il sera utilisé.

7voto

Jon Harrop Points 26951

En bref, même avec le correctif de la dernière version de GHC, Haskell est toujours incapable de fournir un dictionnaire (mutable ou immuable) qui soit compétitivement efficace.

Les tables de hachage de Haskell étaient 32× plus lent que les alternatives comme C++ et .NET avec GHC 6.10. Cela était en partie dû à une bogue de performance dans le collecteur de déchets de GHC qui a été corrigé pour GHC 6.12.2 . Mais les résultats de Simon Marlow ne montrent qu'une amélioration des performances de 5×, ce qui laisse les tables de hachage de Haskell plusieurs fois plus lentes que la plupart des alternatives.

Les alternatives purement fonctionnelles sont également beaucoup plus lentes qu'une table de hachage décente. Par exemple, Haskell IntMap est 10 fois plus lent que la table de hachage de .NET. .

Utilisation de F# 2010 et la dernière version de la plate-forme Haskell 2010.2.0.0 (publié hier !) avec GHC 6.12.3 sur ce Xeon E5405 de 2,0 GHz exécutant Windows Vista 32 bits pour insérer 20M de liaisons int->int dans une table de hachage vide, nous constatons que Haskell est toujours 29× plus lent que 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

Si vous n'exécutez que des microbenchmarks de courte durée, vous pouvez désactiver le garbage collector de GHC comme le suggère Don Stewart ci-dessus. En demandant une génération de pépinière si grande que ce programme particulier ne la remplira jamais, il a ramené le temps pour la table de hachage Haskell à seulement 1,5s ici. Cependant, cela sape complètement l'intérêt d'avoir une génération de pépinière et dégradera massivement les performances des autres codes car les valeurs fraîchement allouées seront toujours froides dans le cache (c'est pourquoi la génération de pépinière est typiquement de la taille du cache L2, des ordres de grandeur plus petits que cela).

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X