对HashTable的性能问题感到好奇

StackOverflow https://stackoverflow.com/questions/3058529

  •  27-09-2019
  •  | 
  •  

题

我读到 Haskell 中的哈希表存在性能问题（在 哈斯克尔咖啡馆 2006年和 飞蛙咨询的博客 2009 年），由于我喜欢 Haskell，这让我很担心。

那是一年前的事了，现在（2010年6月）情况如何？GHC 中的“哈希表问题”解决了吗？

有帮助吗？

解决方案

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

解决办法是 在 GC 中实施“卡片标记” 对于可变指针数组，这发生在 2009 年末。现在在 Haskell 中使用可变指针数组时，您不应该看到过多的 GC。在简单的基准测试中，大型哈希的哈希表插入改进了 10 倍。

请注意，GC 行走问题不会影响 纯功能结构, ，也不是未装箱的数组（像大多数数据一样 平行阵列, ， 或者 向量-类似数组，在 Haskell 中。它也不影响存储在 C 堆上的哈希表（例如 朱迪）。这意味着它不会影响不使用命令式哈希表的日常 Haskellers。

如果您在 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 年，您可能应该只使用 哈希表 包，支持 一系列可变哈希表 原生地。

其他提示

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

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

哦，不要喂巨魔。

附：你自己做实验是很合理的，但也许没有必要，因为值得信赖的 Don Stewart 提出了一些不错的微基准 在他很好的回答中。以下是 Don 的回答的附录：

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

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

我对这个结果有点惊讶，但让我放心的是函数式数据结构的性能相当好。并证实了我的信念，在代码的实际使用条件下对代码进行基准测试确实值得。

简而言之，即使在最新的 GHC 中进行了修复，Haskell 仍然无法提供具有竞争力的高效字典（可变或不可变）。

Haskell 的哈希表是 比 C++ 和 .NET 等替代方案慢 32 倍 与 GHC 6.10。这部分是由于 GHC 垃圾收集器中的性能错误已在 GHC 6.12.2 中修复. 。但 Simon Marlow 的结果显示，性能仅提高了 5 倍，这仍然使 Haskell 的哈希表比大多数替代方案慢很多倍。

纯函数式替代方案也比像样的哈希表慢得多。例如， 哈斯克尔的 IntMap 比 .NET 的哈希表慢 10 倍.

使用 F# 2010 和 最新的Haskell平台2010.2.0.0 （昨天发布！）在运行 32 位 Windows Vista 的 2.0GHz E5405 Xeon 上使用 GHC 6.12.3 将 20M int->int 绑定插入到空哈希表中，我们发现 Haskell 的实时速度仍然比 F# 慢 29 倍CPU 时间慢 200 倍以上，因为 Haskell 会烧毁所有核心：

GHC 6.12.3 Data.HashTable: 42.8s (new!)
.NET hash table:            1.47s

如果您只运行短暂的微基准测试，您可以按照 Don Stewart 上面的建议禁用 GHC 垃圾收集器。通过要求一个如此大的婴儿代，以至于这个特定的程序永远无法填满它，他将 Haskell 哈希表的时间降低到只有 1.5 秒。然而，这完全破坏了托儿所生成的全部意义，并且会极大地降低其他代码的性能，因为新分配的值现在在缓存中总是冷的（这就是为什么托儿所生成通常是 L2 缓存的大小，比这个小几个数量级）。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top