39

我有一个 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)
4

2 回答 2

72

一般来说，垃圾收集是空间/时间的权衡。给 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 来提高性能，但不一定。

于 2010-07-03T19:56:00.140 回答
8

对于较小的数据集，可能会重现该问题，这样更容易看到正在发生的事情。特别是，我建议熟悉分析：

然后，检查您看到的内存配置文件是否符合您的预期（您无需了解所有配置文件选项即可获得有用的图表）。foldl'作为累加器的严格元组与非严格元组的组合将是我首先要看的：如果不强制元组的组件，则该递归正在构建未评估的表达式。

顺便说一句，您可以通过尝试手动评估您的代码以获得非常小的数据集来建立对此类事情的良好直觉。几次迭代就足以查看表达式是否以适合您的应用程序的方式被评估或保持未评估。

于 2010-07-03T21:47:58.193 回答