Выполнение хвостовой рекурсии в C++

Question

Моя функция может быть написана гораздо проще, если я рекурсия хвостового вызова (в отличие от цикла for (;;)...break). Тем не менее, я боюсь, что у меня будут проблемы с производительностью, если компилятор не сможет оптимизировать его, особенно потому, что он будет скомпилирован конечным пользователем.

1. Есть ли способ, чтобы сообщить компилятору «Убедитесь, что вы оптимизировать этот хвост вызов, либо дать мне ошибку» (например, Scala поддерживает это)

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

---

UPDATE:

Компиляторы GCC и MSVC.

Как правило, я ожидаю около десятка хвостов. Но крайний случай мог иметь тысячи. Платформа представляет собой типичный низкопроизводительный ноутбук (например, Core i3 или i5).

Answer 1

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

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

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

Возьмет простую хвостовую рекурсию функции битого подсчета:

int bitcount(unsigned int n, int acc = 0) { 
    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

Это может быть тривиальным переписан в

int bitcount(unsigned int n, int acc = 0) { 
tail_recurse: 
    if (n == 0) 
    return acc; 

    // tail return bitcount(n >> 1, acc + (n & 1)); 
    acc += n & 1; 
    n = n >> 1; 
    goto tail_recurse; 
} 

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

Answer 2

С GCC вы можете добавить проверку выполнения с помощью функции backtrace():

#include <cassert> 
#include <iostream> 
#include <execinfo.h> 

size_t start; 

size_t stack_frames() 
{ 
    void *array[16]; 
    size_t size = backtrace(array, 16); 

    // std::cout << "Obtained " << size << " stack frames.\n"; 
    return size; 
} 

bool missing_tail() 
{ 
    return stack_frames() > start + 2; 
} 

int bitcount(unsigned int n, int acc = 0) 
{ 
    assert(!missing_tail()); 

    if (n == 0) 
    return acc; 

    return bitcount(n >> 1, acc + (n & 1)); 
} 

int main() 
{ 
    start = stack_frames(); 

    std::cout << bitcount(10) << '\n'; 

    return 0; 
} 

Когда не скомпилирована с уровнем оптимизации ниже -O2 (без оптимизации хвостовой рекурсии) вы получаете отказ утверждения.