GHC的垃圾收集RTS选项

Question

我有一个Haskell程序,它处理一个文本文件并构建一个Map(有几百万个元素).整件事可以运行2-3分钟.我发现调整-H和-A选项会对运行时间产生很大影响.

有关于RTS的这个功能的文档,但是对我来说这是一个很难读的,因为我不知道GC理论的算法和术语.我正在寻找一个技术性较低的解释,最好是针对Haskell/GHC.是否有关于为这些选项选择合理值的参考？

编辑:这是代码,它为给定的单词列表构建一个trie.

buildTrie :: [B.ByteString] -> MyDFA 
buildTrie l = fst3 $ foldl' step (emptyDFA, B.empty, 1) $ sort $ map B.reverse l where
    step :: (MyDFA , B.ByteString, Int) -> B.ByteString -> (MyDFA , B.ByteString, Int)
    step (dfa, lastWord, newIndex) newWord = (insertNewStates, newWord, newIndex + B.length newSuffix) where            
        (pref, lastSuffix, newSuffix) = splitPrefix lastWord newWord
        branchPoint = transStar dfa pref

        --new state labels for the newSuffix path
        newStates = [newIndex .. newIndex + B.length newSuffix - 1]
        --insert newStates
        insertNewStates = (foldl' (flip insertTransition) dfa $ zip3 (branchPoint:init newStates) (B.unpack newSuffix) newStates)

Answer 1

一般来说,垃圾收集是一种空间/时间权衡.为GC提供更多空间,所需时间更短.还有(许多)其他因素在起作用,特别是缓存,但空间/时间权衡是最重要的因素.

权衡如下:程序分配内存直到达到某个限制(由GC的自动调整参数决定,或通过RTS选项明确决定).达到限制时,GC会跟踪程序当前使用的所有数据,并回收不再需要的数据使用的所有内存.延迟此过程的时间越长,同时数据就越不可达("死"),因此GC会避免跟踪该数据.延迟GC的唯一方法是使更多内存可用于分配; 因此,更多的内存等于更少的GC,等于更低的GC开销.粗略地说,GHC的-H选项允许您设置GC使用的内存量的下限,因此可以降低GC开销.

GHC使用分代GC,这是对基本方案的优化,其中堆被分成两代或更多代.对象被分配到"年轻"一代,而那些活得足够长的对象被提升为"老一代"(在2代设置中).年轻一代比老一代更频繁地收集,其想法是"大多数物品都很年轻",所以年轻一代的收藏很便宜(他们没有追踪太多数据),但他们回收了大量的记忆.粗略地说,-A选项设置年轻代的大小 - 即在收集年轻代之前将分配的内存量.

-A的默认值为512k:最好让年轻一代保持小于L2缓存,如果超过L2缓存大小,性能通常会下降.但是,相反的方向是GC空间/时间权衡:使用非常大的年轻代可能会通过减少GC必须完成的工作量来超过缓存优势.这并不总是发生,它取决于应用程序的动态,这使GC很难自动调整自身.-H选项还会增加年轻代的大小,因此也会对缓存使用产生负面影响.

底线是:玩弄选项,看看哪些有效.如果你有足够的内存,你很可能通过使用-A或-H来提高性能,但不一定如此.

Answer 2

对于较小的数据集,可能会重现该问题,从而更容易看到正在发生的事情.特别是,我建议熟悉分析:

• Real World Haskell书中的剖析章节提供了一个很好的概述,包括可能遇到的典型问题
• GHC手册中的剖析章节记录了可用的功能

然后,检查您看到的内存配置文件是否符合您的期望(您无需了解所有分析选项以获取有用的图形).严格foldl'与非严格元组作为累加器的组合将是我要看的第一件事:如果元组的组件没有被强制,那么递归正在构建未评估的表达式.

顺便说一句,你可以通过手工评估你的代码来获得真正微小的数据集,从而建立一个关于这些事情的良好直觉.一些迭代就足以看出表达式是否以适合您的应用程序的方式得到评估或保持不被评估.