[Haskell-cafe] Stack overflow

[Philip Armstrong]

On Thu, Feb 14, 2008 at 04:56:39AM -0800, Grzegorz Chrupala wrote:
>I have a very simple program which reads a Data.Map from a file using
>Data.Binary and Data.ByteString.Lazy, which gives stack overflow with files
>over a certain size. Any ideas of what might be causing it?
>
>You can try it with the small file (11M) at:
>http://computing.dcu.ie/~gchrupala/map.bin
>
>import System 
>import Data.Map
>import qualified Data.ByteString.Lazy as BS
>import Data.Binary
>main = do
>  [path] <- getArgs
>  m <- fmap decode (BS.readFile path)::IO (Map (Int,Maybe String) Int)
>  putStrLn . show . findMax $ m

Since no-one else has answered, I'll take a stab. 

Obiously, you have a stack leak due to laziness somewhere -- now
Data.Map is strict in it's keys, but lazy in it's values, and
Data.Binary is lazy so my suspicion would be that you're building up
lazy decode thunks for the value elements on the stack as the map is
being constructed.

If either decode or the Map construction were strict, you'd probably
be OK, but the combination is blowing the stack.

(Data.Binary serialises Maps by writing them out to a list of key,
value pairs in ascending key order. The Map can be reconstructed from
this list in O(N) time.)

In your specific example, you can replace the type for the result of
the decoding with IO [(Int,Maybe String),Int)] and evaluate the right
hand sides (with seq if necessary) before constructing the map from
the list, which will avoid the stack blowout.

In fact, a little experimentation has revealed that this:

   do
    [path] <- getArgs
    m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)]
    putStrLn . show . findMax . fromAscList $ m

will work just fine. No extra evaluation needed at all! I'll leave it
to the Haskell gurus to explain what's going on...

cheers, Phil

-- 
http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt