Philip Armstrong wrote:
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
Thanks to everyone who answered, this fixes my particular problem, and I think thanks to the comments I sort of vaguely understand what going on now. I run into this kind of esoteric laziness leaks from time to time and it's very frustrating -- I think that's about the only thing I don't like about Haskell. -- Grzegorz -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15543838.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.