Haskell Hashtable性能

Question

我试图在Haskell中使用hashtables包的哈希表,并发现我无法接近Python的性能.我怎样才能达到类似的性能？是否有可能给出当前的Haskell库和编译器？如果没有,那么潜在的问题是什么？

这是我的Python代码:

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

这是我相应的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

这是另一个使用的版本Data.Map,对我来说比两者都慢:

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

有趣的是,Data.HashMap表现非常糟糕:

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

我的怀疑是Data.HashMap表现不好,因为不像Data.Map,它不是脊柱严格的(我认为),所以foldl'只是一个foldl,伴随着相关的thunk积累问题.

请注意,我已经使用-prof并验证了大部分的时间花费在hashtables或Data.Map代码,不上forM或类似的东西.所有代码都是用-O2其他参数编译的.

Answer 1

正如reddit.com/u/cheecheeo 在这里建议的那样,使用Data.Judy,您将获得与您的特定微基准测试相似的性能:

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

计时如上:

$ time ./Main
Just 100

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

定时OP的python代码:

$ time ./main.py
100

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

Answer 2

hashtables"Cuckoo散列的注释文档,就像使用线性探测的基本哈希表实现一样,在调整表格大小时可能会遇到长时间的延迟".您使用new,它创建一个默认大小的新表.从查看源代码看,默认大小为2.插入10000000个项目可能需要多次调整.

尝试使用newSized.