io - Leyendo archivo grande en haskell?

lazy-evaluation bytestring

Question

He estado tratando de leer un archivo grande en haskell.

Necesito comprimirlo usando un algoritmo personalizado para un proyecto universitario. Todo funciona bien hasta que empiezo a comprimir archivos grandes.

Extraje lo que estaba saliendo mal de mi programa, y ​​lo expongo aquí en la forma de un "Hola gran archivo":

import System
import qualified Data.ByteString.Lazy as BL
import Data.Word

fold_tailrec :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec _ acc [] =
    acc
fold_tailrec foldFun acc (x : xs) =
    fold_tailrec foldFun (foldFun acc x) xs

fold_tailrec'' :: (a -> b -> a) -> a -> [b] -> a
fold_tailrec'' _ acc [] =
    acc
fold_tailrec'' foldFun acc (x : xs) =
    let forceEval = fold_tailrec'' foldFun (foldFun acc x) xs in
    seq forceEval forceEval

main :: IO ()
main =
    do
        args <- System.getArgs
        let filename = head args
        byteString <- BL.readFile filename
        let wordsList = BL.unpack byteString
        -- wordsList is supposed to be lazy (bufferized)
        let bytesCount = fold_tailrec (/acc word -> acc + 1) 0 wordsList
        print ("Total bytes in " ++ filename ++ ": " 
               ++ (show bytesCount))

Nombro este archivo Test.hs, luego hago lo siguiente:

$ ls -l toto
-rwxrwxrwx 1 root root 5455108 2011-03-23 19:08 toto
$ ghc --make -O Test.hs
[1 of 1] Compiling Main             ( Test.hs, Test.o )
Linking Test ...
$ ./Test toto
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS'' to increase it.
$ ./Test toto +RTS -K50M -RTS
Stack space overflow: current size 50000000 bytes.
Use `+RTS -Ksize -RTS'' to increase it.
$ ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"
$ time ./Test toto +RTS -K500M -RTS
"Total bytes in toto: 5455108"

real    0m33.453s
user    0m8.917s
sys 0m10.433s

¿Podría alguien explicar por qué necesito 500 Megabytes de RAM y 30 segundos de CPU para buscar un miserable archivo de 5 Megabytes? Por favor, ¿qué estoy haciendo mal? ¿Por qué no está [word8] almacenado en búfer como indica la documentación de ByteString? ¿Y cómo solucionar esto?

Intenté definir mi propio pliegue recursivo de la cola en lugar de foldl, foldr o foldl ''. Traté de descongelar los trozos también con seq. No tengo ningún resultado hasta ahora.

Gracias por cualquier tipo de ayuda porque estoy atascado.

Answer 1

La construcción "seq xx" siempre es inútil. Si y = seq xx y yo fuerzo y entonces esto fuerza x y luego devuelve x. Esto es equivalente a y = x y forzar y. Así, "seq forceEval forceEval" no hace nada más que "forceEval".

El error con el uso de un pliegue es común.

Está utilizando un pliegue para realizar un recuento de los bytes en la entrada. Debería usar un pliegue izquierdo estricto para tal suma, pero su pliegue escrito a mano es un pliegue izquierdo perezoso. El (acc + 1) no se está evaluando, por lo que genera 5 millones de aplicaciones anidadas: (((... (0 + 1) +1) +1) +1) +1) +1) ... + 1 ). Luego se fuerza al imprimir, y la evaluación intenta descender en 5 millones de paréntesis.

Por lo tanto, la pila pendiente tiene una entrada para cada Word8. Para las entradas cortas, llega al final y ve 0. Para las entradas largas, se queda sin espacio de pila con GHC porque los creadores y la mayoría de los usuarios de GHC piensan que intentar asignar 5 millones de cuadros de pila suele ser un error de diseño del programador.

Predigo que puedes usar "seq" para arreglar esto:

fold_tailrec'' foldFun acc (x : xs) =
    let acc'' = foldFun acc x
    in seq acc'' (fold_tailrec'' foldFun acc'' xs)