I'm tinkering with a little program I wrote a while back to generate probability distributions and averages for rolling various kinds and quanitities of dice and applying various rules (for instance, roll four six-sided dice, drop the lowest, and add the other three). I'm trying to optimize the thing, and I've run into a space leak. I've found that, if I tell it to roll four 20-sided dice and add, it finishes in under a second and heap usage peaks at under 2MB (not sterling, but not catastrophic); but if I make it five 20-sided dice, it runs out of stack space after thrashing for a while (and getting partway through the final output); for six dice, it thrashes into oblivion. (Running WinXP with 256MB memory.) What puzzles me is that, according to GHC's heap-usage-by-call-center graph, the hog isn't the code that generates every single outcome of rolling the dice (and we're talking about four 20-sided dice here ...), whose heap usage is constant (go GHC! :-) ), but the one that turns the list of outcomes (for instance, [2,3,3,4,4,4 ... 7,7,7,7,7,7 ... 11,11,12] for adding two 6-sided dice) into a probability distribution (like [(2,1),(3,2),(4,3) ... (7,6) ... (11,2),(12,1)]). It is this:

-- Specs contains the options for the simulation; rollBounds simply finds the lowest and highest possible rolls -- type RollValue = Int -- type RollValueDist = Array RollValue Int probDist :: Specs -> [RollValue] -> RollValueDist probDist specs rolls = accumArray (+) 0 (rollBounds specs) [(r, 1) | r <- rolls]

It should be doing an in-place array update as it evaluates the comprehension, but apparently something's being kept in memory longer than it has an excuse for. I tried another, more hand-coded version, to get rid of the mid-calculation comprehension and some possible overhead:

probDist specs = foldl update orig where orig = array bounds [(r, 0) | r <- range bounds] update dist r = dist // [(r, 1 + dist!r)] bounds = rollBounds specs

But this one was even worse. I've sprinkled $! around quite liberally, to no avail; also, I'm compiling with -O, and I've tried various RTS options with no radical change in behavior. What's going on here? The array constructed has to be big, but not *that* big (77 Ints for four 20-sided) ... Is there an inherent inefficiency with GHC's arrays when used like this? I can't come up with a better algorithm - making a zeroed array with an element for each outcome, then adding 1 to the element for each outcome as it is read in seems straightforward enough. (Would a FiniteMap be any better? I'm not sure how ...) Thanks for any help ... I'm starting to get the hang of Haskell, but some of these semantic subtleties are driving me nutty ... Luke Maurer jyrinx_list@mindspring.com