[Haskell-cafe] Haskell maximum stack depth

[Adrian Hey]

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