Измерение производительности после Tail Call Optimization (TCO)

Question

У меня есть представление о том, что это такое. Мой вопрос: -

1.) Если я программирую свой код, который поддается оптимизации Tail Call (последний оператор в функции [рекурсивная функция] является только вызовом функции, никакой другой операции там нет), тогда мне нужно установить любой уровень оптимизации так, чтобы Компилятор делает TCO. В каком режиме оптимизации компилятор будет выполнять TCO, оптимизатор для пространства или времени.

2.) Как узнать, какие все компиляторы (MSVC, gcc, ARM-RVCT) поддерживают TCO

3.) Предполагая, что какой-то компилятор выполняет TCO, мы включаем его. Каким образом можно узнать, что компилятор действительно выполнил TCO? Будет ли размер кода, указывать его или циклы, взятые для его выполнения, скажет это или оба?

-AD

Answer 1

Большинство компиляторов поддерживают TCO, это относительно старая техника. Что касается того, как включить его с определенным компилятором, проверьте документацию для ваших компиляторов. gcc включит оптимизацию на каждом уровне оптимизации, кроме -O1, я думаю, что конкретная опция для этого - -foptimize-sibling-calls. Что касается того, как сказать, как / если компилятор выполняет TCO, посмотрите на вывод ассемблера (например, gcc -S) или разберите объектный код.

Answer 2

1. Оптимизация зависит от компилятора. Обратитесь к документации для различных флагов оптимизации для них
2. Вы также найдете это в документации по компиляторам. Если вам интересно, вы можете написать хвостовую рекурсивную функцию, передать ей большой аргумент и следить за переполнением стека. (проверка сгенерированного ассемблера может быть лучшим выбором, если вы понимаете сгенерированный код.)
3. Вы просто используете отладчик и просматриваете адрес аргументов функции / локальных переменных. Если они увеличиваются / уменьшаются в каждом логическом кадре, который показывает отладчик (или если он фактически показывает только один кадр, даже если вы сделали несколько вызовов), вы знаете, было ли выполнено TCO или нет.

Answer 3

Один из способов определить, происходит ли хвостовой вызов, состоит в том, чтобы проверить, можете ли вы вызвать переполнение стека. Следующая программа не производит переполнение стека при использовании VC ++ 2005 Express Edition, и, хотя ее результаты довольно быстро превосходят возможности long double, вы можете сказать, что все итерации обрабатываются, когда происходит TCO:

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

Обратите внимание, однако, что упрощение создания чистого хвостового вызова в fibcycle равносильно выяснению интерактивной версии, которая вообще не выполняет хвостовой вызов (и будет работать с TCO или без в компиляторе.

Возможно, было бы интересно поэкспериментировать, чтобы увидеть, насколько хорошо TCO может найти оптимизации, которые еще не являются почти оптимальными и легко заменяются итерациями.

Answer 4

Если вы хотите, чтобы ваш компилятор выполнял оптимизацию хвостового вызова, просто отметьте либо

a) документ компилятора, на каком уровне оптимизации он будет выполняться, или

b) проверьте asm, если функция будет вызывать сама себя (вам даже не нужны знания большого asm, чтобы снова определить только символ функции)

Если вы действительно хотите хвостовую рекурсию, мой вопрос:

Почему вы не выполняете удаление хвостового вызова самостоятельно? Это означает не что иное, как удаление рекурсии, и если ее можно удалить, то это возможно не только компилятором на низком уровне, но и на алгоритмическом уровне с вашей стороны, что вы можете запрограммировать ее непосредственно в коде (это ничего не значит, кроме как пойти на цикл вместо вызова к себе).