Neil Mitchell wrote:
Hi
First bad thing: Stack size (memory consumed) doubles each time it overflows.
Bad thing? Assume that allocating memory takes some constant amount of time, such as invoking overflow behaviour etc. To get the size of the stack to n bytes with doubling takes O(log n), to get it there with a constant increase takes O(n).
But whatever the program did to get given stack size must have been at least O(n) anyway, so overall it's still going to be O(n) even if the stack allocation part is O(log n). We're just talking about a very tiny increase in constant factors, at least if Stefan O'Rears hypothesis is correct :-). I'm inclined to agree with him.
If you store the stack in a linear block, then allocation costs O(n) and you can even risk O(n^2) behaviour unless you double each time. I think its fairly well understood that things like hash tables should double in size when they overflow, rather than increasing by some small increment.
It is? Well obviously if the entire thing is copied each time this will be bad, but that's not what we're talking about. See Stefans proposal.
Also remember that this behaviour never wastes more than 50% of the stack, which is a relatively small amount.
Only if the stack is relatively small. Would you say the same about heap, or about a stack that only needed 50% of heap space but ended up using all of it? Or money? Using twice as much as you need of anything is bad IMO.
Third bad thing (the really bad thing): If a stack has temporarily grown (to 64M say), it will never shrink back down again to something more typical (< 4K say). If I understand correctly, it will continue to take 64M from the heap regardless.
That would be nice. But its only beneficial if there are programs which takes large amounts of stack at some point, but then shrink down to very little stack and continue for a reasonable amount of time. Console programs probably don't fit this pattern (since they tend to be batch style and exit quickly). GUI programs probably do, so perhaps stack reduction will be more important as the GUI toolkits mature and Haskell starts getting used for UI type things.
The nature of the app has nothing to do with it AFAICS, this problem can affect any program that evaluates expressions.
That said, unless there is a real user with a real problem (rather than a theoretical concern), priority may go to other bugs.
The point is that writing a stack greedy function definition (rather than a heap greedy alternative) is almost always the simpler option, and would probably be more efficent too. It would also be perfectly OK in *most* situations. But being OK in most situations isn't good enough. You also (as far as is possible given finite amount of total memory) want it to be OK in "pathological" situations, or at least no worse than the heap greedy version. Why should the decision to use a stack greedy definition cause a crash at 8M whereas a heap greedy definition can happily use much more without crashing? I (like everyone else) tend to avoid knowingly writing stack greedy definitions because of this. But I do this as a workaround for ghc's currently (IMO) poor stack management, not because I consider code that uses the stack to be inherently buggy. Furthermore as I said earlier, "using a lot of stack" is purely a ghc rts implementation detail. Other possible Haskell implementations may not use a lot of stack for the same function (may not use a stack at all). So you can't say a program has bugs just because it happens to cause a "stack overflow" with ghc. You might reasonably argue that it has a bug if it uses a lot of memory with any plausible Haskell implementation (one way or another) *and* you can show that there is an alternative implementation which uses asymptotically less memory. Regards -- Adrian Hey