Turns out I was building the trees wrong, ended up getting a structure that looked like a linked list (each tree only had 1 child) so the depth of the recursion was way higher than it should've been. Crisis averted! Still seemed odd that the garbage collector ran for so much of the time, so I checked and there's a ticket in GHC trac about it: http://hackage.haskell.org/trac/ghc/ticket/2236 . On 20-May-09, at 12:02 AM, Matthew Eastman wrote:
...
The code I have right now works great on point sets of size ~10,000, but when I go up much higher things start to go wrong. I start hitting stack overflows, so I increased the stack size. For ~100,000 points though, running the code with +RTS -sstderr -K128m it chugged along for over an hour and then died with a stack overflow. The stats said it spent 50 seconds MUT time and 5300 seconds (almost 90 minutes!) GC time, which seems odd.
...