[Haskell-cafe] Re: What I learned from my first serious attempt low-level Haskell programming

[Lennart Augustsson]

OK, so there are few extra costs for unknown tail calls.
First, there might be a pipeline stall if the jump address isn't  
loaded into a register far enough in advance before the jump.
Second, you need to pass information about the number of arguments in  
the caller.
And finally, you need to test the number of arguments in the callee.

Under the best of circumstances the argument check costs a load  
immediate, a compare, and a non-taken branch.  But looking at the  
output from ghc I doubt this is the case.

	-- Lennart

On Apr 10, 2007, at 23:13 , Stefan O'Rear wrote:

> On Tue, Apr 10, 2007 at 07:59:04PM +0100, Lennart Augustsson wrote:
>> So then tail calls should be very cheap when most of the arguments
>> don't change.
>>
>> On Apr 10, 2007, at 10:17 , Simon Marlow wrote:
>>
>>> Lennart Augustsson wrote:
>>>> It's not that hard to figure out an order to permute the arguments
>>>> on the stack before a tail call that minimizes that number of
>>>> moves and temporary locations.  Lmlc did this 20 years ago. :)
>>>
>>> Right, and that's what GHC does too, with a strongly-connected-
>>> component analysis of the dependencies between assignments of the
>>> args for the tail call.
>>>
>>> Cheers,
>>> 	Simon
>
> The tailcall in question is NOT statically known (it is a variant of
> CPS), so simpleminded tail recursion optimizations will not help much.
>
> Stefan