Speed of bound lambda (via std::function) vs operator() of functor struct

Question

auto lam = [](int a, int b, int c) { return a < b && b < c; };

struct functor {
  int a;
  int b;
  bool operator()(int n) const { return a < n && n < b; }
};

In version one, we

std::vector<std::function<bool (int)>> lamvals;
// get parameters and for each
lamvals.emplace_back(std::bind(lam, a, std::placeholders::_1, b));

The alternative is

std::vector<functor> lamvals;
// get parameters and for each
lamvals.emplace_back(functor{a, b});

In both cases we have a simple iteration

    return std::any_of(lamvals.cbegin(), lamvals.cend(),
            [n](const decltype(lamvals)::value_type & t){return t(n);});

I am seeing a speed difference of 3:1, with the bound lambda slower. The functor is almost as fast as storing integer pairs and hardcoding the tests. Obviously, hardcoding is not as useful for the production code, because there will be several functions in play, not just between. However, I can go with either many functors or many lambdas. The latter is fewer lines of code and looks cleaner, but I don't think I can afford that speed difference; this code is in a critical loop.

I am looking for speedup suggestions.

Answer 1

The difference between the two cases is fundamentally that with the functor, the compiler knows exactly what will be called at compile time, so the function call can be inlined. Lambdas, interestingly enough, also have a unique type. This means again, when you use a lambda, at compile type (since the compiler must know all types) the function being called is already known, so inlining can occur. On the other hand, a function pointer is type based only on its signature. The signature must be known so that it can be called to and returned from appropriately, but other than that a function pointer can point to anything at run-time, as far as the compiler is concerned. The same is true about std::function.

When you wrap the lambda in a std::function, you erase the type of the lambda from a compiler perspective. If this sounds weird/impossible, think of it this way: since a std::function of a fixed type can wrap any callable with the same signature, the compiler has no way of knowing that some other instruction won't come alone and change what the std::function is wrapping.

This link, http://goo.gl/60QFjH, shows what I mean (by the way, the godbolt page is very very handy, I suggest getting acquainted with it). I wrote three examples here similar to yours. The first uses std::function wrapping a lambda, the second a functor, the third a naked lambda (unwrapped), using decltype. You can look at the assembly on the right and see that both of the latter two get inlined, but not the first.

My guess is that you can use lambdas to do exactly the same thing. Instead of bind, you can just do value based capture with the lambdas of a and b. Each time you push back the lambda into the vector, modify a and b appropriately, and voila.

Stylistically though, I actually strongly feel you should use the struct. It's much clearer what's going on. The mere fact that you are seeming to want to capture a and b in one place, and test against c in another, means that this is used in your code in not just one place. In exchange for like, 2 extra lines of code, you get something more readable, easier to debug, and more extensible.