Насколько «умным» является оптимизация Tail-Call GCC?

Question

я просто был разговор, где были обсуждены следующие два peices кода C:

For-Loop:

#include <stdio.h> 
#define n (196607) 

int main() { 
    long loop; 
    int count=0; 
    for (loop=0;loop<n;loop++) { 
    count++; 
    } 
    printf("Result = %d\n",count); 

    return 0; 
} 

Рекурсивный:

#include <stdio.h> 
#define n (196607) 

long recursive(long loop) { 
    return (loop>0) ? recursive(loop-1)+1: 0; 
} 

int main() { 
    long result; 
    result = recursive(n); 
    printf("Result = %d\n",result); 
    return 0; 
} 

Увидев этот код, я видел recursive(loop-1)+1 и подумал: «ах, это не хвост, рекурсивный вызов», потому что он должен работать после завершения вызова recursive; ему необходимо увеличить возвращаемое значение.

Конечно, без оптимизации рекурсивный код запускает переполнение стека, как и следовало ожидать.

с флагом -O2, однако переполнение стека не встречается, что я подразумеваю, что стек используется повторно, а не толкает все больше и больше на стек - это tco.

GCC, очевидно, может обнаружить этот простой случай (+1 для возврата значения) и оптимизировать его, но как далеко он идет?

Каковы пределы того, что gcc может оптимизировать с помощью tco, когда рекурсивный вызов не является последней операцией, которую необходимо выполнить?

Приложение: Я написал полностью хвостовую рекурсивную версию кода return function();. Обертывание выше в цикле с 9999999 итераций, я придумал следующие тайминги:

$ for f in *.exe; do time ./$f > results; done 
+ for f in '*.exe' 
+ ./forLoop.c.exe 

real 0m3.650s 
user 0m3.588s 
sys  0m0.061s 
+ for f in '*.exe' 
+ ./recursive.c.exe 

real 0m3.682s 
user 0m3.588s 
sys  0m0.093s 
+ for f in '*.exe' 
+ ./tail_recursive.c.exe 

real 0m3.697s 
user 0m3.588s 
sys  0m0.077s 

так (правда, простой и не очень строгий) тест показывает, что это действительно, как представляется, в том же порядке затраченное время.

Answer 1

Просто разобрать код и посмотреть, что произошло. Без оптимизации, я получаю это:

0x0040150B cmpl $0x0,0x10(%rbp) 
0x0040150F jle 0x401523 <recursive+35> 
0x00401511 mov 0x10(%rbp),%eax 
0x00401514 sub $0x1,%eax 
0x00401517 mov %eax,%ecx 
0x00401519 callq 0x401500 <recursive> 

Но с -O1, -O2 или -O3 я получаю это:

0x00402D09 mov $0x2ffff,%edx 

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

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