Haskell 哈希表性能

Question

我正在尝试在 Haskell 中使用哈希表 hashtables package ，并发现我无法接近 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 建议的那样 here ，使用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