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

Ответ 1

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

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

Что касается того, что происходит при достижении предела глубины рекурсии, пример Pubby вызывает интересную точку. [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).

Ответ 2

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

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

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; }

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

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

Стандарт говорит в 5.19 [expr.const]:

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

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

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

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

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

Рекурсия хвоста не поддерживается.

Ответ 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, по крайней мере, если функция используется в контексте, который требует постоянного выражения).

Ответ 4

Я видел, как 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 будет оптимизирован в цикл так же, как и для функций non-consexpr. Используйте как минимум -O2 и выше.

Ответ 5

"Хвост", вероятно, является неправильным для начала. 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;
}

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