Haskell Hashtable Leistung

Question

Ich versuche, Hash-Tabellen in Haskell mit der hashtables package zu verwenden, und zu finden, dass ich nicht in der Nähe von Pythons Leistung kommen kann. Wie kann ich ähnliche Leistungen erzielen? Ist es möglich, aktuelle Haskell-Bibliotheken und Compiler zu geben? Wenn nicht, was ist das zugrunde liegende Problem?

Hier ist meine Python-Code:

y = {} 
for x in xrange(10000000): 
    y[x] = x 
print y[100] 

Hier ist mein entsprechenden Code Haskell:

import qualified Data.HashTable.IO as H 
import Control.Monad 

main = do 
    y <- H.new :: IO (H.CuckooHashTable Int Int) 
    forM_ [1..10000000] $ \x -> H.insert y x x 
    H.lookup y 100 >>= print 

Hier ist eine andere Version ist Data.Map verwenden, die für mich langsamer als beide ist:

import qualified Data.Map as Map 
import Data.List 
import Control.Monad 
main = do 
    let m = foldl' (\m x -> Map.insert x x m) Map.empty [1..10000000] 
    print $ Map.lookup 100 m 

Interessanterweise funktioniert Data.HashMap sehr schlecht:

import qualified Data.HashMap.Strict as Map 
import Data.List 
main = do 
    let m = foldl' (\m x -> Map.insert x x m) Map.empty [1..10000000] 
    print $ Map.lookup 100 m 

Mein Verdacht ist, dass Data.HashMap schlecht ab, weil im Gegensatz zu Data.Map, ist es nicht wirbelsäulen streng (glaube ich), so foldl' ist nur ein foldl, mit den damit verbundenen thunk Aufbauproblemen.

Bitte beachte, dass ich verwendet habe -prof und bestätigt, dass die Mehrheit der Zeit verbringt, ist in dem hashtables oder Data.Map Code, nicht auf den forM oder so etwas. Der gesamte Code ist mit -O2 und anderen Parametern kompiliert.

Answer 1

Die Dokumentation für hashtables stellt fest, dass "Cuckoo Hashing, wie die grundlegende Hash-Tabellenimplementierung mit linearen Probing, lange Verzögerungen leiden kann, wenn die Tabelle in der Größe geändert wird." Sie verwenden new, die eine neue Tabelle der Standardgröße erstellt. From looking at the source, scheint die Standardgröße 2 zu sein. Das Einfügen von 10000000 Elementen führt wahrscheinlich zu zahlreichen Änderungen.

Versuchen Sie mit newSized.

Answer 2

Angesichts der oben genannten Zeiten dachte ich, ich würde die Data.Map Lösung werfen, die mit der Verwendung von newSize vergleichbar zu sein scheint.

import qualified Data.Map as M 

main = do 
     print $ M.lookup 100 $ M.fromList $ map (\x -> (x,x)) [1..10000000] 

Answer 3

Als reddit.com/u/cheecheeo here vorgeschlagen, mit Data.Judy, werden Sie eine ähnliche Leistung für Ihre speziellen-Micro erhalten:

module Main where 

import qualified Data.Judy as J 
import Control.Monad (forM_) 

main = do 
    h <- J.new :: IO (J.JudyL Int) 
    forM_ [0..10000000] $ \i -> J.insert (fromIntegral i) i h 
    v <- J.lookup 100 h 
    putStrLn $ show v 

timeing die oben:

$ time ./Main 
Just 100 

real 0m0.958s 
user 0m0.924s 
sys  0m0.032s 

Timing des Python-Codes von OP:

$ time ./main.py 
100 

real 0m1.067s 
user 0m0.886s 
sys  0m0.180s