Space efficiency problem
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". The problem is that there are so many iterations, that the program gets killed (kill -9) by the system. 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. How can I improve this awful program? The optimisation algorithm is coded as simmann = untilM theEnd refine path0 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) theEnd tests if the current temperature has reached the lower limit, and refine produces a new path via a random modification on the current one. What can I do to get this running? It seems to eat up all the available space. I coded this previously in C, with destructive update of the state and path, but in Haskell, with recursion, this seems to be hoplessly inefficient. I use ghc-6.2.1 on a Slackware box based on kernel 2.4.18 with glibc 2.2.5 Thanks for your time! Adrian.
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-)
Keith Wansbrough wrote:
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?
If a process exhausts its resource limits (as set with setrlimit()), the kernel will typically kill it with SIGKILL. Also, if the available system-wide memory gets too low, the kernel may start killing of processes, again with SIGKILL. When this occurs, the shell from which the process was spawned will typically write "Killed" to the terminal. -- Glynn Clements <glynn@gclements.plus.com>
Thanks for the advice. However, though I don't know how ghc manages the heap, I am not sure it is possible to achieve constant heap usage, because a value of type State is a function, and >>= is creating a call stack in this case. I mean, I think that, even if the argument of f :: a -> State s a has a stricness flag, the value m0 :: State s a is itself a function of the state (with type s); then the value ((m0 >>= f) >>= f) >>= .....) >>= f is applied to a state s0, this must be passed down to the bottom of the call stack to perform the actual computation. And this may eat up a lot of heap space. Do you know what can I do about this? Thanks again! Adrian P.S. I appologize for bothering you, but my programming background is in C, not in Haskell, and I have many "white spots" as far as memory management in functional programming is concerned. Thanks again! Adrian
Adrian Victor CRISCIU wrote:
Thanks for the advice. However, though I don't know how ghc manages the heap, I am not sure it is possible to achieve constant heap usage, because a value of type State is a function, and >>= is creating a call stack in this case. I mean, I think that, even if the argument of f :: a -> State s a has a stricness flag, the value m0 :: State s a is itself a function of the state (with type s); then the value ((m0 >>= f) >>= f) >>= .....) >>= f is applied to a state s0, this must be passed down to the bottom of the call stack to perform the actual computation. And this may eat up a lot of heap space.
I don't think this is a problem if the expression associates the other way (as your program does), i.e. m0 >>= (\x -> f x >>= (\x -> f x >>= (\x -> f x >>= ... f))) This can be tail recursive if there's enough strictness. On a related note, it seems like it might be worth introducing (=>>=) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c with a higher precedence than (>>=) and associating to the right, so that one could write m0 >>= f1 =>>= f2 =>>= ... =>>= fn and avoid the inefficiency of the left-associative (>>=). Does this make any sense? -- Ben
participants (4)
-
Adrian Victor CRISCIU -
Ben Rudiak-Gould -
Glynn Clements -
Keith Wansbrough