Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On Tue, 27 Aug 2013, John Lato wrote: [1] Most people are physically incapable of reading documents that explain why what they want to do won't work. Even if people did read the documentation, I suspect that the people most in need of the information would be the least likely to understand how it applies to their situation. Plus: I don't expect that programmers read the documentation of 'sequence' and 'mapM' again every time they use the function. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
Thanks for your examples. On 27/08/13 13:59, Albert Y. C. Lai wrote: The correct fix is to raise the stack cap, not to avoid using the stack. Indeed, ghci raises the stack cap so high I still haven't fathomed where it is. This is why you haven't seen a stack overflow in ghci for a long time. See, ghci agrees: the correct thing to do is to raise the stack cap. If I understand this correctly, you agree that the stack size should be unlimited by default? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On Mon, Aug 26, 2013 at 4:46 AM, Niklas Hambüchen m...@nh2.me wrote: On #haskell we recently had a discussion about the following: import System.Random list - replicateM 100 randomIO :: IO [Int] I would think that this gives us a list of a million random Ints. In fact, this is what happens in ghci. But with ghc we get: Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. You can use ContT to force the function to use heap instead of stack space, e.g. runContT (replicateM 100 (lift randomIO)) return ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On 27/08/13 20:37, Patrick Palka wrote: You can use ContT to force the function to use heap instead of stack space, e.g. runContT (replicateM 100 (lift randomIO)) return That is interesting, and works. Unfortunately its pure existence will not fix sequence, mapM etc. in base. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On Mon, Aug 26, 2013 at 12:05:14PM -0700, Bryan O'Sullivan wrote: On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen m...@nh2.me wrote: This is because sequence is implemented as sequence (m:ms) = do x - m xs - sequence ms return (x:xs) and uses stack space when used on some [IO a]. This problem is not due to sequence, which doesn't need to add any strictness here. It occurs because the functions in System.Random are excessively lazy. In particular, randomIO returns an unevaluated thunk. I don't understand this. The same stack overflow occurs with tenmil :: Int tenmil = 10 * 1000 * 1000 main :: IO () main = do list - replicateM tenmil (return ()) :: IO [()] list `seq` return () return () is not excessiely lazy, is it? Could you explain further? Tom ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
IMHO it's perfectly reasonable to expect sequence/replicateM/mapM to be able to handle a list of ~1e6 elements in the Unescapable Monad (i.e. IO). All the alternate implementations in the world won't be as handy as Prelude.sequence, and no amount of documentation will prevent people from running into this headlong*. So unless there's a downside to upping the stack size limitation I'm unaware of, +1 to that suggestion from me. John [1] Most people are physically incapable of reading documents that explain why what they want to do won't work. Even if people did read the documentation, I suspect that the people most in need of the information would be the least likely to understand how it applies to their situation. On Tue, Aug 27, 2013 at 9:19 PM, John Alfred Nathanael Chee cheech...@gmail.com wrote: This is somewhat related: http://ghc.haskell.org/trac/ghc/ticket/4219 This also solves the concrete problem you gave in your original post (in reverse order): import Control.Monad import System.Random sequencel :: Monad m = [m a] - m [a] sequencel = foldM (\tail m - (\x - return $ x : tail) = m) [] main :: IO () main = print = sequencel (replicate 100 (randomIO :: IO Integer)) Following on Reid's point, maybe it's worth noting in the documentation that replicateM, mapM, and sequence are not tail recursive for Monads that define (=) as strict in the first argument? On Tue, Aug 27, 2013 at 6:07 AM, Niklas Hambüchen m...@nh2.me wrote: On 27/08/13 20:37, Patrick Palka wrote: You can use ContT to force the function to use heap instead of stack space, e.g. runContT (replicateM 100 (lift randomIO)) return That is interesting, and works. Unfortunately its pure existence will not fix sequence, mapM etc. in base. ___ Libraries mailing list librar...@haskell.org http://www.haskell.org/mailman/listinfo/libraries -- Love in Jesus Christ, John Alfred Nathanael Chee http://www.biblegateway.com/ http://web.cecs.pdx.edu/~chee/ ___ Libraries mailing list librar...@haskell.org http://www.haskell.org/mailman/listinfo/libraries ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] sequence causing stack overflow on pretty small lists
On #haskell we recently had a discussion about the following: import System.Random list - replicateM 100 randomIO :: IO [Int] I would think that this gives us a list of a million random Ints. In fact, this is what happens in ghci. But with ghc we get: Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. This is because sequence is implemented as sequence (m:ms) = do x - m xs - sequence ms return (x:xs) and uses stack space when used on some [IO a]. From a theoretical side, this is an implementation detail. From the software engineering side this disastrous because the code is * obviously correct by itself * the first thing people would come up with * not exaggerating: a million elements is not much * used a lot of places: mapM, replicateM are *everywhere* and yet it will kill our programs, crash our airplanes, and give no helpful information where the problem occurred. Effectively, sequence is a partial function. (Note: We are not trying to obtain a lazy list of random numbers, use any kind of streaming or the likes. We want the list in memory and use it.) We noticed that this problem did not happen if sequence were implemented with a difference list. What do you think about this? Should we fix functions like this, probably trading off a small performance hit, or accept that idiomatic Haskell code can crash at any time? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
As an example that this actually makes problems in production code, I found this in the wildlife: https://github.com/ndmitchell/shake/blob/e0e0a43/Development/Shake/Database.hs#L394 -- Do not use a forM here as you use too much stack space bad - (\f - foldM f [] (Map.toList status)) $ \seen (i,v) - ... I could bet that there is a lot of code around on which we rely, which has the same problem but does not go that far in customisation. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen m...@nh2.me wrote: This is because sequence is implemented as sequence (m:ms) = do x - m xs - sequence ms return (x:xs) and uses stack space when used on some [IO a]. This problem is not due to sequence, which doesn't need to add any strictness here. It occurs because the functions in System.Random are excessively lazy. In particular, randomIO returns an unevaluated thunk. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
Maybe an unlimited stack size should be the default? As far as I understand, the only negative effect would be that some programming mistakes would not result in a stack overflow. However, I doubt the usefulness of that: * It already depends a lot on the optimisation level * If you do the same thing in a slightly different way, and you allocate on the heap instead of on the stack you will not get it either ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] sequence causing stack overflow on pretty small lists
On 13-08-26 04:46 AM, Niklas Hambüchen wrote: Effectively, sequence is a partial function. (Note: We are not trying to obtain a lazy list of random numbers, use any kind of streaming or the likes. We want the list in memory and use it.) We noticed that this problem did not happen if sequence were implemented with a difference list. What do you think about this? Should we fix functions like this, probably trading off a small performance hit, or accept that idiomatic Haskell code can crash at any time? 1. Disputed: sequence overflows stack, for all monads (Bonus: a demo of Control.Monad.ST.Lazy) (Bonus: a secret of Control.Monad.State revealed) import Control.Monad.ST.Lazy(runST) import Control.Monad.State(evalState) long :: Monad m = m [Int] long = sequence (map return [1..100]) infinite :: Monad m = m [()] infinite = sequence (repeat (return ())) -- these take constant time one_a = take 1 (runST long) one_b = take 1 (evalState long ()) unit_a = take 1 (runST infinite) unit_b = take 1 (evalState infinite ()) sequence is exactly right for Control.Monad.ST.Lazy and Control.Monad.State. If you fix sequence, you will cause idiomatic use of sequence and Control.Monad.State to use too much time (up to infinite) and too much memory (up to infinite). Note: Control.Monad.State = Control.Monad.State.Lazy For more demos of Control.Monad.ST.Lazy and Control.Monad.State(.Lazy), see my http://lpaste.net/41790 http://lpaste.net/63925 2. What to do for IO, Control.Monad.ST, Control.Monad.State.Strict, etc As you said, we can combine right recursion (foldM) and difference list (aka Hughes list). I will dispute its questionable benefit in the next section, but here it is first. sequence_hughes ms = do h - go id ms return (h []) where go h [] = return h go h (m:ms) = do x - m go (h . (x :)) ms equivalently, sequence_hughes ms = do h - foldM op id ms return (h []) where op h m = do x - m return (h . (x :)) However, as I said, sequence_hughes is totally wrong for Control.Monad.State and Control.Monad.ST.Lazy. And this is not even my dispute of the questionable benefit. 3. Disputed: stack is limited, heap is unlimited sequence_hughes consumes linear heap space in place of linear stack space. That's all it does. There is no free lunch. Empirically: on linux i386 32-bit GHC 7.6.3 -O2: xs - sequence (replicate 200 (return 0 :: IO Int)) print (head xs) 8MB stack, 16MB heap xs - sequence_hughes (replicate 200 (return 0 :: IO Int)) print (head xs) 24MB heap What has sequence_hughes saved? Since a couple of years ago, GHC RTS has switched to growable stack, exactly like growable heap. It starts small, then grows and shrinks as needed. It does not need a cap. The only reason it is still capped is the petty: to stop the program eating up all the available memory in the machine if it gets into an infinite loop (GHC User's Guide) Asymmetrically, the heap is not capped by default to stop the program eating up all the available memory. And the default stack cap 8MB is puny, compared to the hundreds of MB you will no doubt use in the heap. (Therefore, on 64-bit, you have to change 200 to 100 in the above.) (Recall: [Int] of length n entirely in memory takes at least 12n bytes: 4 for pointer to Int, 4 for the number itself, 4 for pointer to next, and possibly a few more bytes I forgot, and possibly a few more bytes if the Int is lazy e.g. randomIO as Bryan said. That's just on 32-bit. Multiply by 2 on 64-bit.) The correct fix is to raise the stack cap, not to avoid using the stack. Indeed, ghci raises the stack cap so high I still haven't fathomed where it is. This is why you haven't seen a stack overflow in ghci for a long time. See, ghci agrees: the correct thing to do is to raise the stack cap. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
