Performance measurement after Tail Call Optimization (TCO)
I have an idea of what it is. My question is: -
1.) If I am programming my code that lends itself to Tail Call optimization (the last statement in the function [recursive function], which is a function call, there is no other operation), then I need to set any optimization level to the TCO compiler. In which optimization mode the compiler will perform TCO, optimizer for space or time.
2.) How to find out which compilers (MSVC, gcc, ARM-RVCT) support TCO
3.) Assuming some compiler does TCO, we enable it then. How do you know that compielr really did TCO? Will the size of the code say this or the Loops taken to execute it say this or both?
-AD
source to share
Most compilers support TCO, a relatively old technique. As for how to enable it with a specific compiler, check the documentation for your compilers. gcc will enable optimizations at every optimization level except -O1, I think there is a dedicated option for that -foptimize-sibling-calls
. As for how / if the compiler does TCO, look at the output of the assembler (for example gcc -S
) or split the object code.
source to share
- Optimization is a compiler. See the documentation for the various optimization flags for these.
- You will also find this in the Compilers documentation. If you are interested, you can write a tail recursive function and pass a large argument to it and look for a stack overflow. (inspecting the generated assembler may be the best choice if you understand the generated code.)
- You just use the debugger and look at the address of the function arguments / local variables. If they increment / decrement every logical frame the debugger shows (or in fact it only shows one frame, even if you've made multiple calls), you know if the TCO has been executed or not.
source to share
If you want your compiler to do tail call optimizations, just check
a) the compiler document on which the optimization level will run, or
b) check asm if the function will call itself (you don't even need to have any more asm knowledge to find the character symbol again)
If you really want tail recursion, my question would be:
Why don't you perform tail call removal at all? This means nothing more than removing the recursion, and if it is removable, then it is not only possible by the compiler at a low level, but also at an algorithmic level, which you can program directly into your code (this means nothing more than a loop instead of calling for yourself).
source to share
One way to determine if a callback is being executed is to see if a stack overflow can be forced. The following program does not create a stack overflow using VC ++ 2005 Express Edition and, although its results significantly exceed the throughput of a long double, you can tell that all iterations are handled when TCO is executed:
/* FibTail.c 0.00 UTF-8 dh:2008-11-23
* --|----1----|----2----|----3----|----4----|----5----|----6----|----*
*
* Demonstrate Fibonacci computation by tail call to see whether it is
* is eliminated through compiler optimization.
*/
#include <stdio.h>
long double fibcycle(long double f0, long double f1, unsigned i)
{ /* accumulate successive fib(n-i) values by tail calls */
if (i == 0) return f1;
return fibcycle(f1, f0+f1, --i);
}
long double fib(unsigned n)
{ /* the basic fib(n) setup and return. */
return fibcycle(1.0, 0.0, n);
}
int main(int argc, char* argv[ ])
{ /* compute some fibs until something breaks */
int i;
printf("\n i fib(i)\n\n");
for (i = 1; i > 0; i+=i)
{ /* Do for powers of 2 until i flips negative
or stack overflow, whichever comes first */
printf("%12d %30.20LG \n", i, fib((unsigned) i) );
}
printf("\n\n");
return 0;
}
Note, however, that the simplifications for creating a clean tail call in fibcycle are tantamount to finding out a reciprocal version that doesn't tail call at all (and will work with or without TCO in the compiler.
It might be interesting to experiment to see how well TCO can find optimizations that are not nearly optimal yet and are easily replaced by iterations.
source to share