[Haskell-cafe] Stack overflow

[Adrian Hey]

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