[Haskell-cafe] Space efficiency problem

[Keith Wansbrough]

> Hi,
> 
> This may be silly, but I tried to code a simmulated annealing method
> to solve the travelling salesman prblem, by adapting the algorithm
> described in "Numerical Recipes in C".

Doesn't seem silly so far! :-)

> The problem is that there are
> so many iterations, that the program gets killed (kill -9) by the
> system.

I'm not sure what you mean here - I've never encountered a system that
kills processes with -9, other than at shutdown time.  Are you sure
it's -9?

How do you know it's because there are too many iterations?

> I use the State monad to code the optimisation algorithm,
> and a simple configurations generator for generating the each
> path. After profiling with -hc, the heap profile shows that the
> top-level function of the algorithm uses about 40Mb of heap space.

That sounds fine to me - I have plenty of programs that use well over
100MB of heap.  How much memory do you have?  (you say later that it
eats up all the available space - I find it hard to believe 40MB is
all you have!).

> How can I improve this awful program?

You probably have a space leak.  This is usually caused by p or f not
forcing the evaluation of all of m0.  Since the next m0 depends on the
previous one, and so on, this causes all values of m0 to be held in
the heap until the end of the program.

Add strictness annotations in the right places[*] until heap usage is
constant, rather than increasing with each iteration.

> untilM :: (Monad m) => (m a -> m Bool) -> (a -> m a) -> m a -> m a
> untilM p f m0 = do
> 	isOver <- p m0
> 	if isOver then m0
> 		  else untilM p f (m0 >>= f)

[*] of course, this is an entirely non-trivial task, and involves art
as well as skill...

Hope this helps.

Cheers,

--KW 8-)