[Haskell-cafe] How do I get a long iteration to run in constant space
W M
considering it for a simulation I've been designing,
but I ran into this problem with a simple numerical
calculation. The attached program is supposed to
solve a stiff differential equation, and you have to
use a very small stepsize and lots of steps to resolve
the part of the solution near a singularity. It looks
to me like this program should run in constant space
because the iterate2 function is tail-recursive, but
when I run it on hugs or ghc 2.6.1, I get an error
that it runs out of stack space on the third
calculation. (And the quick fix is to give it a flag
that increases the stack, but if I'm to use haskell
for a potentially large and long simulation, I can't
afford to let it run for three days only to get an
error and figure out that it needs more stack space
than the computer can give.) I suppose in my ODE
example it's building up expressions somewhere for
lazy evaluation, so I've tried putting seq and $! in
various places. I have another example where using
"else seq x (iterate2 ...)" helps, but that doesn't
solve my problem here. I've also tried -O but it
doesn't help. Can anyone give me some idea as to what
to do?
Thanks,
-wgm
iterate2 f x n =
if n == 0 then
x
else
iterate2 f (f x) (n - 1)
integrate step f xInit xFinal yInit nSteps =
let
h = (xFinal - xInit) / fromIntegral nSteps
next = step f h
in
iterate2 next (xInit, yInit) nSteps
rk4Next f h (x, y) =
let
a1 = h * f x y
a2 = h * f (x + h/2) (y + a1/2)
a3 = h * f (x + h/2) (y + a2/2)
a4 = h * f (x + h) (y + a3)
in
(x + h, y + a1/6 + a2/3 + a3/3 + a4/6)
rk4 = integrate rk4Next
stiff x y = -( ((exp (x - 1)) + (x - 1) * y)
/ (1 - x - 0.0001 * y) )
main =
do
putStr "Begin\n"
putStr (show (rk4 stiff 0 1 (exp (-1)) 1000))
putStr "\n"
putStr (show (rk4 stiff 0 1 (exp (-1)) 10000))
putStr "\n"
putStr (show (rk4 stiff 0 1 (exp (-1)) 100000))
putStr "\n"
__________________________________
Do you Yahoo!?
Yahoo! Mail - You care about security. So do we.
http://promotions.yahoo.com/new_mail
_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Malcolm Wallace
> I suppose in my ODE
> example it's building up expressions somewhere for
> lazy evaluation,
Exactly right. The trick is spotting which expressions. Until you
have some experience of likely causes, rather than guessing I can
recommend studying some heap profiles to learn what kind of values
are building up - e.g. are they closures for 'integrate' or for '+'?
Here are a couple of simple changes that seem to fix your space leak.
> iterate2 f x n =
> if n == 0 then
> x
> else
> iterate2 f (f x) (n - 1)
Try
x `seq` iterate2 f (f x) (n - 1)
to ensure that the accumulator is holding simple values rather than
closures.
Also, currently you are building pairs lazily. Making a strict pair
type helps:
data Pair a = P !a !a
> integrate step f xInit xFinal yInit nSteps =
> let
> h = (xFinal - xInit) / fromIntegral nSteps
> next = step f h
> in
> iterate2 next (xInit, yInit) nSteps
iterate2 next (P xInit yInit) nSteps
> rk4Next f h (x, y) =
> let
> a1 = h * f x y
> a2 = h * f (x + h/2) (y + a1/2)
> a3 = h * f (x + h/2) (y + a2/2)
> a4 = h * f (x + h) (y + a3)
> in
> (x + h, y + a1/6 + a2/3 + a3/3 + a4/6)
P (x + h) (y + a1/6 + a2/3 + a3/3 + a4/6)
> rk4 = integrate rk4Next
>
> stiff x y = -( ((exp (x - 1)) + (x - 1) * y)
> / (1 - x - 0.0001 * y) )
>
> main =
> do
> putStr "Begin\n"
> putStr (show (rk4 stiff 0 1 (exp (-1)) 1000))
> putStr "\n"
> putStr (show (rk4 stiff 0 1 (exp (-1)) 10000))
> putStr "\n"
> putStr (show (rk4 stiff 0 1 (exp (-1)) 100000))
> putStr "\n"
ol...@pobox.com
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...
Graham Klyne
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
--
>_______________________________________________
>Haskell-Cafe mailing list
>Haskel...@haskell.org
>http://www.haskell.org/mailman/listinfo/haskell-cafe
------------
Graham Klyne
For email:
http://www.ninebynine.org/#Contact
Ben Lippmeier
In my experience, any time your program makes use of some state-like
structure which gets updated over a number of iterations, you're going
to be in trouble with space leaks.
There's a library function which summarises this nicely,
mapAccumL :: (state -> x -> (state, y)) -> state -> [x] -> (state, [y])
The GHC library docs describe mapAccumL as
"The mapAccumL function behaves like a combination of map and foldl; it
applies a function to each element of a list, passing an accumulating
parameter from left to right, and returning a final value of this
accumulator together with the new list."
Now imagine that state is some large structure. The [x] list is a couple
of hundred elements long, and you print out some -> but not all <- of
the [y] elements. While the [y] list remains live, a whole collection of
half evaluated intermediate states also remain live - enter the
massive space leak.
Projects I have written which suffered massive space leaks include:
-> A parallel lazy evaluator,
http://cs.anu.edu.au/ample.
The state: the machine state, threads, stacks, the heaps.
The [x] list: machine instructions.
The [y] list: profiling info.
If you don't print out all possible profiling info then all those
intermediate states remain live and you've got a massive space leak.
-> An astroids game I wrote for X.
The state: position, velocities of ship, astroids, missiles.
The [x] list: ship control data, key codes.
The [y] list: a list of graphics prims which get rendered to the screen.
You would think that because the list of prims gets consumed by the
renderer it wouldn't leak.. but it did, about 200k / sec. Then I changed
some seemingly irrelevant part of the code and the space leak went
away.. and I have no idea why. yay.
-> My ICFP contest entry for this year,
Not really a mapAccumL type problem, but still a space leak.
At one stage I had a bug in the parser for my assembly language where it
didn't handle comments properly. One of the entries I ran through my
simulator had comments at the end of lines with Drop statements, but
nowhere else.
The simulator ran fine until an ant found some food, carried it back to
the hill, then attempted to drop it.. parser error. My Haskell program
hadn't fully evaluated the thunks to read / parse / assemble that line
of code until the ant had tried to use that part of the program.. I
laughed, and laughed.. :).
...
I think the only way to totally slay bugs like these is to use some
deepSeq'esque function on all your intermediate states, or any time when
you reckon some evaluation should be 'finished'. Either that or explicly
define intermediate structures to be fully strict.
I see the GHC people have got a seqExpr function in
compiler/coreSyn/CoreSyn.lhs, which I imagine would be applied to the
expression tree after every compiler stage.
Ben.
Graham Klyne wrote:
> 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
>
_______________________________________________
William Lee Irwin III
> Now imagine that state is some large structure. The [x] list is a couple
> of hundred elements long, and you print out some -> but not all <- of
> the [y] elements. While the [y] list remains live, a whole collection of
> half evaluated intermediate states also remain live - enter the
> massive space leak.
> Projects I have written which suffered massive space leaks include:
> -> A parallel lazy evaluator,
> http://cs.anu.edu.au/ample.
> The state: the machine state, threads, stacks, the heaps.
> The [x] list: machine instructions.
> The [y] list: profiling info.
> If you don't print out all possible profiling info then all those
> intermediate states remain live and you've got a massive space leak.
> -> An astroids game I wrote for X.
> The state: position, velocities of ship, astroids, missiles.
> The [x] list: ship control data, key codes.
> The [y] list: a list of graphics prims which get rendered to the screen.
Know any tricks for 2D recurrences where only points along the i=j line
(which depend on all points where i <= j) are used for the final result?
-- wli
W M
I take it that the extra case always fails but forces
the arguments to be evaluated? Nice trick.
Thanks!
--wgm
--- ol...@pobox.com wrote:
__________________________________
Do you Yahoo!?
Yahoo! Mail - Helps protect you from nasty viruses.
http://promotions.yahoo.com/new_mail