[Haskell-cafe] Haskell maximum stack depth

Adrian Hey ahey at iee.org
Thu Feb 7 12:43:43 EST 2008

Neil Mitchell wrote:
> Hi
>> But the point is that *both* heapGobbler and neilGobbler are likely to
>> be slower and chew through at least twice as much heap as stackGobbler,
>> which would be the implementation of choice for both simplicity and
>> performance if it wasn't for this stack management problem.
> Sure?

Yes, though testing stackGobbler with a large enough data set could
be problematic for the very reason we've been discsussing.

But let's say your hypothesis was correct. If so then presumably *all*
Haskell programs could give better performance than they currently do
if we nuked the stack completely and have ghc generate CPS style code.

This too would be fine with me. The problem with the current situation
is that we have perfectly sound and correct programs that "crash" quite
unnecessarily (and even if they don't get quite that far, can still
cause considerable per thread memory wastage if what SPJ says is true).
Why their authors choose to use a "stack greedy" implementation and
whether that was by design or a mistake really *isn't* the point.

As I said before (this is the third time I think), the fact that these
programs use a lot of "stack" at all is just a peculiarity of *ghc*
implementation, so it really is a ghc responsibility to do a decent
job of stack management IMO. It's not a programmer responsibility to
code in such a way that minimal "stack" is used (with ghc).

> That sounds like the thing that people can conjecture, but
> benchmarks can prove. And I'd claim that neilGobbler is the simplest
> function by a large margin.

AFAICT neilGobbler isn't even entirely safe as an implementation of
an eager take. There's nothing the Haskell standard to stop it being
transformed into..

neilGobbler :: Int -> [x] -> [x]
neilGobbler n xs = length (take n xs) `seq` take n xs

Adrian Hey

More information about the Haskell-Cafe mailing list