6

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

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 中，而第二个程序将其花费在fmapLens.Family.State.Strictzoom中。使用图如下。这两个程序都将大约 70% 的时间用于垃圾收集。

难道我做错了什么？Prelude 功能是max不是不够严格？我不知道库函数是否不好，或者我是否使用错误的库！（应该是后者。）

为了完整起见，这里有一个 git repocabal install ，如果你想亲眼看看我在说什么，你可以克隆并运行它，这里是两个程序的内存使用情况：

程序 1 的内存使用情况 程序 2 的内存使用情况

4

1 回答 1

5

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

编辑：我发现了错误。 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 解析之后，您会得到 Ncat管道，这会为每个解析的元素增加 O(N) 开销。

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

编辑：我已经提交了一个拉取请求来解决第二个问题（你需要使用intercalate惰性字节串）。现在程序在两个版本的 5 KB 常量空间中运行：

在此处输入图像描述

在此处输入图像描述

于 2014-05-19T21:04:37.060 回答