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.