好奇哈希表性能问题
我读过哈斯克尔的哈希表中存在的性能问题（2006年的Haskell-Cafe和2009年的Frog Consultancy的博客 ），而且因为我喜欢Haskell，所以我很担心。
那是一年前，现在是什么状态（2010年6月）？ GHC中的“哈希表问题”是否已经被修复？
问题在于垃圾收集器需要遍历可变数组指针（“盒式数组”），寻找指向可能准备释放的数据的指针。 盒装，可变数组是实现哈希表的主要机制，因此特定的结构显示了GC遍历问题。 这对很多语言来说都很常见。 症状是垃圾收集过多（在GC中花费的时间高达95％）。
解决的办法是在GC中为指针的可变数组实现“卡片标记” ，这在2009年末发生。现在，在Haskell中使用可变的指针数组时，您不应该看到过多的GC。 在简单的基准testing中，大哈希hashtable插入提高了10倍。
请注意，GC散步问题不会影响纯函数结构 ，也不会影响Haskell中的大多数数据并行数组或类似向量的数组，也不会影响存储在C堆上的散列表（如judy ）。它不会影响日常Haskellers不使用命令式散列表。
如果你在Haskell中使用哈希表，你现在不应该观察任何问题。 例如，这里是一个简单的散列表程序，它将1000万个整数插入散列。 我会做基准testing，因为原始引用没有提供任何代码或基准。
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 mnn 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' (\mn -> I.insert nnm) 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) nj print =<< J.lookup 100 j
运行这个，
$ time ./A 10000000 +RTS -s ... 2.1s
所以，正如你所看到的，哈希表的GC问题是固定的 ，并且总是有其他的库和数据结构是非常合适的。 总之，这是一个非问题。
注意：从2013年开始，您应该只使用hashtables包，它本地支持一系列可变的hashtable 。
像这样的问题只能通过实验来解决。 但是，如果你没有时间和金钱去做实验，那么你就得问问别人他们的想法。 当你这样做的时候，你可能要考虑来源，并考虑给出的信息是否已经以任何方式审查或审查。
Jon Harrop提出了一些关于Haskell的有趣说法。 让我build议您在Google Groups和其他地方searchHarrop在Haskell，Lisp和其他function语言方面的专业知识。 您还可以阅读Chris Okasaki和Andy Gill在Haskell的Patricia树上所做的工作，了解他们的专业知识是如何被看待的。 你也可以find谁的索赔，如果有的话，已由第三方检查。 那么你可以自己决定如何认真对待不同的function语言的performance。
哦，不要喂巨魔。
PS你做自己的实验是相当合理的，但也许没有必要，因为可靠的唐·斯图尔特（Don Stewart）在他的好的答案中提出了一些很好的微观基准 。 这是Don的答案的附录：
附录：在AMD Phenom 9850 Black Edition上使用Don Stewart的代码，时钟频率为2.5GHz，4GB RAM，32位模式下，使用ghc -O ，
- 使用默认堆，
IntMap比散列表快40％。 - 使用2G堆，哈希表比
IntMap快40％。 - 如果我使用默认堆数千万个元素，则
IntMap比散列表（CPU时间） 快4倍 ，IntMap是挂钟时间的两倍 。
我对这个结果有点惊讶，但是保证function数据结构performance相当好。 并且我确信，在实际使用的条件下，它确实支付您的代码的基准。
简而言之，即使在最新的GHC中，Haskell仍然无法提供有竞争力的字典（可变或不可变）。
使用GHC 6.10，Haskell的散列表比C ++和.NET等替代品慢32倍 。 这部分是由于GHC 6.12.2修复的GHC垃圾收集器的性能问题 。 但是Simon Marlow在那里的结果只显示了5倍的性能改进，这仍然使Haskell的哈希表比大多数替代方法慢了许多倍。
纯function的替代品也比正常的哈希表慢得多。 例如， Haskell的IntMap比.NET的哈希表慢了10倍 。
在这个运行32位Windows Vista的2.0GHz E5405 Xeon上使用F＃2010和最新的Haskell Platform 2010.2.0.0 （昨天发布！），将GHM 6.12.3join到一个空的哈希表中，我们发现Haskell仍然比F＃实时慢29倍，CPU时间超过200倍，因为Haskell烧毁所有内核：
GHC 6.12.3 Data.HashTable：42.8s（new！） .NET哈希表：1.47s
假如你只运行短命的微基准，你可以按照唐·斯图尔特（Don Stewart）上面的build议禁用GHC垃圾回收器。 通过要求一个如此之大的托儿所，这个特定的程序将永远不会填满，他把Haskell哈希表的时间降低到只有1.5秒。 然而，这完全破坏了产生一个托儿所的整个观点，并将大量降低其他代码的性能，因为新分配的值现在总是在caching中是冷的（这就是为什么托儿所一代通常是二级caching的大小，比这个数量级要小）。
