[Haskell-cafe] Squashing space leaks

[Josef Svenningsson]

On 5/5/05, Greg Buchholz <haskell at sleepingsquirrel.org> wrote:
> 
>     I've been dabbling with implementing the "n-body" benchmark over at
> the "Great Computer Language Shootout"...
> 
> http://shootout.alioth.debian.org/benchmark.php?test=nbody
> 
> ...and I've stumbled on to a problem with space leaks.  The code below
> works great for low numbers of iterations, but crashes and burns with
> large numbers.  You can temporarily fix it up by specifying larger
> stack and heap sizes (with the +RTS -K & -H options), but this only gets
> you so far.  I haven't been able to glean much information from the
> profiling reports.  You can see the reports I generated (like the
> biography report) over at <http://sleepingsquirrel.org/nbody>.  I've
> tried several different variations on the "advance" function, as well as
> trying "seq" in numerous spots, but I haven't stumbled on to the right
> combination yet.  Any pointers?
> 
I think the thing that really kills you is the way you shuffle around
the list in the advance function. Your commented out rotations
function has the same problem. Here is my attempt to solve the problem
a little more efficiently:

\begin{code}
update :: (a -> [a] -> a) -> ([a] -> [a]) -> [a] -> [a]
update f newlist []     = []
update f newlist (a:as) = a' : update f (newlist . (a':)) as
  where a' = f a (newlist as)

advance dt ps = update newplanet id ps
  where newplanet p ps = Planet (pos p + delta_x) new_v (mass p)
          where delta_v = sum (map (\q -> 
                  (pos p - pos q) `scale` ((mass q)*dt/(dist p q)^3)) ps)
                new_v   = (vel p) - delta_v
                delta_x = new_v `scale` dt 
\end{code}
(update is a really bad name for the above function. It's just the
first name that came to mind. You can probably come up with something
better.)

Also, putting strictness annotations in the Planet data type will
yield some speedup.

HTH,

/Josef