What does unsafePerformIO do to the stack

[Simon Marlow]

Bernd Brassel wrote:
> Thanks for your answer Simon.
> 
> Simon Marlow wrote:
>> Bernd Brassel wrote:
>>> Consider the following program:
>>>
>>> module Stack where
>>>
>>> import System.IO.Unsafe
>>>
>>> main = print (sim (replicate 1299959 ()))
>>>
>>> sim []     = True
>>> sim (_:xs) = goodStack (sim xs)
>>>
>>> goodStack x = fromJust (Just x)          --no stack overflow
>>> badStack  x = unsafePerformIO (return x) --stack overflow
>>>
>>> fromJust (Just x) = x
>> goodStack == id, and GHC even with no optimisation will transform it
>> into id, and inline it into sim.  So with goodStack, sim ends up being
>> tail-recursive.  With badStack, sim is no longer tail recursive
>> (unsafePerformIO is not inlined), so it runs out of stack.  Simple!
> 
> Is it really that simple? I guess that in a lazy language we have to
> look a bit closer to see what is tail recursive and what is not. If I
> understand you correctly, you say that if goodStack was not inlined you
> would have a bad stack as well, right?

My apologies - I oversimplified things.  You're quite right, it looks like 
the unsafePerformIO version ought to be tail-recursive too.

It turns out to be rather subtle.  If you replace unsafePerformIO by 
unsafeDupablePerformIO (from GHC.IOBase), then you do indeed get 
tail-recursion.  But this is only due to a clever trick in the RTS: what 
happens is that (sim xs) is a thunk, so when evaluating it, even in a 
tail-recursive position, an update frame is pushed on the stack.  The next 
recursive call to (sim xs) pushes another update frame on the stack, and so 
on.  Since these update frames are all adjacent to one another, a trick 
known as "stack squeezing" can squash them down into a single frame, and 
this is what happens for unsafeDupablePerformIO.

The ordinary unsafePerformIO is performing stack squeezing once per call, 
because the stack squeezing is done by the same code that does the 
"duplicate computation" check that unsafePerformIO needs to do.  Stack 
squeezing doesn't look at the same bit of stack twice, so subsequent 
squeezings don't manage to remove any update frames.  I've fixed this in my 
tree.  It also needed some tweaks to the heuristic which decides whether to 
squeeze or not based on a cost/benefit tradeoff.

So the upshot is: you can use unsafeDupablePerformIO right now, or you can 
wait until I've tested and committed this patch to get tail-recursion with 
unsafePerformIO.

I've no idea how it works in Hugs, you'll have to ask them :)

Cheers,
	Simon