Overhead of recursive lambdas

Question

Do recursive lambda functions induce any overhead comparing to regular recursive functions (since we have to capture them into a std::function) ?
What is the difference between this function and a similar one using only regular functions ?

int main(int argc, const char *argv[])
{
    std::function<void (int)> helloworld = [&helloworld](int count) {
        std::cout << "Hello world" << std::endl;
        if (count > 1) helloworld(--count);
    }; 
    helloworld(2);
    return 0; 
}

Answer 1

There is overhead using lambdas recursively by storing it as a std::function, although they are itself basically functors. It seems that gcc is not able to optimize well which can be seen in a direct comparison.

Implementing the behaviour of a lambda, i.e. creating a functor, enables gcc of optimizing again. Your specific example of a lambda could be implemented as

struct HelloWorldFunctor
{
   void operator()(int count) const
   {
      std::cout << "Hello world" << std::endl;
      if ( count > 1 )
      {
         this->operator()(count - 1);
      }
   }
};
int main()
{
   HelloWorldFunctor functor;
   functor(2);
}

For the example I've created the functor would look like in this second demo.

Even if one introduces calls to impure functions such as std::rand, the performance without a recursive lambda or with a custom functor is still better. Here's a third demo.

Conclusion: With the usage of a std::function, there's overhead, although it might be negligible depending on the use case. Since this usage prevents some compiler optimizations, this shouldn't be used extensively.

Answer 2

So std::function is implemented polymorphically. Meaning your code is roughly equivalent to:

struct B
{
    virtual void do(int count) = 0;
};

struct D
{
    B* b;
    virtual void do(int count)
    {
        if (count > 1)
            b->do(count--);
    }
};

int main()
{
    D d;
    d.b = &d;
    d.do(10);
}

It is rare to have a tight enough recursion such that a virtual method lookup is a significant overhead, but depending on your application area it is certainly possible.

Answer 3

Lambdas in C++ are equivalent to functors so it would be the same that calling the operator() of some class created automatically by the compiler. When you capture the environment what's happening behind the scenes is that those captured variables are passed to the constructor of the class and stored as member variables.

So in short, the performance difference should be very close to zero.

Here there is some further explanation:

Jump to the section "How are Lambda Closures Implemented?" http://www.cprogramming.com/c++11/c++11-lambda-closures.html

EDIT:

After some research and thanks to Stefan answer and code, it turned out that there is an overhead on recursive lambdas because of the std::function idiom. Since the lambda has to be wrapped on a std::function in order to call itself, it involves to call a virtual function which does add an overhead.

The subject is treated on the comments of this answer: https://stackoverflow.com/a/14591727/1112142