[Haskell-cafe] Space leaks (was: How do I get a long iteration to run in constant space)

[Graham Klyne]

I've been starting to take note of discussion about space leaks in 
Haskell.  So far, it's not a topic that's bothered me, other than obvious 
programming errors, and I've never found the need to force strict 
evaluation of my Haskell programs.  I find myself wondering why this is.

Your comment about arithmetic expressions is telling:  the kind of program 
I have been writing (parsers, symbolic processing, etc.) performs almost no 
arithmetic.  (So far, I've used lists instead of arrays, so a usual source 
of arithmetic functions is missing.)

I've also worked with datasets that fit in memory, so failure to "stream" 
data hasn't been a problem.  I suspect that's the more pernicious case for 
space leaks, since the causes aren't always so obvious.

Are there any guidelines or warning signs to look out for that may be 
indicative of potential space-leak problems?  So far, I can think of:
- arithmetic results
- multiple uses of a large data value

#g
--

At 00:44 05/10/04 -0700, oleg at pobox.com wrote:

>I added two lines to your code:
>
>iterate2 f x n | seq f $ seq x $ seq n $ False = undefined
>iterate2 f x n = --- as before
>
>rk4Next f h (x, y) | seq f $ seq h $ seq x $ seq y $ False = undefined
>rk4Next f h (x, y) = -- as before
>
>I also increased ten times the number of steps for the last iteration,
>to make the example more illustrative.
>    putStr (show (rk4 stiff 0 1 (exp (-1)) 1000000))
>
>The rest of the code is unchanged. The program now runs on GHCi
>
>*Foo> main
>Begin
>(1.0000000000000007,-6.503275017254139)
>(0.9999999999999062,-6.497717470015538)
>(1.000000000007918,-6.497716616653335)
>
>
>on on hugs
>
>Begin
>(1.0,-6.50327501725414)
>(0.999999999999906,-6.49771747001554)
>(1.00000000000792,-6.49771661665334)
>
>with the default stack size for both interpreters. It seems the code
>does run in constant space now.
>
>The added lines are meant to turn the relevant functions from lazy to
>strict. When you see something like '(n-1)' and 'y + a1/6', it is a
>red flag. These are exactly the kinds of expressions that lead to
>memory exhaustion. Perhaps it is because the size of an unevaluated
>thunk for (n-1) is so much bigger than the size of the evaluated
>thunk. It seems that arithmetic expressions are the best candidates
>for some opportunistic evaluation...
>_______________________________________________
>Haskell-Cafe mailing list
>Haskell-Cafe at haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe

------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact