Different stack depth for lambdas and regular functions in C++?

Question

Consider a normal recursive function:

#include <iostream>
#include <functional>

void f(unsigned long long int x) {
    std::cout << x << "\n";
    if(x < 1e9)
        f(x+1);
}

int main() {
    f(1);
    return 0;
}

This terminates at 43033.

Now consider a recursive lambda:

#include <iostream>
#include <functional>

int main() {
    std::function<void(int)> g = [&g](unsigned long long int x) {
        std::cout << x << "\n";
        if(x < 1e9)
            g(x+1);
    };
    g(1);
    return 0;
}

This terminates at a much lower stack depth of 11736.

Why do lambdas have a lower max stack depth?

(Compiling with g++ (GCC) 5.4.0, with -std=c++14 -Wall)

Also note that compiling with -O3 optimization allows for practically infinite recursion depth, but the lambda still terminates at 25k.

EDIT: Following @Yakk, here are results with the Y-combinator:

#include <iostream>
#include <functional>

using namespace std;

template <typename T, typename R>
function<R(T)> Y(function<function<R(T)>(function<R(T)>)> f) {
    // Y f = f (λx.(Y f) x)
    return f([=](T x) { return Y(f)(x); });
}

int main() {
    using fg = function<void(int)>;
    function<fg(fg)> sg = [](fg g) {
        return [g](unsigned long long int x) {
            std::cout << x << "\n";
            if(x < 1e9)
                g(x+1);
        };
    };

    Y(sg)(1);
    return 0;
}

This terminates at 4781 and 9221 with and without -O3 respectively.

Try using the lambda directly (`auto f`) I think the overhead is in `std::function ` — Motti, Sep 26 '16 at 11:25
@Motti It won't compile because it needs to know the function signature beforehand for recursion! — xyz, Sep 26 '16 at 11:28
@prakharsingh95, good point, anyway as @Yakk said the overhead is in `std::function` not in the lambda. — Motti, Sep 26 '16 at 11:36
The stack can hold N bytes. You can fit either M widgets or K gadgets in the stack. A widget and a gadget occupy different number of bytes. What's the question again? — n. m. could be an AI, Sep 26 '16 at 12:01
The -O3 infinite recursion is actually optimised to a loop due to tail call recursion optimisation implemented by the compiler. Stack space isn't required to achieve the code here so it can simply be implemented as a loop. See https://godbolt.org/g/35glKa (specifically the jmp .L6 and recursion around .L12) — Danny Birch, Sep 26 '16 at 12:05
@DannyBirch Thanks, I get that. But why not do it with `std::function`? — xyz, Sep 26 '16 at 12:06
@n.m. I am still not getting the Y-combinator and `-O3` (on lambda) results. — xyz, Sep 26 '16 at 12:08
The compiler tries harder, sees a way to avoid using the stack altogether. What's exactly inexplicable in that? — n. m. could be an AI, Sep 26 '16 at 12:13
std::function is implemented using a virtual call. You can see from the disassembly the stack usage from calling the std::function, my guess is the compiler does not implement this optimisation for one reason or another (the assembly which is produced is far more complex, perhaps this is the reason why) — Danny Birch, Sep 26 '16 at 12:13

score 5 · Accepted Answer · edited May 23 '17 at 12:16

5

std function does not mean the same thing as lambda. A std function is an object capable of storing some lambdas, or a function pointer, or a pointer to member function, or a pointer to member data, or almost any object that overrides operator() compatibly.

When you store a lambda within a std function, there is some overhead. Not much, but some. Some of this overhead may show up as using the stack more (and the overhead will be larger in unoptimized builds).

You can more directly recurse using a lambda by using the y combinator, but even there you'll be passing a reference-to-self as a parameter, and unless the recursion is eliminated by the optimizer it will probably use more stack. (A highly tweaked optimizer could notice that a stateless lambda reference argument could be eliminated, but that seems tricky to work out).

edited May 23 '17 at 12:16

Community

1
1

answered Sep 26 '16 at 11:23

Yakk - Adam Nevraumont

262,606
27
330
524

AFAIK, `std::function` are the only way to write recursive lambdas. If you can give an example it would be great! – xyz Sep 26 '16 at 11:30
@prakharsingh95 My guess is Yakk is talking about something like this - https://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/ - but yes, a more succinct summary, in the answer, would always be good. – underscore_d Sep 26 '16 at 11:52
std::function calls have an extra parameter: `Effectively does INVOKE(f, std::forward(args)..., R)` (Quote from http://en.cppreference.com/w/cpp/utility/functional/function/operator() ) – Sep 26 '16 at 11:54
@underscore_d I added the results from that as well. Still not clear to me. – xyz Sep 26 '16 at 11:56
1

@prak link to one of many y combinators for lambda on stack overflow added. There are many variations. Again, use of `std::function` is not required. `std::function` is for type erasure, nothing we are doing requires type erasure. In any case you asked why the recursive depth is shorter, the reason should be clear now, no? – Yakk - Adam Nevraumont Sep 26 '16 at 12:38

Different stack depth for lambdas and regular functions in C++?

1 Answers1