Может ли оценка функции constexpr выполнить оптимизацию хвостовой рекурсии

Question

Интересно, можем ли мы использовать длинные хвостовые рекурсии для constexpr в C ++ 11 для длинных циклов?

Answer 1

По правилам [implimits] реализации разрешено устанавливать предел глубины рекурсии для constexpr вычислений.Оба компилятора, которые имеют полные constexpr реализации (gcc и clang), применяют такое ограничение, используя по умолчанию 512 рекурсивных вызовов, как предложено стандартом.Для обоих этих компиляторов, а также для любой другой реализации, которая следует предложению стандарта, оптимизация хвостовой рекурсии была бы по существу не обнаруживаемой (если в противном случае компилятор не аварийно завершил бы работу, не достигнув своего предела рекурсии).

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

Что касается того, что происходит при достижении предела глубины рекурсии, пример Пабби поднимает интересный момент.[expr.const]p2 указывает, что

вызов функции constexpr или конструктора constexpr, который превысил бы пределы рекурсии, определенные реализацией (см. Приложение B);

не являетсяпостоянное выражение.Поэтому, если предел рекурсии достигнут в контексте, который требует постоянного выражения, программа является плохо сформированной.Если функция constexpr вызывается в контексте, который не требует постоянного выражения, реализация, как правило, не обязана пытаться оценить ее во время перевода, но если она выбирает и предел рекурсии достигнут, это необходимовместо этого выполнить вызов во время выполнения.В полной, скомпилированной тестовой программе:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
constexpr unsigned long long k = f(0xffffffff);

GCC говорит:

depthlimit.cpp:4:46:   in constexpr expansion of ‘f(4294967295ull, 0ull)’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
[... over 500 more copies of the previous message cut ...]
depthlimit.cpp:2:23:   in constexpr expansion of ‘f((n + -1ull), (s + n))’
depthlimit.cpp:4:46: error: constexpr evaluation depth exceeds maximum of 512 (use -fconstexpr-depth= to increase the maximum)

, а clang говорит:

depthlimit.cpp:4:30: error: constexpr variable 'k' must be initialized by a constant expression
constexpr unsigned long long k = f(0xffffffff);
                             ^   ~~~~~~~~~~~~~
depthlimit.cpp:2:14: note: constexpr evaluation exceeded maximum depth of 512 calls
  return n ? f(n-1,s+n) : s;
             ^
depthlimit.cpp:2:14: note: in call to 'f(4294966784, 2194728157440)'
depthlimit.cpp:2:14: note: in call to 'f(4294966785, 2190433190655)'
depthlimit.cpp:2:14: note: in call to 'f(4294966786, 2186138223869)'
depthlimit.cpp:2:14: note: in call to 'f(4294966787, 2181843257082)'
depthlimit.cpp:2:14: note: in call to 'f(4294966788, 2177548290294)'
depthlimit.cpp:2:14: note: (skipping 502 calls in backtrace; use -fconstexpr-backtrace-limit=0 to see all)
depthlimit.cpp:2:14: note: in call to 'f(4294967291, 17179869174)'
depthlimit.cpp:2:14: note: in call to 'f(4294967292, 12884901882)'
depthlimit.cpp:2:14: note: in call to 'f(4294967293, 8589934589)'
depthlimit.cpp:2:14: note: in call to 'f(4294967294, 4294967295)'
depthlimit.cpp:4:34: note: in call to 'f(4294967295, 0)'
constexpr unsigned long long k = f(0xffffffff);
                                 ^

Если мы изменим код так, чтобыоценка не должна выполняться во время перевода:

constexpr unsigned long long f(unsigned long long n, unsigned long long s=0) {
  return n ? f(n-1,s+n) : s;
}
int main(int, char *[]) {
  return f(0xffffffff);
}

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

Answer 2

Не понимаю, почему это невозможно, но это качество деталей реализации.

Традиционно для шаблонов традиционно использовалось, например, запоминание, чтобы компиляторы больше не давились:

template <size_t N>
struct Fib { static size_t const value = Fib <N-1>::value + Fib<N-2>::value; };

template <>
struct Fib<1> { static size_t const value = 1; }

template <>
struct Fib<0> { static size_t const value = 0; }

, но вместо этого запомните уже вычисленное значение, чтобы уменьшить сложность его оценки до O (N).

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

Стандарт гласит: 5.19 [expr.const] :

2 / Условное выражение является основным константным выражением, если оно не включает одно из следующего в качестве потенциально вычисляемого подвыражения (3.2) [...]:

• вызов функции constexpr или конструктора constexpr, который превысил бы определенные рекурсией пределы реализации (см. Приложение B);

И читать Приложение B:

2 / Пределы могут ограничивать количества, которые включают те, которые описаны ниже, или другие. Число в скобках после каждого количества рекомендуется как минимальное для этого количества. Однако эти количества являются лишь ориентировочными и не определяют соответствие.

• Рекурсивные вызовы функции constexpr [512].

Хвостовая рекурсия не брошена.

Answer 3

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

constexpr unsigned ack( unsigned m, unsigned n )
{
    return m == 0
        ? n + 1
        : n == 0
        ? ack( m - 1, 1 )
        : ack( m - 1, ack( m, n - 1 ) );
}

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

Answer 4

"Хвост", вероятно, неправильно для начала.constexpr функции намного ближе к математическим функциям.Для математических функций следующие две функции идентичны:

constexpr unsigned long long fun1(unsigned long long n) {
  if (n == 0) return 0 ;
  return n + fun1(n-1);
}
constexpr unsigned long long fun2(unsigned long long n) {
  if (n != 0) return n + fun2(n-1);
  return  0;
}

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

Answer 5

Я видел, как GCC выполняет эту оптимизацию.Вот пример:

constexpr unsigned long long fun1(unsigned long long n, unsigned long long sum = 0) {
  return (n != 0) ? fun1(n-1,sum+n) : sum;
}
fun1(0xFFFFFFFF);

Работает на -O2, иначе вылетает.

Удивительно, но и оптимизирует это:

constexpr unsigned long long fun2(unsigned long long n) {
  return (n != 0) ? n + fun2(n-1) : 0;
}

Я проверял разборкуформы non-conspexpr, и я могу подтвердить, что она оптимизируется в цикл.

Но не это:

constexpr unsigned long long fun3(unsigned long long n) {
  return (n != 0) ? n + fun3(n-1) + fun3(n-1) : 0;
}

Таким образом, в заключение, GCC оптимизирует в цикл так же, как и для функций, не связанных с последовательностью.Используйте как минимум -O2 и выше.