Haskell哈希表性能

Question

我将使用hashtables包在Haskell中尝试使用哈希表，但发现无法达到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.Map 不同，Data.HashMap 没有严格的脊骨（我想），所以 foldl' 只是一个带有相应的 thunk 累积问题的 foldl，因此表现不佳。

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

- Andrew Gibiansky

---

你得到了什么时间？ - jamshidh

哈希表的设计需要平衡各种因素。值得指出的是，插入长线性数据序列几乎与哈希表的一般用例相反，因此这种人为的情况可能会因错误的原因而偏向于某种实现。然而，获取一组合适的随机数据来相互测试则存在风险，可能会测量到错误的代码部分。 - AndrewC

为什么要使用Data.Map而不是专门针对整数键的Data.IntMap？ - alternative

@AndrewGibiansky 我的意思是，一个针对一般用途进行优化的哈希表可能在处理非随机数据时表现不佳，因此使用线性数据进行测试可能会人为地减慢速度。（相反，一个能够快速接受线性数据的哈希表在发生冲突时可能表现不佳。）你现在没有测试正常性能，因此无法确定它在正常条件下的运行速度。（例如，如果你使用反转数据测试简单快速排序算法，你将得到一个不准确的典型性能图像。如果你将线性数据插入到树中，你将得到最坏情况的性能。） - AndrewC

你的 Map 和 HashMap 代码没有指定 Int 类型，因此默认使用较大且速度较慢的任意精度 Integer。 - AndrewC

Answer 1

根据reddit用户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

- user4222027

Answer 2

哈希表的文档指出："Cuckoo hashing(布谷鸟哈希)，像使用线性探测的基本哈希表实现一样，当表被调整大小时会遭受长时间延迟。" 你使用了new，它创建了一个默认大小的新表。 从查看源代码，默认大小为2。插入10000000个项目可能需要许多次调整大小。

试试使用newSized。

- Christian Conkle

---

感谢您的建议，这对我有很大帮助。如果我使用 newSized 来精确地指定元素数量，那么 Python 代码和 Haskell 代码的速度只会相差2倍。还有其他哪些技巧可能会有所帮助吗？ - Andrew Gibiansky

Answer 3

根据上述时间，我认为可以提供 Data.Map 的解决方案，这个方案似乎与使用 newSized 相当。

import qualified Data.Map as M

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

- jamshidh

---

这也是一个解决方案，但我认为它并不完全准确地反映了原始代码的含义，因为重点在于我们正在进行重复插入，且没有所有数据。但这仍然是一个有用的数据点。 - Andrew Gibiansky

@AndrewGibiansky，我认为你指的是fromList。但是如果你查看源代码，你会发现fromList只是插入操作的折叠实现。 - luqui

在我的平台上，将列表强制转换为:: [Int]可以提高13％的速度（从8.5秒到7.4秒），其中Data.Map.Lazy优于Data.Map.Strict，但切换到IntMap可以使其快2倍，而获胜者是Data.IntMap.Strict，时间为3.5秒。您实际上可以使用fromDistinctAscList更快（2.2秒），但正如安德鲁指出的那样，这可能是作弊，因为基准测试类似于真实世界的用法。 - CR Drost

我发现通过要求 GHC 使用其 LLVM 后端，IntMaps 的速度略有加快（约 10％），但效果不是很明显。相比之下，Python 运行时间为1.371秒，因此它仍然更快。当我将“fromList $ map”内容展开成带有“M.insert”的累加器循环时，似乎也会出现同样的加速，这可能是由于 cons-单元重新分配或其他原因。 - CR Drost