[Haskell-cafe] Stack overflow

[Philip Armstrong]

On Sun, Feb 17, 2008 at 10:01:14PM +0000, Adrian Hey wrote:
> Philip Armstrong wrote:
>> Since no-one else has answered, I'll take a stab.
>> Obiously, you have a stack leak due to laziness somewhere
>
> I wouldn't say that was obvious, though it is certainly a
> possibility.
>
> I'm never exactly clear what people mean by a "stack leak".
> It seems some folk regard any algorithm that makes use of
> O(n) or worse stack space as a "stack leak".

In my personal lexicon, a stack leak is one where you accumulate
unevaluated thunks on the stack.

In this case, the combination of Data.Map not evaluating it's values
and Data.Binary being lazy is (I think) resulting in decode thunks
accumulating on the stack.

> My opinion is that using O(n) or worse working memory when
> the job could be done in O(log n) or O(1) memory is certainly
> bad, but using O(n) stack is no worse in principle than using
> O(n) heap. But at the moment it is worse in practice with ghc,
> regretably :-(

I'd agree with this entirely.

>> In fact, a little experimentation has revealed that this:
>>
>>   do
>>    [path] <- getArgs
>>    m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)]
>>    putStrLn . show . findMax . fromAscList $ m
>>
>> will work just fine. No extra evaluation needed at all! I'll leave it
>> to the Haskell gurus to explain what's going on...
>
> That's very interesting. Strangely if you use fromDistinctAscList
> instead (as used by the Binary instance get method) the problem
> re-appears. This is despite fromAscList making use of fromDistinctAscList.

Yup. It's because (I've just realised) fromAscList is evaluating the
values returned by decode in order to build the Distinct Ascending
List to pass to fromDistinctAscList. A previous version I was going to
put up simply ran another function over the list before passing it to
the map constructor, which was not particularly elegant but also
worked.

Data.Binary calls fromDistinctAscList to build the map, which is why
it gets into this mess.

> BTW, I find this especially ironic as fromDistinctAscList is the perfect
> example what I was talking about in another thread (continuation passing
> madness caused by an irrational fear of stack use).

In *some* cases, continuation passing can be quite a bit faster than
other approaches IIRC. I haven't looked at this bit of code though.

> As to what's really going on here, I haven't figured it out and I'm not
> really inclined to try :-)

I did try and do some profiling, but gave up when I realised that I'd
have to go sprinking SCCs around the core libraries, which would mean
recompiling Data.Map and friends...

Heap profile graphs which assign everything to "CAF" are not very
helpful :)

Phil

-- 
http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt

  LocalWords:  fromDistinctAscList IIRC sprinking