i3mr125's blog

is defining an std::function slower than the normal definition of a function ?
By i3mr125, history, 7 months ago, In English

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

code

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

code

So I really don't understand the issue here

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +44 Vote: I do not like it

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
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      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

      → Reply
  • »
    »
    7 months ago, # ^ |
    ← Rev. 2   Vote: I like it +28 Vote: I do not like it

    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

    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.

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
        ← Rev. 9   Vote: I like it +18 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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.

          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));
}

          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;
          → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      7 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      Control (global function): 5.32s

      #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;
}

      Auto: 5.84s

      #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;
}

      Std function: 5.73s

      #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;
}

      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

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
        ← Rev. 2   Vote: I like it +18 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Try tests without map

        → Reply