Ale*_*tto 50 haskell hashtable ghc
我读到Haskell中的哈希表存在性能问题(2006 年的Haskell-Cafe和2009年的Flying Frog Consultancy的博客),因为我喜欢Haskell,所以我很担心.
那是一年前,现在的状况是什么(2010年6月)？GHC中是否修复了"哈希表问题"？
Don*_*art 135
问题是垃圾收集器需要遍历可变指针数组("盒装数组"),寻找可能准备解除分配的数据的指针.盒装可变数组是实现哈希表的主要机制,因此特定结构显示了GC遍历问题.这在许多语言中都很常见.症状是垃圾收集过多(GC中花费的时间高达95%).
修复是在GC中为可变指针数组实现"卡标记",这些指针发生在2009年末.现在,在Haskell中使用可变指针数组时,不应该看到过多的GC.在简单的基准测试中,大散列的哈希表插入提高了10倍.
请注意,GC行走问题不会影响纯粹的功能结构,也不会影响Haskell中的未装箱数组(如大多数数据并行数组或类似矢量的数组.也不会影响存储在C堆上的哈希表(如judy).它不会影响日常Haskeller不使用命令式哈希表.
如果你在Haskell中使用哈希表,你现在不应该发现任何问题.例如,这是一个简单的散列表程序,它将1000万个int插入到散列中.我将进行基准测试,因为原始引文不提供任何代码或基准.
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包,它本身支持一系列可变哈希表.
Nor*_*sey 26
像这样的问题只能通过实验来解决.但如果你没有时间或金钱做实验,你必须问别人他们的想法.当您这样做时,您可能需要考虑来源并考虑所提供的信息是否已经过任何方式的审查或审查.
Jon Harrop提出了一些有关Haskell的有趣主张.我建议您在Google Groups和其他地方搜索Harrop在Haskell,Lisp和其他函数语言方面的专业知识.您还可以阅读Chris Okasaki和Andy Gill在Haskell的Patricia树上的作品,看看他们的专业知识是如何被看到的.您还可以找到第三方已检查过哪些索赔(如果有).然后,您可以自己决定如何认真地采取不同的人对不同功能语言的表现的主张.
哦,不要喂巨魔.
PS你做自己的实验是非常合理的,但也许没有必要,因为可信赖的唐·斯图尔特在他的好答案中提出了一些不错的微基准.这是Don回答的附录:
附录:在AMD Phenom 9850黑色版上使用Don Stewart的代码,主频为2.5GHz,4GB RAM,32位模式,带ghc -O,
IntMap比哈希表快40%.IntMap.IntMap是快四倍比哈希表(CPU时间)或者快两倍的挂钟时间.我对这个结果感到有点惊讶,但确信功能数据结构表现相当不错.并且我相信在我们将要使用的实际条件下对您的代码进行基准测试确实是值得的.
In short, even with the fix in the latest GHC, Haskell is still incapable of providing a dictionary (mutable or immutable) that is competitively efficient.
Haskell's hash tables were 32× slower than alternatives like C++ and .NET with GHC 6.10. That was partly due to a performance bug in the GHC garbage collector that was fixed for GHC 6.12.2. But Simon Marlow's results there show only a 5× performance improvement which still leaves Haskell's hash tables many times slower than most alternatives.
Purely functional alternatives are also much slower than a decent hash table. For example, Haskell's IntMap is 10× slower than .NET's hash table.
Using F# 2010 and the latest Haskell Platform 2010.2.0.0 (released yesterday!) with GHC 6.12.3 on this 2.0GHz E5405 Xeon running 32-bit Windows Vista to insert 20M int->int bindings into an empty hash table we find that Haskell is still 29× slower than F# in real time and over 200× slower in terms of CPU time because the Haskell burns all cores:
GHC 6.12.3 Data.HashTable: 42.8s (new!) .NET hash table: 1.47s
Provided you run only short-lived microbenchmarks you can disable the GHC garbage collector as Don Stewart suggests above. By asking for a nursery generation so large that this particular program will never fill it, he brought the time for the Haskell hash table down to only 1.5s here. However, this completely undermines the whole point of having a nursery generation and will massively degrade the performance of other code because freshly allocated values will now always be cold in the cache (which is why the nursery generation is typically the size of the L2 cache, orders of magnitude smaller than this).