A while ago I was curious about using recursive lambdas in C++. Since Scheme was my first programming language at the university, recursion is close to my heart. Back when I first tried to use them in C++, the only idiom available (AFAIK) to do so was using the std::function functionality, which it is not optimal since it adds runtime overhead and prevent some optimizations to kick in. The subject was treated in this question:
http://stackoverflow.com/questions/17066667/overhead-of-recursive-lambdas/17067042
However, time has passed and now we have a new standard with new features. In particular we have generic lambdas in C++14 and that open a new idiom to make recursive lambdas. It’s not pretty nor elegant but have some properties that makes them interesting enough to at least being explored.
I made an example using my favourite example for recursive functions (Fibonacci). To have some reference, I also wrote two versions using std::function and a regular recursive function.
To start, let’s see how would be the ideal solution:
auto fib = [&fib](int64_t x)->int64_t
{
if(x == 0 || x == 1) return 1; else return fib(x-1) + fib(x-2);
};
Unfortunately, we cannot capture a variable declared using auto in its own initialization. Since lambdas in C++ are unique and unnamed, our big problem here is how to reference the functor that the compiler would create for us. We cannot use the this keyword inside the body of the lambda either. So, let’s cheat… Since we have generic lambdas in C++14, we can do something like this:
auto fib = [](int64_t x, const auto& lambda)->int64_t
{
if(x == 0 || x == 1)
return 1;
else return lambda(x-1,lambda) + lambda(x-2, lambda);
};
fib(35,fib);
The code above is ugly but will compile just fine. It will expands to something similar to the following code.
class /* implementation depended mangled name */
{
public:
template<typename T>
T operator () (int64_t x, T ff) const { ... }
};
*implementation depended mangled name* fib;
fib<*implementation depended mangled name*>(35, fib);
It would be awesome if the compiler would hide that reference to the same lambda for us, just the same way it hides the this pointer when calling member functions. We can do it by ourselves but still looks ugly.
auto fib = [](int64_t x)
{
auto lambda = [](int64_t x, const auto& lambda)->int64_t
{
if(x == 0 || x == 1)
return 1;
else return lambda(x-1,lambda) + lambda(x-2, lambda);
};
return lambda(x, lambda);
}
I tried this approach and compared the results with std::function approach and the regular function. The full code and the results are shown below but you can also find it on: https://bitbucket.org/pmelendez/recursive-lambdas-c
#include <iostream>
#include <functional>
#include <chrono>
using namespace std::chrono;
int64_t f(int64_t x)
{
if(x == 0 || x == 1)
return 1;
else return f(x-1) + f(x-2);
}
int main()
{
int var = 35;
std::function<int64_t(int64_t)> f1 = [&f1](int64_t x)->int64_t
{
if(x == 0 || x == 1)
return 1;
else return f1(x-1) + f1(x-2);
};
auto f2 = [](int64_t x)
{
auto lambda = [](int64_t x, const auto& ff)->int64_t
{
if(x == 0 || x == 1)
return 1;
else return ff(x-1,ff) + ff(x-2,ff);
};
return lambda(x,lambda);
};
std::cout << "Lambda in C++14 tests" << std::endl;
auto start1 = steady_clock::now();
auto res = f(var);
auto end1 = steady_clock::now();
auto diff1 = end1 - start1;
auto start2 = steady_clock::now();
auto res2 = f1(var);
auto end2 = steady_clock::now();
auto diff2 = end2 - start2;
auto start3 = steady_clock::now();
auto res3 = f2(var);
auto end3 = steady_clock::now();
auto diff3 = end3 - start3;
std::cout << "duration (normal function) : "
<< duration_cast<std::chrono::milliseconds> (diff1).count()
<< " ms" << std::endl;
std::cout << "duration (std::function) : "
<< duration_cast<std::chrono::milliseconds> (diff2).count()
<< " ms" << std::endl;
std::cout << "duration (auto) : "
<< duration_cast<std::chrono::milliseconds> (diff3).count()
<< " ms" << std::endl;
}
Results using clang++ and g++ with and without optimization:
$ ./lambda_test
Lambda in C++14 tests
Compiled using:
clang++ -std=c++14 -stdlib=libc++ main.cpp -o lambda_test
duration (normal function) : 63 ms
duration (std::function) : 427 ms
duration (auto) : 80 ms
$ ./lambda_test_opt
Lambda in C++14 tests
Compiled using:
clang++ -std=c++14 -stdlib=libc++ main.cpp -o lambda_test_opt -O3
duration (normal function) : 27 ms
duration (std::function) : 68 ms
duration (auto) : 27 ms
$ ./lambda_test_gcc
Lambda in C++14 tests
Compiled using:
g++-4.9 -std=c++1y main.cpp -o lambda_test_gcc
duration (normal function) : 61 ms
duration (std::function) : 533 ms
duration (auto) : 68 ms
$ ./lambda_test_gcc_opt
Lambda in C++14 tests
Compiled using:
g++-4.9 -std=c++1y main.cpp -o lambda_test_gcc_opt -O3
duration (normal function) : 18 ms
duration (std::function) : 57 ms
duration (auto) : 17 ms
Some interesting remarks. Without optimization, the new/ugly approach is slightly slower than the regular recursive function, but it is several times faster than the std::function approach.
However, with optimizations turned on things are way nicer. The std::function code is comparable with the regular recursive function without optimization. Moreover, the ugly approach is just as fast as the regular recursive function! If only we could fix the uglyness :)
If you are wondering why I only executed each function once instead of multiple times each, I tried both methods afterward and the results didn’t change too much. You can check the update version on Bitbutcket.
I plan to keep exploring this. Maybe one day we would have a nice way to use recursive lambdas in C++ that are as fast as regular recursive functions, we are getting close though…