haskell - 在 Haskell 中折叠生产者/解析器时的空间爆炸

Question

假设我有一个这样的模块:

module Explosion where

import Pipes.Parse (foldAll, Parser, Producer)
import Pipes.ByteString (ByteString, fromLazy)
import Pipes.Aeson (DecodingError)
import Pipes.Aeson.Unchecked (decoded)
import Data.List (intercalate)
import Data.ByteString.Lazy.Char8 (pack)
import Lens.Family (view)
import Lens.Family.State.Strict (zoom)

produceString :: Producer ByteString IO ()
produceString = fromLazy $ pack $ intercalate " " $ map show [1..1000000]

produceInts :: 
    Producer Int IO (Either (DecodingError, Producer ByteString IO ()) ())
produceInts = view decoded produceString

produceInts' :: Producer Int IO ()
produceInts' = produceInts >> return ()

parseBiggest :: Parser ByteString IO Int
parseBiggest = zoom decoded (foldAll max 0 id)

'produceString' 函数是一个字节串生产者，我关心的是在它上面折叠一个解析以产生某种结果。

以下两个程序显示了通过将字节字符串解析为一系列 JSON 整数来解决在字节字符串中查找最大值问题的不同方法。

方案一:

module Main where

import Explosion (produceInts')
import Pipes.Prelude (fold)

main :: IO ()
main = do
    biggest <- fold max 0 id produceInts'
    print $ show biggest

方案二:

module Main where

import Explosion (parseBiggest, produceString)
import Pipes.Parse (evalStateT)

main :: IO ()
main = do
    biggest <- evalStateT parseBiggest produceString
    print $ show biggest

不幸的是，当我分析它们时，这两个程序总共占用了大约 200MB 的内存，我希望使用流解析器可以解决这个问题。第一个程序将大部分时间和内存 (> 70%) 用于 (^.)来自 Lens.Family，而第二个花费在 fmap ，由 zoom 调用来自 Lens.Family.State.Strict。使用图如下。这两个程序都将大约 70% 的时间用于垃圾收集。

难道我做错了什么？是前奏功能 max不够严格？我不知道库函数是否不好，或者我是否使用错误的库! (应该是后者。)

为了完整起见， here's a git repo你可以克隆和运行 cabal install如果您想亲眼看看我在说什么，这是两个程序的内存使用情况:

Answer 1

将严格的字节串包装在单个 yield 中不会让它变得懒惰。您必须产生较小的 block 才能获得任何流式传输行为。

编辑:我发现了错误。 pipes-aeson内部使用 consecutively函数定义如下:

consecutively parser = step where
    step p0 = do
      (mr, p1) <- lift $
         S.runStateT atEndOfBytes (p0 >-> PB.dropWhile B.isSpaceWord8)
      case mr of
         Just r  -> return (Right r)
         Nothing -> do
            (ea, p2) <- lift (S.runStateT parser p1)
            case ea of
               Left  e -> return (Left (e, p2))
               Right a -> yield a >> step p2

有问题的行是带有 PB.dropWhile 的行。 .这增加了与解析元素的数量成比例的二次放大。

发生的情况是，通过此计算的管道会累积一个新的 cat每次解析后管道下游。所以在 N 解析后你得到 N cat管道，这为每个解析的元素增加了 O(N) 开销。

我创建了 a Github issue解决这个问题。 pipes-aeson由 Renzo 维护，他之前已经解决了这个问题。

编辑:我已经提交了 pull request解决第二个问题(对于惰性字节串，您需要使用 intercalate)。现在程序在两个版本的 5 KB 常量空间中运行: