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

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

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

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

ОБНОВЛЕНИЕ:

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

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


c++ optimization recursion tail-call-optimization
person SRobertJames    schedule 26.05.2015    source источник
comment
Сколько хвостовых вызовов вы ожидаете примерно? На какие компиляторы вы ориентируетесь?   -  person Guvante    schedule 27.05.2015
comment
Если это действительно хвостовая рекурсия, и вам нужно точно знать, что компилятор оптимизирует рекурсию, должно быть просто закодировать ее как цикл самостоятельно.   -  person jxh    schedule 27.05.2015
comment
См. этот ответ, чтобы найти некоторые другие причины, по которым хвостовая рекурсивная функция не может быть оптимизирована.   -  person jxh    schedule 27.05.2015

Ответы (2)


arrow_upward
9
arrow_downward

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

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

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

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

person Community    schedule 26.05.2015
comment
Пример также можно было бы легко написать с циклом while, чтобы сделать его еще более понятным, но приятно видеть, что не все против goto, когда это применимо. - person Sami Kuhmonen; 27.05.2015
comment
@SamiKuhmonen Да, это то, что я имел в виду под тривиально переписанным, чтобы полностью избежать рекурсии. Спасибо. :) - person ; 27.05.2015

arrow_upward
1
arrow_downward

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

person manlio    schedule 27.05.2015