Felipe, I tried the $! bit, but I get the same result. I guess there's another leak somewhere... Patrick On Wed, Apr 27, 2011 at 11:20 AM, Felipe Almeida Lessa wrote:

On Wed, Apr 27, 2011 at 11:52 AM, Patrick LeBoutillier wrote:

...

How do I figure out why the program needs a lot of stack?

Usually it is because you are building a large thunk.

...

Also, is there an easy way to increace performance?

Getting rid of the thunks should increase performance as well.

I've had just a quick look on your code, but here are some suggestions:

...

record :: (Ord n) => n -> Distrib n -> Distrib n record n (Distrib m rs) = Distrib (M.alter f slot m) rs  where f (Just n) = Just $ n + 1        f Nothing = Just 1        slot = findSlot n rs        findSlot x (r@(Range a b):rs)          | x >= a && x < b = r          | otherwise       = findSlot x rs        findSlot x []       = OutOfBounds

Try changing "Just $ n + 1" to "Just $! n + 1".  It is possible that this change alone removes the leak (it is the only obvious leak I'm seeing right now).

Also, for findSlot you may want to do a binary search, but that isn't related to the leak at all.

Cheers,

-- Felipe.

-- ===================== Patrick LeBoutillier Rosemère, Québec, Canada

On Wednesday 27 April 2011 17:20:15, Felipe Almeida Lessa wrote:

On Wed, Apr 27, 2011 at 11:52 AM, Patrick LeBoutillier

wrote:

...

How do I figure out why the program needs a lot of stack?

Usually it is because you are building a large thunk.

...

Also, is there an easy way to increace performance?

Getting rid of the thunks should increase performance as well.

I've had just a quick look on your code, but here are some suggestions:

...

record :: (Ord n) => n -> Distrib n -> Distrib n record n (Distrib m rs) = Distrib (M.alter f slot m) rs where f (Just n) = Just $ n + 1 f Nothing = Just 1 slot = findSlot n rs findSlot x (r@(Range a b):rs) | x >= a && x < b = r | otherwise = findSlot x rs findSlot x [] = OutOfBounds

Try changing "Just $ n + 1" to "Just $! n + 1". It is possible that this change alone removes the leak (it is the only obvious leak I'm seeing right now).

I'm not sure that alone would help. I think he'll still get a thunk (M.alter f slot (M.alter f slot (... ())). record would need to force the Map, easiest to make Distrib strict in the map, data Distrib n = Distrib !(M.Map (Range n Int)) [Range n] Another point is that he uses a foldr, which generally is a bad strategy for building Maps, much better to use foldl' in general. Some more gains I would expect from not using a Map here, but to use accumArray on an unboxed array (UArray Int Int, one would have to map the slots to indices, but that's trivial to do when finding the right slot).

Also, for findSlot you may want to do a binary search,

Not while the ranges are stored as a list. Exercise: Why is a binary search on a singly linked list a bad idea? Storing the 'list' of ranges as an array would make a binary search worthwhile, though, at least for situations with more ranges. For the four (or five including OutOfBounds) ranges in the example main, linear search of a singly linked list will be hard to beat.

but that isn't related to the leak at all.

Cheers,

On Wed, Apr 27, 2011 at 3:41 PM, Daniel Fischer wrote:

Not while the ranges are stored as a list. Exercise: Why is a binary search on a singly linked list a bad idea?

I'm sorry if it sounded as if that was what I was suggesting. You can't do any better than O(n) with a linked list. Cheers, -- Felipe.