Why can lambdas be better optimized by the compiler than plain functions?

Question

In his book The C++ Standard Library (Second Edition) Nicolai Josuttis states that lambdas can be better optimized by the compiler than plain functions.

In addition, C++ compilers optimize lambdas better than they do ordinary functions. (Page 213)

Why is that?

I thought when it comes to inlining there shouldn't be any difference any more. The only reason I could think of is that compilers might have a better local context with lambdas and such can make more assumptions and perform more optimizations.

Answer 1

The reason is that lambdas are function objects so passing them to a function template will instantiate a new function specifically for that object. The compiler can thus trivially inline the lambda call.

For functions, on the other hand, the old caveat applies: a function pointer gets passed to the function template, and compilers traditionally have a lot of problems inlining calls via function pointers. They can theoretically be inlined, but only if the surrounding function is inlined as well.

As an example, consider the following function template:

template <typename Iter, typename F>
void map(Iter begin, Iter end, F f) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

Calling it with a lambda like this:

int a[] = { 1, 2, 3, 4 };
map(begin(a), end(a), [](int n) { return n * 2; });

Results in this instantiation (created by the compiler):

template <>
void map<int*, _some_lambda_type>(int* begin, int* end, _some_lambda_type f) {
    for (; begin != end; ++begin)
        *begin = f.operator()(*begin);
}

… the compiler knows _some_lambda_type::operator () and can inline calls to it trivially. (And invoking the function map with any other lambda would create a new instantiation of map since each lambda has a distinct type.)

But when called with a function pointer, the instantiation looks as follows:

template <>
void map<int*, int (*)(int)>(int* begin, int* end, int (*f)(int)) {
    for (; begin != end; ++begin)
        *begin = f(*begin);
}

… and here f points to a different address for each call to map and thus the compiler cannot inline calls to f unless the surrounding call to map has also been inlined so that the compiler can resolve f to one specific function.

Answer 2

Because when you pass a "function" to an algorithm you are in fact passing in a pointer to function so it has to do an indirect call via the pointer to the function. When you use a lambda you are passing in an object to a template instance specially instantiated for that type and the call to the lambda function is a direct call, not a call via a function pointer so can much more likely be inlined.