Tail Recursion and Tail Call Optimization: Difference between revisions
Jump to navigation
Jump to search
[unchecked revision] | [unchecked revision] |
Content deleted Content added
Okay, I delayed this way more than I thought I would... |
|||
Line 1: | Line 1: | ||
== |
== What is a tail call? == |
||
Formally, a call within a function is a tail call if the caller does not modify the state after the call and before returning. |
|||
Informally, a tail call is when a function calls another function, and returns immediately. In assembly, it's when a CALL and a RET instructions are found right next to each other. For example, in the following code: |
|||
The previous information on this page was simply put wrong. So I've deleted it. I suppose I should write the correct information instead, but I'm feeling a bit lazy right now, could you just check out Wikipedia for me? Thank you. (https://en.wikipedia.org/wiki/Tail_call) |
|||
<code> |
|||
I also happen to have made a topic on the forum about this. Still lazy though. (https://forum.osdev.org/viewtopic.php?f=8&t=33791) |
|||
myFunction: |
|||
CALL foo |
|||
CALL bar |
|||
RET |
|||
</code> |
|||
<code>CALL bar</code> is a tail call, but <code>CALL foo</code> is not. |
|||
I'll deal with this later. Probably. Hopefully. |
|||
Note that, it's important that there is no operation between <code>CALL bar</code> and <code>RET</code>. Consider the following example: |
|||
<code> |
|||
int foo(x){ |
|||
return bar(x) * 2; |
|||
} |
|||
</code> |
|||
Even though this looks like a tail call, the caller has to modify the return value after the <code>CALL</code> operation. As such, it's not actually a tail call. In assembly: |
|||
<code> |
|||
CALL bar |
|||
SHL EAX, 1 |
|||
RET |
|||
</code> |
|||
However the following is a tail call: |
|||
<code> |
|||
int foo(x){ |
|||
return bar(x * 2); |
|||
} |
|||
</code> |
|||
In assembly: |
|||
<code> |
|||
SHL EAX, 1 |
|||
CALL bar |
|||
RET |
|||
</code> |
|||
As you can see, there is no operation between <code>CALL</code> and <code>RET</code> this time. |
|||
== Optimizing a tail call == |
|||
A tail call can be optimized by simply replacing <code>CALL</code> with <code>JMP</code> and removing <code>RET</code>. So looking at this example, one more time: |
|||
<code> |
|||
int foo(x){ |
|||
return bar(x * 2); |
|||
} |
|||
</code> |
|||
In assembly, no tail call optimization: |
|||
<code> |
|||
SHL EAX, 1 |
|||
CALL bar |
|||
RET |
|||
</code> |
|||
In assembly, with tail call optimization: |
|||
<code> |
|||
SHL EAX, 1 |
|||
JMP bar |
|||
</code> |
|||
This has a minor speed up as you no longer have to save and restore the instruction pointer. The callee (in this case, <code>bar</code>) will return all the way back to the caller of this function. |
|||
It doesn't have much of an impact on a function like this, but it can have immense impact on recursive calls. A recursive call that takes 1000 recursions will have to save and restore the instruction pointer 1001 times without tail call optimization, but only once with it. |
|||
== Epilogues and Prologues == |
|||
In the above examples, it is assumed that functions don't have a prologue or epilogue which is highly impractical. As such a proper implementation of tail call optimization is a lot trickier than shown here. This is only a rudimentary example. |