Haskell Hashtable Performance

Question

Próbuję użyć tabel mieszania w Haskell z hashtables package i stwierdzenie, że nie mogę uzyskać w pobliżu wydajności Pythona. Jak mogę osiągnąć podobną wydajność? Czy jest to możliwe, biorąc pod uwagę obecne biblioteki i kompilatory Haskella? Jeśli nie, jaki jest podstawowy problem?

Oto mój kod Python:

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

Oto mój odpowiedni kod 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 

Oto kolejna wersja użyciu Data.Map, które jest wolniejsze niż zarówno dla mnie:

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 

Co ciekawe, Data.HashMap działa bardzo źle:

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 

Podejrzewam, że Data.HashMap wykonuje źle, ponieważ w odróżnieniu Data.Map, nie jest Mrożąca ścisłe (chyba), więc foldl' tylko foldl, związanych z tym problemów thunk wodnej.

Zauważ, że użyłem -prof i sprawdzeniu, że większość czasu jest spędzić w kodzie hashtables lub Data.Map, a nie na forM lub coś podobnego. Cały kod jest kompilowany z -O2 i nie ma innych parametrów.

Answer 1

Dokumentacja dla hashtables stwierdza, że ​​"Cuckoo hashing, podobnie jak podstawowa implementacja tablic asocjacyjnych za pomocą sondowania liniowego, może cierpieć z powodu dużych opóźnień przy zmianie rozmiaru tabeli." Używasz new, która tworzy nową tabelę domyślnego rozmiaru. From looking at the source, wydaje się, że domyślny rozmiar to 2. Wstawienie 10000000 elementów prawdopodobnie pociąga za sobą liczne zmiany rozmiaru.

Spróbuj użyć newSized.

Answer 2

Biorąc pod uwagę powyższe czasy, pomyślałem, że wrzucę rozwiązanie Data.Map, które wydaje się być porównywalne do używania newSized.

import qualified Data.Map as M 

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

Answer 3

Jak reddit.com/u/cheecheeo zasugerował here korzystając Data.Judy, dostaniesz podobną wydajność dla danego 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 powyższego:

$ time ./Main 
Just 100 

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

Czas synchronizacji kodu Pythona:

$ time ./main.py 
100 

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