[Haskell-cafe] Stack, Heap and GHC

Brandon Moore brandonm at yahoo-inc.com
Thu Dec 14 18:42:41 EST 2006


David Roundy wrote:
> On Thu, Dec 14, 2006 at 04:00:53PM +0100, Felix Breuer wrote:
>   
>> Hello everyone,
>>
>> I have been trying to run a Haskell program of mine that does an
>> extensive computation with very large amounts of data. I compiled the
>> program with ghc --make. When I run it it terminates after some time
>> with the message:
>>
>>   Stack space overflow: current size 8388608 bytes.
>>   Use `+RTS -Ksize' to increase it.
>>
>> The program isn't that well written so the overflow did not surprise me,
>> I expected that it might run out of memory. What did surprise me was the
>> *stack* overflow. I do not use recursion in my program except for a
>> couple of fold operations over very large lists. So I have a number of
>> questions:
>>     
>
> Here's a little program that can illustrate this issue:
>
> import Data.List
>
> largenum = 1000000
>
> main = do putStrLn "strict foldl1"
>           print $ foldl1' (\a b -> a + 1) $ [1..largenum]
>           putStrLn "lazy foldl1"
>           print $ foldl1 (\a b -> a + 1) $ [1..largenum]
>
>
> It gets through the first one, but not the second call, which differs only
> in the strictness of the foldl.  You can make it use up more memory by
> making largenum a hundred times bigger, in which case for some reason it
> doesn't seem to have a stack error (although it hasn't completed on my
> computer, and uses something like 2G of memory).  Perhaps the thunks are
> placed on the heap, and only when they are actually evaluated does anything
> go onto the stack?
>   
As I understand, that's exactly how it works. If you enter a thunk, all 
the computation
you need to do to force it uses the stack. In particular, if your thunk 
looks like
(1 + (1 + (1 + ...))) then it's wrapping up a huge chunk of evaluation 
that has to be done
all at once, and probably blows out the stack when it evaluates 1, 
pushes it and starts evaluating
the right argument, which means evaluating a 1, pushing it, and starting 
the right argument ...

Brandon




More information about the Haskell-Cafe mailing list