оптимизация — выполнение хвостовой рекурсии в переполнении стека

Question

оптимизация — выполнение хвостовой рекурсии в переполнении стека

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

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

ОБНОВИТЬ:

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

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

10

c++optimization recursion tail-call-optimization

Решение

Другие решения

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

#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 (без оптимизации хвостовой рекурсии) вы получаете ошибку утверждения.

1

Источник

Accepted Answer

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

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

Я рекомендую переписать его так, чтобы читателю было ясно, что происходит, но не полагался на компилятор, оптимизирующий хвостовые вызовы. Хотя ненавистный, 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;
}

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

9