Explosión espacial al doblar a los productores/analizadores en Haskell

memory stream

Question

Suponiendo que tengo un módulo como este:

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)

La función ''produceString'' es un productor de bytes, y me preocupa doblar un análisis para producir algún tipo de resultado.

Los siguientes dos programas muestran diferentes formas de abordar el problema de encontrar el valor máximo en la cadena de bytes analizándolo como una serie de entradas JSON.

Programa 1:

module Main where

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

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

Programa 2:

module Main where

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

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

Desafortunadamente, ambos programas consumen unos 200MB de memoria total cuando los perfilo, un problema que esperaba que el uso de los analizadores de transmisión pudiera resolver. El primer programa pasa la mayor parte de su tiempo y memoria (> 70%) en (^.) Desde Lens.Family, mientras que el segundo lo gasta en fmap , llamado por zoom desde Lens.Family.State.Strict. Los gráficos de uso están debajo. Ambos programas dedican aproximadamente el 70% de su tiempo a la recolección de basura.

¿Estoy haciendo algo mal? ¿La función de preludio no es lo suficientemente estricta? No puedo decir si las funciones de la biblioteca son malas o si estoy usando la biblioteca equivocada. (Probablemente sea este último)

Para completar, aquí hay un repositorio git que puedes clonar y ejecutar la cabal install si quieres ver de lo que estoy hablando de primera mano, y aquí está el uso de la memoria de los dos programas:

Answer 1

Envolver una cadena de bytes estricta en un solo yield no lo hace perezoso. Debes ceder trozos más pequeños para obtener cualquier comportamiento de transmisión.

Editar: encontré el error. pipes-aeson usa internamente una función consecutively definida así:

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

La línea problemática es la que tiene PB.dropWhile . Esto agrega una explosión cuadrática proporcional a la cantidad de elementos analizados.

Lo que sucede es que la tubería que se enhebra a través de este cálculo acumula un nuevo tubo cat abajo de cada análisis. Entonces, después de N analiza, obtienes N cat pipes, que agrega O (N) sobrecarga a cada elemento analizado.

Creé un problema de Github para arreglar esto. pipes-aeson es mantenido por Renzo y él ha solucionado este problema antes.

Editar: He enviado una solicitud de extracción para solucionar un segundo problema (necesitabas usar el intercalate para cadenas de bytes perezosas). Ahora el programa se ejecuta en un espacio constante de 5 KB para ambas versiones: