Measuring performance after Tail Call Optimization(TCO)

Question

I have an idea about what it is. My question is :-

1.) If i program my code which is amenable to Tail Call optimization(Last statement in a function[recursive function] being a function call only, no other operation there) then do i need to set any optimization level so that compiler does TCO. In what mode of optimization will compiler perform TCO, optimizer for space or time.

2.) How do i find out which all compilers (MSVC, gcc, ARM-RVCT) does support TCO

3.) Assuming some compiler does TCO, we enable it then, What is the way to find out that the compielr has actually done TCO? Will Code size, tell it or Cycles taken to execute it will tell that or both?

-AD

Answer 1

If you want your compiler to do tail call optimization, just check either

a) the doc of the compiler at which optimization level it will be performed or

b) check the asm, if the function will call itself (you dont even need big asm knowledge to spot the just the symbol of the function again)

If you really really want tail recursion my question would be:

Why dont you perform the tail call removal yourself? It means nothing else than removing the recursion, and if its removable then its not only possible by the compiler on low level but also on algorithmic level by you, that you can programm it direct into your code (it means nothing else than go for a loop instead of a call to yourself).

Answer 2

Most compilers support TCO, it is a relatively old technique. As far as how to enable it with a specific compiler, check the documentation for your compilers. gcc will enable the optimization at every optimization level except -O1, I think the specific option for this is -foptimize-sibling-calls. As far as how to tell how/if the compiler is doing TCO, look at the assembler output (gcc -S for example) or disassemble the object code.

Answer 3

1. Optimization is Compiler specific. Consult the documentation for the various optimiztion flags for them
2. You will find that in the Compilers documentation too. If you are curious, you can write a tail recursive function and pass it a big argument, and lookout for a stack-overflow. (tho checking the generated assembler might be a better choice, if you understand the code generated.)
3. You just use the debugger, and look out the address of function arguments/local variables. If they increase/decrease on each logical frame that the debugger shows (or if it actually only shows one frame, even though you did serveral calls), you know whether TCO was done or wasn't done.

Answer 4

One way to determine if tail-call is happening is to see if you can force a stack overflow. The following program does not produce a stack overflow using VC++ 2005 Express Edition and, even though its results exceed the capacity of long double rather quickly, you can tell that all of the iterations are being processed when TCO is happening:

    /* 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;
      }

Notice, however, that the simplifications to make a pure tail-call in fibcycle is tantamount to figuring out an interative version that doesn't do a tail-call at all (and will work with or without TCO in the compiler.

It might be interesting to experiment in order to see how well the TCO can find optimizations that are not already near-optimal and easily replaced by iterations.