titulo - IO sobre archivos grandes en haskell: problema de rendimiento

modificar tags mkv

Question

Estoy intentando trabajar con archivos grandes usando Haskell. Me gustaría explorar un byte de archivo de entrada después de un byte y generar un byte de salida después del byte. Por supuesto, necesito que el IO se almacene con bloques de tamaño razonable (unos pocos KB). No puedo hacerlo, y necesito tu ayuda, por favor.

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

main :: IO () 
main =     
    do         
        args <- System.getArgs         
        let filename = head args         
        byteString <- BL.readFile filename         
        let wordsList = BL.unpack byteString         
        let foldFun acc word = doSomeStuff word : acc
        let wordsListCopy = foldl'' foldFun [] wordsList
        let byteStringCopy = BL.pack (reverse wordsListCopy)
        BL.writeFile (filename ++ ".cpy") byteStringCopy
    where
        doSomeStuff = id

TestCopy.hs este archivo TestCopy.hs , luego hago lo siguiente:

$ ls -l *MB
-rwxrwxrwx 1 root root 10000000 2011-03-24 13:11 10MB
-rwxrwxrwx 1 root root  5000000 2011-03-24 13:31 5MB
$ ghc --make -O TestCopy.hs 
[1 of 1] Compiling Main             ( TestCopy.hs, TestCopy.o )
Linking TestCopy ...
$ time ./TestCopy 5MB

real    0m5.631s
user    0m1.972s
sys 0m2.488s
$ diff 5MB 5MB.cpy
$ time ./TestCopy 10MB 

real    3m6.671s
user    0m3.404s
sys 1m21.649s
$ diff 10MB 10MB.cpy 
$ time ./TestCopy 10MB +RTS -K500M -RTS

real    2m50.261s
user    0m3.808s
sys 1m13.849s
$ diff 10MB 10MB.cpy 
$ 

Mi problema: hay una gran diferencia entre un archivo de 5 MB y uno de 10 MB. Me gustaría que las actuaciones sean lineales en el tamaño del archivo de entrada. Por favor, ¿qué estoy haciendo mal y cómo puedo lograrlo? No me importa usar cadenas de bytes vagas o cualquier otra cosa, siempre y cuando funcione, pero tiene que ser una biblioteca estándar de ghc.

Precisión: es para un proyecto universitario. Y no estoy tratando de copiar archivos. La función doSomeStuff realizará acciones de compresión / descompresión que tengo que personalizar.

Answer 1

Para el procesamiento de entrada fragmentada, usaría el paquete del enumerador .

import Data.Enumerator
import Data.Enumerator.Binary (enumFile)

Usamos cadenas de bytes

import Data.ByteString as BS

y IO

import Control.Monad.Trans (liftIO)
import Control.Monad (mapM_)
import System (getArgs)

Su función principal podría ser similar a la siguiente:

main =
  do (filepath:_) <- getArgs
     let destination
     run_ $ enumFile filepath $$ writeFile (filepath ++ ".cpy")

enumFile lee 4096 bytes por fragmento y los pasa a writeFile, que lo anota.

enumWrite se define como:

enumWrite :: FilePath -> Iteratee BS.ByteString IO ()
enumWrite filepath =
  do liftIO (BS.writeFile filepath BS.empty)   -- ensure the destination is empty
     continue step
  where
  step (Chunks xs) =
    do liftIO (mapM_ (BS.appendFile filepath) xs)
       continue step
  step EOF         = yield () EOF

Como puede ver, la función de paso toma trozos de cadenas de bytes y los agrega al archivo de destino. Estos fragmentos tienen el tipo Stream BS.Bytestring, donde Stream se define como:

data Stream a = Chunks [a] | EOF

En un paso EOF termina, produciendo ().

Para tener una lectura mucho más elaborada sobre esto yo personalmente recomiendo el tutorial de Michael Snoymans

Los números

$ time ./TestCopy 5MB
./TestCopy 5MB  2,91s user 0,32s system 96% cpu 3,356 total

$ time ./TestCopy2 5MB
./TestCopy2 5MB  0,04s user 0,03s system 93% cpu 0,075 total

Eso es una gran mejora. Ahora, para implementar su pliegue, probablemente desee escribir un Enumeratee, que se utiliza para transformar una secuencia de entrada. Afortunadamente, ya existe una función de mapa definida en el paquete del enumerador, que puede modificarse para su necesidad, es decir, puede modificarse para transferir el estado.

En la construcción del resultado intermedio

Usted construye la Lista de palabras en orden inverso y la invierte después. Creo que las listas de diferencias hacen un mejor trabajo, porque los anexos toman solo O (1) tiempo debido al hecho de que agregar es solo una composición de función. No estoy seguro si toman más espacio sin embargo. Aquí hay un boceto de las listas de diferencias:

type DList a = [a] -> [a]

emptyList :: DList a
emptyList = id

snoc :: DList a -> a -> DList a
snoc dlist a = dlist . (a:)

toList :: DList a -> [a]
toList dlist = dlist []

Esta respuesta probablemente ya no sea necesaria, pero la agregué para completarla.

Answer 2

Supongo que este es un seguimiento de la lectura de archivos grandes en Haskell. de ayer.

Intente compilar con "-rtsopts -O2" en lugar de solo "-O".

Usted afirma que "me gustaría explorar un byte de archivo de entrada después de un byte y generar un byte de salida después de un byte". pero su código lee la entrada completa antes de intentar crear cualquier salida. Esto no es muy representativo del objetivo.

Con mi sistema veo "ghc -rtsopts --make -O2 b.hs" dando

(! 741)-> time ./b five
real 0m2.789s user 0m2.235s sys 0m0.518s
(! 742)-> time ./b ten
real 0m5.830s user 0m4.623s sys 0m1.027s

Que ahora parece lineal para mí.