Рекурсия хвоста С++ с использованием 64-битных переменных

Я написал простую функцию Фибоначчи как упражнение на С++ (используя Visual Studio), чтобы проверить Tail Recursion и посмотреть, как это работает.

это код:

int fib_tail(int n, int res, int next) {
  if (n == 0) {
    return res;
  }
  return fib_tail(n - 1, next, res + next);
}

int main()
{
  fib_tail(10,0,1); //Tail Recursion works
}

когда я скомпилировался в режиме Release, я видел оптимизированную сборку, используя инструкцию JMP, несмотря на вызов. Итак, мой вывод: работа хвоста рекурсии. См. Изображение ниже:

Tail Recursion

Я хотел бы выполнить некоторые тесты производительности, увеличив входную переменную n в моей функции Fibonacci. Затем я решил изменить тип переменной, используемый в функции, от int до unsigned long long. Затем я прошел большое число, например: 10e + 08

Теперь это новая функция:

typedef  unsigned long long ULONG64;

ULONG64 fib_tail(ULONG64 n, ULONG64 res, ULONG64 next) {
   if (n == 0) {
     return res;
   }
   return fib_tail(n - 1, next, res + next);
}

int main()
{
  fib_tail(10e+9,0,1); //Tail recursion does not work
}

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

Tail Recursion doesn't work

Как вы видите сейчас, есть инструкция вызова, тогда как я ожидал только простой JMP. Я не понимаю, почему использование переменной 8 байтов отключает рекурсию хвоста. Почему компилятор не выполняет оптимизацию в этом случае?

Ответы

Ответ 1

Это один из тех вопросов, которые вы должны были спросить у парней, которые делают оптимизацию компилятора для MS - нет действительно никакой технической причины, почему ANY return type должен предотвращать переход от рекурсии хвоста как таковой - может быть Другие причины, такие как "код слишком сложный для понимания" или некоторые такие.

clang 3.7 на пару недель назад ясно показывает:

_Z8fib_tailyyy:                         # @_Z8fib_tailyyy
    pushl   %ebp
    pushl   %ebx
    pushl   %edi
    pushl   %esi
    pushl   %eax
    movl    36(%esp), %ecx
    movl    32(%esp), %esi
    movl    28(%esp), %edi
    movl    24(%esp), %ebx
    movl    %ebx, %eax
    orl %edi, %eax
    je  .LBB0_1
    movl    44(%esp), %ebp
    movl    40(%esp), %eax
    movl    %eax, (%esp)            # 4-byte Spill
.LBB0_3:                                # %if.end
    movl    %ebp, %edx
    movl    (%esp), %eax            # 4-byte Reload
    addl    $-1, %ebx
    adcl    $-1, %edi
    addl    %eax, %esi
    adcl    %edx, %ecx
    movl    %ebx, %ebp
    orl %edi, %ebp
    movl    %esi, (%esp)            # 4-byte Spill
    movl    %ecx, %ebp
    movl    %eax, %esi
    movl    %edx, %ecx
    jne .LBB0_3
    jmp .LBB0_4
.LBB0_1:
    movl    %esi, %eax
    movl    %ecx, %edx
.LBB0_4:                                # %return
    addl    $4, %esp
    popl    %esi
    popl    %edi
    popl    %ebx
    popl    %ebp
    retl


main:                                   # @main
    subl    $28, %esp
    movl    $0, 20(%esp)
    movl    $1, 16(%esp)
    movl    $0, 12(%esp)
    movl    $0, 8(%esp)
    movl    $2, 4(%esp)
    movl    $1410065408, (%esp)     # imm = 0x540BE400
    calll   _Z8fib_tailyyy
    movl    %edx, f+4
    movl    %eax, f
    xorl    %eax, %eax
    addl    $28, %esp
    retl

То же самое относится к gcc 4.9.2, если вы даете ему -O2 (но не в -O1, который был всем нужен)

(И, конечно, также в 64-битном режиме)