简单解析器运行内存不足

Question

我想了解为什么这个简单的解析器会在处理大文件时内存不足。我真的不知道我做错了什么。

import Data.Attoparsec.ByteString.Char8
import qualified Data.Attoparsec.ByteString.Lazy as Lazy
import System.Environment
import qualified Data.ByteString.Lazy as B
import Control.Applicative

parseLine :: Parser String
parseLine = manyTill' anyChar (endOfLine <|> endOfInput)

parseAll :: Parser [Int]
parseAll = manyTill' 
        (parseLine >> (return 0)) -- discarding what's been read
        endOfInput

main :: IO()
main = do 
        [fn] <- getArgs
        text <- B.readFile fn

        case Lazy.parse parseAll text of
                Lazy.Fail _ _ _ -> putStrLn "bad"
                Lazy.Done _ _ -> putStrLn "ok"

我是运行程序：

 runhaskell.exe test.hs x.log

输出：

test.hs: Out of memory

x.log 大小约为 500MB。我的机器有 16GB 的内存。

Answer 1

如果您查看 the documentation of attoparsec，您会注意到有一个类似的示例，并附有以下注释：

Note the overlapping parsers anyChar and string "-->". While this will work, it is not very efficient, as it will cause a lot of backtracking.

使用 anyChar 的替代方法拒绝 endOfLine 接受的字符应该可以解决这个问题。例如

satisfy (\c -> c `notElem` ['\n', '\r'])

Answer 2

我不太熟悉 Attoparsec，但我认为您可能很难单独使用它来解析常量内存中的大文件。如果您将顶级解析器 parseAll 替换为：

parseAll :: Parser ()
parseAll = skipMany anyChar

并分析它，您会发现内存使用量仍然无限制地增长。（当我将您的代码转换为使用严格 ByteStrings 的增量阅读时，它没有任何区别。）

我认为问题是这样的：因为 Attoparsec 会自动回溯，所以它必须为 parseAll（您的版本或我的版本 - 这无关紧要）做好准备，以便像这样使用：

(parseAll <* somethingThatDoesntMatch) <|> parseDifferently

如果 parseAll 已经解析了 50 万行并到达结尾，somethingThatDoesntMatch 将导致它一直回溯到开头，然后用 parseDifferently 重新解析所有内容。因此，在解析完全完成之前，无法释放用于回溯的元信息和 ByteStrings 本身。

现在，您的解析器（以及我上面的示例）"obviously" 不需要以这种方式回溯，但 Attoparsec 不会推断出这一点。

我可以想出几种方法：

如果您正在解析兆字节而不是千兆字节，请考虑使用 Parsec，它仅在明确表示时回溯（例如，使用 try）。
使用手工制作的非回溯解析器将您的日志文件分解成行（或行块），然后运行您的 Attoparsec 解析器在每个 line/block 上完成。

简单解析器运行内存不足

Simple parser running out of memory

haskell

memory-leaks

attoparsec

简单解析器 运行 内存不足

Simple parser running out of memory

haskell

memory-leaks

attoparsec

简单解析器运行内存不足