Reading large file in haskell?

Question

i've been trying to read a large file in haskell.

I need to compress it using a custom algorithm for a university project. Everything works fine untill i start to compress big files.

I extracted what was going wrong out of my program, and i expose it here in the form of a "Hello big file":

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))

I name this file Test.hs, then do the following:

$ 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

Could anyone please explain why i need 500 Megabytes of RAM and 30 seconds of CPU in order to browse a miserable 5 Megabytes file ? Please what am i doing wrong ? Why isn't the [word8] bufferized as the ByteString documentation states. And how to fix this ?

I tried to define my own tail recursive fold instead of foldl, foldr, or foldl'. I tried to unfreeze the thunks as well with seq. I got no result so far.

Thanks for any kind of help because i'm stuck.

Answer 1

The construct "seq x x" is always useless. If y = seq x x and I force y then this forces x then returns x. This is equivalent to y=x and forcing y. Thus "seq forceEval forceEval" does nothing more than "forceEval".

The error with your use of a fold is a common one.

You are using a fold to perform a count of the bytes in the input. You should be using a strict left fold for such a sum, but your hand written fold is a lazy left fold. The (acc+1) is not getting evaluated, so it builds 5 million nested applications: (((...(0+1)+1)+1)+1)+1)+1)...+1). Then it is forced when printing, and the evaluation tries to descend into 5 million parentheses.

Thus the pending stack has one entry for each Word8. For short inputs it reaches the end and sees 0. For long inputs it runs out of stack space with GHC because the creators and most users of GHC think that trying to allocate 5 million stack frames is usually a design error by the programmer.

I predict that you can use "seq" to fix this:

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