Hi all, I have a very simple program which reads a Data.Map from a file using Data.Binary and Data.ByteString.Lazy, which gives stack overflow with files over a certain size. Any ideas of what might be causing it? You can try it with the small file (11M) at: http://computing.dcu.ie/~gchrupala/map.bin import System import Data.Map import qualified Data.ByteString.Lazy as BS import Data.Binary main = do [path] <- getArgs m <- fmap decode (BS.readFile path)::IO (Map (Int,Maybe String) Int) putStrLn . show . findMax $ m -- Grzegorz -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15479718.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Thu, Feb 14, 2008 at 04:56:39AM -0800, Grzegorz Chrupala wrote:
I have a very simple program which reads a Data.Map from a file using Data.Binary and Data.ByteString.Lazy, which gives stack overflow with files over a certain size. Any ideas of what might be causing it?
You can try it with the small file (11M) at: http://computing.dcu.ie/~gchrupala/map.bin
import System import Data.Map import qualified Data.ByteString.Lazy as BS import Data.Binary main = do [path] <- getArgs m <- fmap decode (BS.readFile path)::IO (Map (Int,Maybe String) Int) putStrLn . show . findMax $ m
Since no-one else has answered, I'll take a stab. Obiously, you have a stack leak due to laziness somewhere -- now Data.Map is strict in it's keys, but lazy in it's values, and Data.Binary is lazy so my suspicion would be that you're building up lazy decode thunks for the value elements on the stack as the map is being constructed. If either decode or the Map construction were strict, you'd probably be OK, but the combination is blowing the stack. (Data.Binary serialises Maps by writing them out to a list of key, value pairs in ascending key order. The Map can be reconstructed from this list in O(N) time.) In your specific example, you can replace the type for the result of the decoding with IO [(Int,Maybe String),Int)] and evaluate the right hand sides (with seq if necessary) before constructing the map from the list, which will avoid the stack blowout. 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... cheers, Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt
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". 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 :-(
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. 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). As to what's really going on here, I haven't figured it out and I'm not really inclined to try :-) Regards -- Adrian Hey
Adrian Hey wrote:
Philip Armstrong wrote:
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.
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).
I'm fairly certain that the stack overflow is (indirectly) caused by Data.Binary, not Data.Map. The result of 'decode' is a list of known length with unevaluated elements (because the Get monad is lazy) [*], where each element depends on the previous one (because reading is sequential, and the elements of the list may have nonuniform size). Now when you evaluate the last element, that will demand the last but one element, which in turn will demand the previous element, and so on. If the list is long enough, you'll get a stack overflow. Using fromAscList instead of fromDistinctAscList cures the problem, because it inspects every key in the list, starting from the beginning, in order to eliminate duplicates. fromDistinctAscList, on the other hand, does not inspect the keys at all. do [path] <- getArgs m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)] putStrLn . show . last $ m should also exhibit the same stack overflow. HTH, Bertram [*] For example, consider this: Prelude Data.Binary> length (decode (encode (42 :: Int)) :: [Int]) 42 Prelude Data.Binary> decode (encode (42 :: Int)) :: [Int] [*** Exception: too few bytes. Failed reading at byte position 16
Bertram Felgenhauer wrote:
I'm fairly certain that the stack overflow is (indirectly) caused by Data.Binary, not Data.Map.
Yes, I think you are right. At least it seems clear that the stack overflow is not directly caused by fromDistinctAscList.
The result of 'decode' is a list of known length with unevaluated elements (because the Get monad is lazy) [*], where each element depends on the previous one (because reading is sequential, and the elements of the list may have nonuniform size). Now when you evaluate the last element, that will demand the last but one element, which in turn will demand the previous element, and so on. If the list is long enough, you'll get a stack overflow.
Using fromAscList instead of fromDistinctAscList cures the problem, because it inspects every key in the list, starting from the beginning, in order to eliminate duplicates. fromDistinctAscList, on the other hand, does not inspect the keys at all.
do [path] <- getArgs m <- liftM decode (BS.readFile path)::IO [((Int, Maybe String), Int)] putStrLn . show . last $ m
should also exhibit the same stack overflow.
Indeed it does. So it seems if I understand correctly, this is yet another example what I would call the lazy applied strict thunk chain problem (I'm sure you understand what I mean by that). The standard "party line" advice in such circumstances is to prevent their formation by evaluating eagerly as they are applied. However, this is often not possible for users of libraries they don't "own", if the API does not provide the necessary strictness control. I would argue that even if it possible is sometimes undesirable too (if evaluation is expensive, saves nothing in heap use and the final value may never be needed). So I still think the stack management system should be designed so that as far as is practical (given finite memory), any expression that can be built on the heap can also be evaluated without causing a "stack overflow". But I guess this rant is not much help to the OP :-) Regards -- Adrian Hey
On Sun, Feb 17, 2008 at 11:45:26PM +0000, Adrian Hey wrote:
But I guess this rant is not much help to the OP :-)
Can the Get Monad from Data.Binary be replaced by the one in Data.Binary.Strict.Get? Would probably require some hacking on the library I guess. Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt
Philip Armstrong wrote:
On Sun, Feb 17, 2008 at 11:45:26PM +0000, Adrian Hey wrote:
But I guess this rant is not much help to the OP :-)
Can the Get Monad from Data.Binary be replaced by the one in Data.Binary.Strict.Get?
Would probably require some hacking on the library I guess.
I was getting stack overflows when using Data.Binary with a few other datastructures so I decided to try this option. I hacked a Data.Binary.Strict module which is basically a copy and paste of Data.Binary, but exports a strict decode which uses the Get monad from Data.Binary.Strict.Get. It's just a hack and I'm sure there are better ways of doing it but it works for me so I'm attaching it. -- Grzegorz http://www.nabble.com/file/p15710959/Strict.hs Strict.hs -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15710959.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
On Feb 27, 2008, at 3:02 AM, Grzegorz Chrupala wrote:
I was getting stack overflows when using Data.Binary with a few other datastructures so I decided to try this option. I hacked a Data.Binary.Strict module which is basically a copy and paste of Data.Binary, [...]
We've recently hit the point where it makes sense to check Hackage
before you embark on small hacking projects like this:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict-0.3...
Bryan O'Sullivan wrote:
On Feb 27, 2008, at 3:02 AM, Grzegorz Chrupala wrote:
I was getting stack overflows when using Data.Binary with a few other datastructures so I decided to try this option. I hacked a Data.Binary.Strict module which is basically a copy and paste of Data.Binary, [...]
We've recently hit the point where it makes sense to check Hackage before you embark on small hacking projects like this:
http://hackage.haskell.org/cgi-bin/hackage-scripts/package/binary-strict-0.3...
My module uses the Get monad from the above binary-strict package, but defines and exports the equivalents of functions in Data.Binary, which are missing from binary-strict, most importantly the (strict version) of the decode function. Best, -- Grzegorz -- View this message in context: http://www.nabble.com/Stack-overflow-tp15479718p15717389.html Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.
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
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.
Philip Armstrong wrote:
On Sun, Feb 17, 2008 at 10:01:14PM +0000, Adrian Hey wrote:
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.
Can you or anyone else give an example? Thanks -- Adrian Hey
On Mon, Feb 18, 2008 at 05:56:41PM +0000, Adrian Hey wrote:
Philip Armstrong wrote:
On Sun, Feb 17, 2008 at 10:01:14PM +0000, Adrian Hey wrote:
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.
Can you or anyone else give an example?
I think I was thinking of this: http://r6.ca/blog/20071028T162529Z.html but can't be entirely sure. Sorry! Phil -- http://www.kantaka.co.uk/ .oOo. public key: http://www.kantaka.co.uk/gpg.txt
Philip Armstrong wrote:
On Mon, Feb 18, 2008 at 05:56:41PM +0000, Adrian Hey wrote:
Philip Armstrong wrote:
On Sun, Feb 17, 2008 at 10:01:14PM +0000, Adrian Hey wrote:
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.
Can you or anyone else give an example?
I think I was thinking of this:
http://r6.ca/blog/20071028T162529Z.html
but can't be entirely sure. Sorry!
Perhaps I should say can someone provide an example and explain why they believe it is faster. That isn't to say I doubt the measurements taken with that particular code, but I must say that if transforming code that uses the "hardware accelerated" continuation passing (by that I mean the machine stack of course) to explicit continuations on the heap is generally faster, there must be something very wrong in stack land. But perhaps there is? Interestingly, if you allow sufficient stack space for Grzegorz version (+64M) it does terminate, but it's still much slower than the version you provided (about 30 times slower). I don't know if this slow down is due only to the stack use, or whether both the stack use and the slow down are just different artefacts of the problem Bertram mentioned. Regards -- Adrian Hey
participants (5)
-
Adrian Hey -
Bertram Felgenhauer -
Bryan O'Sullivan -
Grzegorz Chrupala -
Philip Armstrong