Haskell Hashtable Performance

Question

Sto cercando di utilizzare le tabelle hash in Haskell con lo hashtables package e trovo che non riesco ad andare da nessuna parte vicino alle prestazioni di Python. Come posso ottenere prestazioni simili? E 'possibile dare le attuali librerie e compilatori Haskell? In caso contrario, qual è il problema di fondo?

Ecco il mio codice Python:

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

Ecco il mio corrispondente codice 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 

Ecco un'altra versione utilizzando Data.Map, che è più lento di sia per me:

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 

È interessante notare che Data.HashMap si comporta molto male:

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 

mio sospetto è che Data.HashMap esegue male perché a differenza di Data.Map, non è spina dorsale-rigida (credo), quindi foldl' è solo un foldl, con i problemi di accumulo tonfo associati.

Nota che ho usato -prof e verificato che la maggior parte del tempo è passare nel codice hashtables o Data.Map, non sul forM o qualcosa di simile. Tutto il codice è compilato con -O2 e nessun altro parametro.

Answer 1

La documentazione per hashtables rileva che "L'hashing del cuculo, come l'implementazione della tabella hash di base mediante sondaggio lineare, può subire lunghi ritardi quando la tabella viene ridimensionata." Si utilizza new, che crea una nuova tabella con le dimensioni predefinite. From looking at the source, sembra che la dimensione predefinita sia 2. L'inserimento di 10000000 elementi probabilmente comporta numerose modifiche.

Provare a utilizzare newSized.

Answer 2

Considerati i tempi indicati sopra, ho pensato di inserire la soluzione Data.Map, che sembra essere paragonabile all'utilizzo di newSized.

import qualified Data.Map as M 

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

Answer 3

Come reddit.com/u/cheecheeo suggerito here, utilizzando Data.Judy, otterrete prestazioni simili per la sua particolare microbenchmark:

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 quanto sopra:

$ time ./Main 
Just 100 

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

Cronometrare il codice Python di OP:

$ time ./main.py 
100 

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