Il modo più efficiente per cercare in un file di grandi dimensioni

Question

Qual è il modo più efficiente per elaborare file binari di grandi dimensioni in Haskell?

La risposta standard è leggere l'intero file come un ByteString pigro e quindi utilizzare qualcosa come il pacchetto binario per scrivere un parser su di esso. Ci sono un paio di problemi con quella ...

In primo luogo, librerie come binario non veramente gestire analizza il fallimento, e sono esplicitamente aspettandosi analisi a fallire a volte.

In secondo luogo, non sto analizzando l'intero contenuto del file. Ho intenzione di saltare molti pezzi di esso. E leggere i gigabyte di dati dal disco alla RAM solo per fare in modo che il garbage collector lo butta via di nuovo sembra piuttosto poco performante.

In relazione a ciò, devo essere in grado di dire se il salto che voglio eseguire mi porterà alla fine del file o meno (ed errore se lo fa).

Potrebbe anche essere necessario cercare indietro, o forse in uno specifico byte offset all'interno del file, che non sembra essere ben supportato da un approccio ByteString pigro. (C'è un grave pericolo di finire per contenere l'intero file nella RAM.)

L'alternativa, ovviamente, è leggere singoli byte uno alla volta, intercalati con i comandi hSeek. Ma ora il problema è: quanto è efficiente la lettura di un file un byte alla volta? Sembra che potrebbe anche essere piuttosto lento. Non sono sicuro che sia hSetBuffering abbia un effetto su questo. (?)

Quindi, naturalmente, c'è mmap. Ma sembra che impazzire il sistema di memoria virtuale se usato su file di grandi dimensioni. (Che è strano, considerando che è l'intero scopo per esso esistente ...)

Cosa pensiamo, gente? Qual è il modo migliore per avvicinarsi a questo, in termini di prestazioni I/O e manutenibilità del codice?

Answer 1

Avevo un problema simile quando si lavora su parser pdf. Inizialmente ho usato il pacchetto iteratee (è supports random access). AFAIK è l'unica libreria IO con supporto IO casuale.

Il mio current approach si basa sul pacchetto io-streams. L'ho trovato più comodo. Le prestazioni sono sufficienti, integrazione attoparsec, inclusi molti combinatori.

Ecco un esempio di base come utilizzare iteratee per IO casuale:

shum@shum-laptop:/tmp/shum$ cat test.hs 

import qualified Data.Iteratee as I 
import qualified Data.Attoparsec.Iteratee as I 
import qualified Data.Attoparsec.Char8 as P 
import Control.Monad.IO.Class 
import System.Environment 

main :: IO() 
main = do 
    [file] <- getArgs 
    flip I.fileDriverRandom file $ do 
    I.seek 20 
    num1 <- I.parserToIteratee P.number 
    liftIO $ print num1 
    I.seek 10 
    num2 <- I.parserToIteratee P.number 
    liftIO $ print num2 
shum@shum-laptop:/tmp/shum$ cat in.data 
111111111 
222222222 
333333333 
shum@shum-laptop:/tmp/shum$ runhaskell test.hs in.data 
333333333 
222222222 
shum@shum-laptop:/tmp/shum$