修复一个特别难以发现的Haskell空间泄漏问题

Question

在我对一些用于将推文数据分解为n元组的Haskell代码进行了最后一次性能优化之后，我遇到了一个空间泄漏的问题。当我进行性能分析时，GC使用了大约60-70%的进程，并且有很多内存被拖累。希望一些Haskell大牛能够指出我的错误所在。

{-# LANGUAGE OverloadedStrings, BangPatterns #-}
import Data.Maybe
import qualified Data.ByteString.Char8 as B
import qualified Data.HashMap.Strict as H
import Text.Regex.Posix
import Data.List
import qualified Data.Char as C

isClassChar a = C.isAlphaNum a || a == ' ' || a == '\'' ||
                a == '-' || a == '#' || a == '@' || a == '%'

cullWord :: B.ByteString -> B.ByteString
cullWord w = B.map C.toLower $ B.filter isClassChar w

procTextN :: Int -> B.ByteString -> [([B.ByteString],Int)]
procTextN n t = H.toList $ foldl' ngram H.empty lines
  where !lines        = B.lines $ cullWord t
        ngram tr line = snd $ foldl' breakdown (base,tr) (B.split ' ' line)
        base          = replicate (n-1) ""

breakdown :: ([B.ByteString], H.HashMap [B.ByteString] Int) -> B.ByteString -> ([B.ByteString],H.HashMap [B.ByteString] Int)
breakdown (st@(s:ss),tree) word =
  newStack `seq` expandedWord `seq` (newStack,expandedWord)
      where newStack     = ss ++ [word]
            expandedWord = updateWord (st ++ [word]) tree

updateWord :: [B.ByteString] -> H.HashMap [B.ByteString] Int -> H.HashMap [B.ByteString] Int
updateWord w h = H.insertWith (+) w 1 h

main = do
  test2 <- B.readFile "canewobble"
  print $ filter (\(a,b) -> b > 100) $ 
     sortBy (\(a,b) (c,d) -> compare d b) $ procTextN 3 test2

- Erik Hinton

---

你能提供一些输入数据供我们测试吗？ - Mikhail Glushenkov

哦，那会有帮助！这是我的测试数据：https://raw.github.com/esmooov/stash/master/canewobble - Erik Hinton

你有计算过内存中要存储的数据的内存占用吗？可以参考Johan Tibell的非常有用的博客文章http://blog.johantibell.com/2011/06/memory-footprints-of-some-common-data.html。在主程序中，如果你正在执行排序操作，由于排序本质上是一种内存密集型操作，如果你正在收集大量数据进行排序，那么将会占用大量内存。 - stephen tetley

@stephen 大部分时间都花在procTextN上，移除sortBy并没有太大帮助。 - Mikhail Glushenkov

你的类型声明非常长，所以代码不太适合问题的格式（并且通常看起来很糟糕）。如果你无限制地导入 B.ByteString 和 H.HashMap（像这样：import Data.HashMap.Strict(HashMap) 除了你现在有的限定导入之外），那会帮助很多。 - HaskellElephant

@HaskellElephant 修复这个问题的简单方法是使用类型别名，就像我在这里所做的那样。 - Mikhail Glushenkov

Answer 1

一项小的优化是在排序之前使用HashMap.filter过滤数据。这帮助我减少了2秒的执行时间。另外，我使用序列(Data.Sequence)代替列表(没有明显的差异 :-( )。我的版本可以在这里找到。

查看堆剖面图，我不认为你的程序存在空间泄漏： 。

您只是在内存中构建了一个相当大的哈希表（377141个键值对），然后在一些处理之后将其丢弃。根据Johan's post，这种大小的哈希表需要大约5*N + 4*(N-1)个字 = 3394265*4字节 ~= 13 MiB，这与堆剖面显示的结果相符。其余空间由键和值占用。在我的机器上，GC花费的时间约为40％，考虑到您正在不断更新哈希表和临时“堆栈”，而没有对数据进行任何计算密集型操作，这听起来并不不合理。既然您唯一需要哈希表的操作是insertWith，也许最好使用可变数据结构？ 更新: 我已经使用可变哈希表重写了您的程序。有趣的是，速度差异并不大，但内存使用略有改善：

正如您所看到的，分配给哈希表的块的大小在执行过程中保持不变。

- Mikhail Glushenkov

---

Data.Sequence通常是创建堆栈时首选的数据结构。列表特别不适合用作堆栈。 - John L

是的，但这里所有的堆栈都非常小（3个元素），所以那并不是很重要。 - Mikhail Glushenkov

哦，这是一个非常好的回答。我有一些预感，可能只是过于多疑了，问题实际上是 HashMap 的大小太大了。我采取了您的建议，根据过滤器的建议，同时由于这种 ngramming 是丢失的，将 ngramming 分成 1MB 块，并在每轮中修剪 HashMap 中所有小值。现在，我可以在不到 200MB 的内存中处理多达 100MB 的文件。再次感谢大家！（附言：我正在考虑尝试使用可变哈希表，但是我总感觉在 Haskell 中使用可变数据结构感到内疚。有什么心理建议吗？哈！) - Erik Hinton

哇，非常感谢您提供可变哈希表的示例。这是一个很好的处理方式，并且有趣地说明了Haskell中可变数据结构的性能特征。我编写了一个并行化版本，但速度只快了一点点。有时候你能做的事情只有那么多。 - Erik Hinton