[Haskell-beginners] Understanding program stack usage

[Daniel Fischer]

On Wednesday 27 April 2011 17:20:15, Felipe Almeida Lessa wrote:
> On Wed, Apr 27, 2011 at 11:52 AM, Patrick LeBoutillier
> 
> <patrick.leboutillier at gmail.com> 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,