is defining an std::function slower than the normal definition of a function ?

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

so I was solving a standard dp problem but it got TLE using this form of the calc function

code

void solve(){
    string a,b;
    cin >> a >> b;
    vector<vector<int>>dp(N,vector<int>(N,-1));
    int n = sz(a), m = sz(b);
    function<int(int,int)>calc=[&](int i,int j)->int{
        if(i==n&&j==m)
            return 0;
        if(i>n||j>m)
            return INT_MAX;
        if(~dp[i][j])
            return dp[i][j];
        int op1 = calc(i,j+1)+1;
        int op2 = calc(i+1,j)+1;
        int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
        return dp[i][j] = min({op1,op2,op3});
    };
    cout << calc(0,0);
}

and it passed by defining the same function exactly outside the solve function like this.

code

vector<vector<int>>dp(N,vector<int>(N,-1));
int n,m;
string a,b;
int calc(int i,int j){
    if(i==n&&j==m)
        return 0;
    if(i>n||j>m)
        return INT_MAX;
    if(~dp[i][j])
        return dp[i][j];
    int op1 = calc(i,j+1)+1;
    int op2 = calc(i+1,j)+1;
    int op3 = calc(i+1,j+1)+(a[i]!=b[j]);
    return dp[i][j] = min({op1,op2,op3});
}
void solve() {
    cin >> a >> b;
    n = sz(a), m = sz(b);
    cout << calc(0,0);
}

So I really don't understand the issue here

template <class Fun> class y_combinator_result { Fun fun_; public: template <class T> explicit y_combinator_result(T&& fun) : fun_(std::forward<T>(fun)) {} template <class ...Args> decltype(auto) operator()(Args&& ...args) { return fun_(std::ref(*this), std::forward<Args>(args)...); } }; template <class Fun> decltype(auto) y_combinator(Fun&& fun) { return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun)); }

#include <iostream> #include <map> using namespace std; map<int, int> basecases; int fib(int n) { if(basecases.find(n) != basecases.end()) return basecases[n]; return fib(n-1) + fib(n-2); } int main(int argc, char *argv[]) { basecases[0] = 1; basecases[1] = 1; int n = atoi(argv[1]); cout << fib(n) << endl; }

#include <iostream> #include <map> using namespace std; int main(int argc, char *argv[]) { map<int, int> basecases; basecases[0] = 1; basecases[1] = 1; auto fib=[&](const auto &f, int n) -> int { if(basecases.find(n) != basecases.end()) return basecases[n]; return f(f, n-1) + f(f, n-2); }; int n = atoi(argv[1]); cout << fib(fib, n) << endl; }

#include <iostream> #include <map> #include <bits/stdc++.h> using namespace std; int main(int argc, char *argv[]) { map<int, int> basecases; basecases[0] = 1; basecases[1] = 1; function<int(int)> fib=[&](int n) -> int { if(basecases.find(n) != basecases.end()) return basecases[n]; return fib(n-1) + fib(n-2); }; int n = atoi(argv[1]); cout << fib(n) << endl; }

Comments (12)

Write comment?

reedef

13 months ago, # |

+44

In the second example, when you call a function defined statically, the compiler knows exactly where in the code it has to jump to ahead of time, and is also able to look inside the code of the function and do optimizations based on that (including inlining, although full inlining is not possible for recursive functions like this).

When you call function<int(int,int)> it's like a virtual function. The location where the code will have to jump to is not necessarily know statically, so the compiler can't always look at the code. A sufficiently smart compiler in this case would realize that there's only one piece of code it could point to and optimize for that, but that doesn't seem to be happenning. There's also the fact that all local variable access are "capured", which means that when you reference n and m inside the lambda it's not to a known location, it points to the variable in the stack of the main function. I'm not sure what datastructures C++ uses to keep track of this but that might introduce some overhead as well.

→ Reply

i3mr125

13 months ago, # ^ |

oh, so that's why Thanks a lot. so I should just avoid this way of writing a function i guess to be on the safe side

+10

The "proper" way to have functions share global state is to use a struct, although in some cases it might be overkill. A global also works but you have to remember to clear the globals if you call the functions many times which is more bug-prone. Either way it's fine, it's mostly a case of preference

Bedge

← Rev. 2 →

+28

In addition to what reedef had said, std::function most likely would also allocate heap memory due to its polymorphic behavior (you can reassign the std::function variable with any callable object).

If you use just lambda instead of std::function:

something like this

auto calc=[&](const auto& calc, int i,int j)->int{
    ...
    int op1 = calc(calc, i,j+1)+1;
    int op2 = calc(calc, i+1,j)+1;
    int op3 = calc(calc, i+1,j+1)+(a[i]!=b[j]);
    return dp[i][j] = min({op1,op2,op3});
};
cout << calc(calc, 0,0);

It will actually be fast enough to pass the tests. Probably it's because there is less indirection when using lambda (as it is a core language feature) and the compiler is smart enough to optimize it enough. Also, there won't be any virtual function-like behavior, as lambda is just an anonymous class object, where its parentheses operator will be what you had described in the function definition, so its address could be static.

NimaAryan

auto here converts to std::function. there isn't any difference!?

The reason we can use calc inside of calc function without doing something like what you did is type of the function is specified but when we use auto it isn't.

← Rev. 9 →

+18

Not really, lambda is not a std::function. an example showing

In short, lambda is an anonymous function object. If you do something like this:

auto x = [](int a, int b) { return a + b; };
x(1, 2);

the compiler do some magic to it and transform it to something like:

struct XXX {
    int operator()(int a, int b) {
        return a + b;
    }
};
XXX x;
x(1, 2);

So the auto in above is actually XXX instead of std::function<int(int, int)>.

You could construct a std::function with lambda but they are not equivalent.

And yes because you cannot construct a lambda with naming of the type (so auto is needed), so we unfortunately have to pass calc as a const auto&, as its type is still unknown inside the calc function.

oh I didn't know that.

Btw we can use this code-snippet to not pass the function itself inside and outside of the lambda.

Example:

auto fib = y_combinator([&](auto fib, int n) -> int {
    if (n <= 1) {
      return n;
    }
    return fib(n - 1) + fib(n - 2);
});
cout << fib(23) << endl;

just tried this and apparently it was faster. I guess I will use lambda functions when there is multiple test cases since it's overall the better option and as Reedef mentioned as well, I don't want to clear the data structures defined globally in each test case since sometimes it might cost a little time. Thanks a lot

I actually tested this, and I got unexpected results (average over 10 runs, with n=43):

Control (global function): 5.32s

Auto: 5.84s

Std function: 5.73s

Seems like for this specific small function the compiler was able to optimize it quite well. Not sure why the example in the post is different

yeah, that's weird. when I tried the global function on that problem the worst case was 0.9 seconds but the lambda was 0.8 and the std::function Tle as I said lol

I think optimization could be compiler-dependent and sometimes it could optimize some trivial cases. But I also guess in your example, it could be the runtime bottleneck is due to accessing the map, so the runtime cost of std::function etc. is less significant.

oversolver

Try tests without map

i3mr125's blog