Оптимизирует ли C ++ 11 удаленные хвостовые рекурсивные вызовы в лямбдах?
Мой предварительный ответ — нет, как видно из следующего кода теста:
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
void TestFunc (void);
int TestFuncHelper (vector<int>&, int, int);
int main (int argc, char* argv[]) {
TestFunc ();
return 0;
} // End main ()
void TestFunc (void) {
// Recursive lambda
function<int (vector<int>&, int, int)> r = [&] (vector<int>& v_, int d_, int a_) {
if (d_ == v_.size ()) return a_;
else return r (v_, d_ + 1, a_ + v_.at (d_));
};
int UpperLimit = 100000; // Change this value to possibly observe different behaviour
vector<int> v;
for (auto i = 1; i <= UpperLimit; i++) v.push_back (i);
// cout << TestFuncHelper (v, 0, 0) << endl; // Uncomment this, and the programme works
// cout << r (v, 0, 0) << endl; // Uncomment this, and we have this web site
} // End Test ()
int TestFuncHelper (vector<int>& v_, int d_, int a_) {
if (d_ == v_.size ()) return a_;
else return TestFuncHelper (v_, d_ + 1, a_ + v_.at (d_));
} // End TestHelper ()
Есть ли способ заставить компилятор оптимизировать рекурсивные хвостовые вызовы в лямбдах?
Заранее спасибо за помощь.
РЕДАКТИРОВАТЬ
Я просто хотел уточнить, что я хотел спросить, оптимизирует ли C ++ 11 рекурсивные хвостовые вызовы в лямбдах. Я использую Visual Studio 2012, но я мог бы переключаться между средами, если абсолютно известно, что GCC выполняет желаемую оптимизацию.
Решение
Вы на самом деле не делаете хвостовой вызов в «лямбда-коде», по крайней мере, не напрямую. std::function это Оболочка полиморфной функции, это означает, что он может хранить любой вызываемый объект. Лямбда в C ++ имеет уникальный, безымянный тип класса и не является std::function объект, они могут быть просто сохранены в них.
поскольку std::function использует стирание типа, он должен перепрыгнуть через несколько обручей, чтобы вызвать то, что ему изначально было передано. Эти обручи обычно выполняются либо с виртуальными функциями, либо с указателями на функции для специализаций шаблонов функций и void*,
Единственная природа косвенности делает это очень Оптимизаторам трудно видеть сквозь них. В том же духе компилятору очень трудно видеть сквозь std::function и решить, есть ли у вас хвостовой рекурсивный вызов.
Другая проблема заключается в том, что r может быть изменено изнутри r или одновременно, поскольку это простая переменная, и вдруг у вас больше нет рекурсивного вызова! С помощью идентификаторов функций это просто невозможно, они не могут менять значения на полпути.
Я просто хотел уточнить, что я хотел спросить, оптимизирует ли C ++ 11 рекурсивные хвостовые вызовы в лямбдах.
Стандарт C ++ 11 описывает поведение рабочей программы на абстрактной машине, а не то, как компилятор оптимизирует вещи. Фактически, компилятору разрешено оптимизировать вещи только в том случае, если он не меняет наблюдаемого поведения программы (исключение составляют copy-elision / (N) RVO).
Другие решения
Других решений пока нет …