Хвост рекурсии

Question

Я реализую функцию следующим образом:

void Add(list* node)
{
    if(this->next == NULL)
        this->next = node;
    else
        this->next->Add(node);
}

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

void Add(list *node)
{
    list *curr = this;
    while(curr->next != NULL) curr = curr->next;
    curr->next = node;
}

Это не будет использовать рекурсию вообще.
Какая версия лучше?(в размере стека или скорости)
Пожалуйста, не задавайте "Почему не использовать STL / Boost / что-либо еще?"комментарии / ответы.

Answer 1

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

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

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

Answer 2

Я попробовал, создав три файла для проверки вашего кода:

node.hh:

struct list {
  list *next;
  void Add(list *);
};

tail.cc:

#include "node.hh"

void list::Add(list* node)
{
    if(!this->next)
        this->next = node;
    else
        this->next->Add(node);
}

loop.cc:

#include "node.hh"

void list::Add(list *node)
{
    list *curr = this;
    while(curr->next) curr = curr->next;
    curr->next = node;
}

Скомпилировал оба файла с G ++ 4.3 для IA32, с -O3 и -S, чтобы получить выходные данные сборки, а не объектные файлы

Результаты:

tail.s:

_ZN4list3AddEPS_:
.LFB0:
        .cfi_startproc
        .cfi_personality 0x0,__gxx_personality_v0
        pushl   %ebp
        .cfi_def_cfa_offset 8
        movl    %esp, %ebp
        .cfi_offset 5, -8
        .cfi_def_cfa_register 5
        movl    8(%ebp), %eax
        .p2align 4,,7
        .p2align 3
.L2:
        movl    %eax, %edx
        movl    (%eax), %eax
        testl   %eax, %eax
        jne     .L2
        movl    12(%ebp), %eax
        movl    %eax, (%edx)
        popl    %ebp
        ret
        .cfi_endproc

loop.s:

_ZN4list3AddEPS_:
.LFB0:
        .cfi_startproc
        .cfi_personality 0x0,__gxx_personality_v0
        pushl   %ebp
        .cfi_def_cfa_offset 8
        movl    %esp, %ebp
        .cfi_offset 5, -8
        .cfi_def_cfa_register 5
        movl    8(%ebp), %edx
        jmp     .L3
        .p2align 4,,7
        .p2align 3
.L6:
        movl    %eax, %edx
.L3:
        movl    (%edx), %eax
        testl   %eax, %eax
        jne     .L6
        movl    12(%ebp), %eax
        movl    %eax, (%edx)
        popl    %ebp
        ret
        .cfi_endproc

Вывод: выходные данные достаточно схожи (базовый цикл / рекурсия становятся равными movl, movl, testl, jne в обоих), о которых действительно не стоит беспокоиться. В рекурсивной версии есть один менее безусловный скачок, хотя я бы не хотел ставить в любом случае, который быстрее, если он вообще измерим. Выберите наиболее подходящий для выражения алгоритм. Даже если , если , вы позже решите, что это был плохой выбор, переключать его не так уж сложно.

Добавление -g к компиляции также не меняет фактическую реализацию с g ++, хотя есть дополнительное осложнение, заключающееся в том, что установка точек останова больше не ведет себя так, как вы ожидаете - точки останова на хвостовой линии вызова получают удар максимум один раз (но не для списка из 1 элемента) в моих тестах с GDB, независимо от того, насколько глубока рекурсия.

Тайминги:

Из любопытства я запустил несколько таймингов с тем же вариантом g ++. Я использовал:

#include <cstring>
#include "node.hh"

static const unsigned int size = 2048;
static const unsigned int count = 10000;

int main() {
   list nodes[size];
   for (unsigned int i = 0; i < count; ++i) {
      std::memset(nodes, 0, sizeof(nodes));
      for (unsigned int j = 1; j < size; ++j) {
        nodes[0].Add(&nodes[j]);
      }
   }
}

Это было выполнено 200 раз с каждой из версий цикла и хвостового вызова. Результаты с этим компилятором на этой платформе были довольно убедительными. В среднем у хвоста было 40,52 секунды, в то время как у виски было в среднем 66,93. (Стандартные отклонения составляли 0,45 и 0,47 соответственно).

Так что я, конечно, не боялся бы использовать рекурсию хвостового вызова, если бы это казалось более хорошим способом выражения алгоритма, но я, вероятно, тоже не стал бы использовать его, так как я подозреваю, что эти временные наблюдения скорее всего будет отличаться от платформы / компилятора (версии).