On 5/5/05, Greg Buchholz
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