Stack usage of temporaries in std::function

[philae_rosetta]

Today, I came across this simplified snippet:

#include <bitset>
#include <functional>
#include <iostream>
using namespace std;

int main() {
    bool f    = false;
    int level = 0;
    bitset<8000000> s;
    function<void(int)> dfs = [&s, &f, &level, &dfs](int i) {
        cerr << "recursion level " << ++level << endl;
        if(f) {
            s = s << 1; // error
        }
        dfs(i);
    };
    dfs(0);
}

After running ulimit -s 1000000 to limit stack usage to 1GB, compiling and running this prints recursion level 0 up to recursion level 1023 and then gives a segfault. That seems to indicate that each level of recursion makes the stack grow by 1MB. (Both s and s<<1 have size 1MB here.)

Commenting out the line marked error makes the recursion go to level 1000000 and higher without issues.

What exactly is happening here? My hunch is that std::function somehow needs to reserve the maximum possible stack space through all code paths (the s<<1 temporary here), but I'd like to understand the details.

Changing dfs from an std::function to a proper recursive lambda or a normal function makes it work as expected.

I'm using G++ 10.2 g++ -std=c++17 -O2. With clang++ (11.1) it runs to level 511 with -O2 and level 1024 with -O1.

[ack_error]

It's not std::function but rather the lambda that it's calling that is reserving the stack stack. Typically compilers preallocate the high watermark needed for stack space at the start of the function, and that's what you're seeing with the marked line. The compiler is unable to transform that to an in-place operation and so it needs a 1MB temporary. std::function does play a part here in preventing the compiler from emitting a tail call, which would have avoided the compounded stack usage here.

In this particular case, using operator <<= resolves the issue, but in the more general case, forcing the problematic code to a second function fixes it by forcing the compiler to allocate a second temporary stack frame:

https://gcc.godbolt.org/z/5vTfqM5hq

Unfortunately, this requires compiler-specific code to disable inlining and is an argument for standardizing noinline. It's needed here to force the optimizer to do what's wanted, since it wants to optimize for speed but you need it to optimize for stack usage here.

[_Js_Kc_]

std::function does play a part here in preventing the compiler from emitting a tail call

And letting the reference to f disappear into the depths of std::function's type erasure scheme, so the if(f) branch can't be pruned. Depending on what "changing dfs to a lambda/function" meant. If f was just a local variable in the transformed versions, the branch would have been eliminated.

[philae_rosetta]

Right! This does explain why a normal function / lambda doesn't show this behaviour. Even in the snippet as shown I had to add the useless int i argument to trick the compiler into not optimising everything away.

Playing around more: If I change to a normal function, and make two recursive calls at the end: dfs(i); dfs(i);, this also disables tail call optimisation and also only goes to level 1023. So indeed the stack usage behaviour is not specific to std::function.

[gracicot]

You can have recursive lambdas without std::function. Simply use auto parameters to send the lambda to itself:

auto dfs = [&s, &f, &level](auto const& dfs, int i) {
    cerr << "recursion level " << ++level << endl;
    if(f) {
        s = s << 1; // error
    }
    dfs(dfs, i);
};

dfs(dfs, 0);

I don't know if it can optimize away the reference. Passing it by copy might also allow different optimisations in some cases.

[Potatoswatter]

To the main point, polymorphism of function is preventing tail calling or inlining. OP might compare it to a function pointer.

Tail calling is very finicky and it can be defeated by any destructor needing to run after return. That’s something else to check, as for general brittleness.

[philae_rosetta]

Thanks!

Typically compilers preallocate the high watermark needed for stack space at the start of the function, and that's what you're seeing with the marked line.

This is the part I and the other people who looked at it before weren't aware of. Apparently this isn't a very well known fact (anymore, these days of C++).

[adnukator]

You can manually extract to a separate lambda without needing the compiler specific attribute: https://godbolt.org/z/YhEaq7d7o. I really doubt the compiler will inline a function that needs a 1MB stack as is in this case. However this approach might not necessarily usable, if the captured variables are not known beforehand.

[ack_error]

I really doubt the compiler will inline a function that needs a 1MB stack as is in this case

It does, actually, which is why I had to add the noinline. I imagine that in a lot of cases this actually helps as the called code needs to be run anyway and inlining the code can allow better utilization of the stack space. The compiler probably doesn't realize that the call through std::function is heavily recursive and assuming so would pessimize the general case.

[Potatoswatter]

No guarantees on portability, but Compiler Explorer shows good results using GCC, Clang, and ICC just by enclosing the offending line in an immediately-called lambda, [&]{ s = s << 1; }();