52

我读到 Haskell 中的哈希表存在性能问题（在 2006年的Haskell-Cafe和 2009 年的 Flying Frog Consultancy 的博客上），因为我喜欢 Haskell，这让我很担心。

那是一年前的事，现在（2010 年 6 月）的状态如何？GHC 中的“哈希表问题”是否已修复？

4

2 回答 2

137

问题是垃圾收集器需要遍历指针的可变数组（“盒装数组”），寻找指向可能准备好释放的数据的指针。盒装的可变数组是实现哈希表的主要机制，因此特定的结构会出现 GC 遍历问题。这是许多语言的共同点。症状是垃圾收集过多（高达 95% 的时间花在 GC 上）。

修复是在 GC中为可变指针数组实现“卡片标记” ，这发生在 2009 年末。现在在 Haskell 中使用可变指针数组时应该不会看到过多的 GC。在简单的基准测试中，大哈希的哈希表插入提高了 10 倍。

请注意，GC 遍历问题不会影响纯粹的功能结构，也不会影响未装箱的数组（如Haskell 中的大多数数据并行数组或类似向量的数组。它也不会影响存储在 C 堆上的哈希表（如judy）。这意味着它不会影响不使用命令式哈希表的日常 Haskeller。

如果您在 Haskell 中使用哈希表，您现在应该不会发现任何问题。例如，这里是一个简单的哈希表程序，它将 1000 万个整数插入到哈希中。我会做基准测试，因为原始引用没有提供任何代码或基准。

import Control.Monad
import qualified Data.HashTable as H
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  m <- H.new (==) H.hashInt
  forM_ [1..size] $ \n -> H.insert m n n
  v <- H.lookup m 100
  print v

使用 GHC 6.10.2，在修复之前，插入 10M 个整数：

$ time ./A 10000000 +RTS -s
...
47s.

使用 GHC 6.13，修复后：

./A 10000000 +RTS -s 
...
8s

增加默认堆区域：

./A +RTS -s -A2G
...
2.3s

避免使用哈希表并使用 IntMap：

import Control.Monad
import Data.List
import qualified Data.IntMap as I
import System.Environment

main = do
  [size] <- fmap (fmap read) getArgs
  let k = foldl' (\m n -> I.insert n n m) I.empty [1..size]
  print $ I.lookup 100 k

我们得到：

$ time ./A 10000000 +RTS -s        
./A 10000000 +RTS -s
6s

或者，或者，使用 judy 数组（它是通过外部函数接口调用 C 代码的 Haskell 包装器）：

import Control.Monad
import Data.List
import System.Environment
import qualified Data.Judy as J

main = do
  [size] <- fmap (fmap read) getArgs
  j <- J.new :: IO (J.JudyL Int)
  forM_ [1..size] $ \n -> J.insert (fromIntegral n) n j
  print =<< J.lookup 100 j

运行这个，

$ time ./A 10000000 +RTS -s
...
2.1s

因此，如您所见，哈希表的 GC 问题是固定的，并且一直有其他库和数据结构非常适合。总之，这不是问题。

注意：截至 2013 年，您可能应该只使用hashtables包，它本机支持一系列可变哈希表。

于 2010-06-17T02:40:20.150 回答
28

像这样的问题真的只能通过实验来解决。但如果你没有时间或金钱做实验，你就得问问其他人的想法。当您这样做时，您可能需要考虑来源并考虑所提供的信息是否已经过任何方式的审查或审查。

Jon Harrop 提出了一些关于 Haskell 的有趣主张。我建议您在 Google Groups 和其他地方搜索 Harrop 在 Haskell、Lisp 和其他函数式语言方面的专业知识。您还可以阅读 Chris Okasaki 和 Andy Gill 在 Haskell 的 Patricia 树上的工作，看看他们的专业知识是如何被评价的。您还可以找到谁的索赔（如果有的话）已经被第三方检查过。然后，您可以自己决定如何认真对待不同人对不同函数式语言性能的主张。

哦，不要喂巨魔。

PS 你自己做实验是很合理的，但也许没有必要，因为值得信赖的唐斯图尔特在他的好答案中提供了一些很好的微基准。这是唐的答案的附录：

附录：在主频为 2.5GHz、4GB RAM、32 位模式的 AMD Phenom 9850 Black Edition 上使用 Don Stewart 的代码，带有ghc -O,

  • 使用默认堆，它IntMap比哈希表快 40%。
  • 使用 2G 堆，哈希表比IntMap.
  • 如果我使用默认堆处理一千万个元素，则IntMap它比哈希表（CPU 时间）快四倍，或者是挂钟时间的两倍。

我对这个结果有点惊讶，但我确信函数式数据结构的性能非常好。并在我的信念中证实，在将要使用的实际条件下对代码进行基准测试确实值得。

于 2010-06-17T02:34:58.537 回答