Why is Data.Binary's encodeFile not acting lazy?

Question

In GHCI, I run this simple test:

encodeFile "test" [0..10000000]

The line runs really quickly (<10sec), but my memory usage shoots up to ~500MB before it finishes. Shouldn't encodeFile be lazy since it uses ByteString.Lazy?

Edit: Roman's answer below is great! I also want to point out this answer to another question, that explains why Data.Binary does strict encoding on lists and provides a slightly more elegant work around.

In general, GHCi is not a good choice for any kind of profiling. It doesn't do any kind of optimization and interprets Haskell code, so the memory usage and performance characteristics are often completely different compared to compiled Haskell. You should compile with `ghc -O2` and see if the problem repeats there. — shang, Jul 26 '12 at 05:56
I found the problem in a program compiled with ghc -O2, and worked it down to this. — Mike Izbicki, Jul 26 '12 at 17:01

score 9 · Accepted Answer · edited Jul 26 '12 at 11:40

Here's how serialization of lists is defined:

instance Binary a => Binary [a] where
    put l  = put (length l) >> mapM_ put l

That is, first serialize the length of the list, then serialize the list itself.

In order to find out the length of the list, we need to evaluate the whole list. But we cannot garbage-collect it, because its elements are needed for the second part, mapM_ put l. So the whole list has to be stored in memory after the length is evaluated and before the elements serialization starts.

Here's how the heap profile looks like:

profile

Notice how it grows while the list is being built to compute its length, and then decreases while the elements are serialized and can be collected by the GC.

So, how to fix this? In your example, you already know the length. So you can write a function which takes the known length, as opposed to computing it:

import Data.Binary
import Data.ByteString.Lazy as L
import qualified Data.ByteString as B
import Data.Binary.Put

main = do
  let len = 10000001 :: Int
      bs = encodeWithLength len [0..len-1]
  L.writeFile "test" bs

putWithLength :: Binary a => Int -> [a] -> Put
putWithLength len list =
  put len >> mapM_ put list

encodeWithLength :: Binary a => Int -> [a] -> ByteString
encodeWithLength len list = runPut $ putWithLength len list

This program runs within 53k of heap space.

You can also include a safety feature into putWithLength: compute the length while serializing the list, and check with the first argument in the end. If there's a mismatch, throw an error.

Exercise: why do you still need to pass in the length to putWithLength instead of using the computed value as described above?

+1 for showing the heap profile (and being correct, of course) — alternative, Jul 26 '12 at 11:54
Exercise answer: because the format requires the length to be the first thing in the encoding, but you won't have the computed length until the very end. — Mike Izbicki, Jul 26 '12 at 17:03

Why is Data.Binary's encodeFile not acting lazy?

1 Answers1