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.

Answer 3

Lambdas are not faster or slower than usual functions. Please correct me if wrong.

First, what is a the difference between lambda and usual function:

1. Lambda can have capture.
2. Lambda with high possibility will be simply removable during compilation from object file, due it has internal linkage.

Let's speak about capture. It doesn't give any performance to the function, due compiler has to pass additional object with data needed to handle a capture. Anyway, if you will just use lambda function in place, it will be easily optimized. Also if lambda won't use capture, you can cast your lambda to a function pointer. Why? Because it is just a usual function if it has no capture.

void (*a1)() = []() {
    // ...
};
void _tmp() {
    // ...
}
void (*a2)() = _tmp;

Both examples above are valid.

Speaking about the removal of function from object file. You can simply put your function to anonymous namespace, and it will make a deal. Function will be a little bit more happy to be inlined, due it is not used anywhere except your file.

auto a1 = []() {
    // ...
};

namespace {
    auto a2() {
        // ...
    }
}

Functions above will be the same by performance.

Also I noticed that function pointers and lambdas are compared. It is not a good thing to do because they are different. When you have a pointer to function, it can point to a variety of different functions, and it can be changed in runtime, because it is just a pointer to memory. Lambda can't do that. It always operates with only one function, due information which function to call is stored in type itself.

You can write code with function pointers like that:

void f1() {
    // ...
}
void f2() {
    // ...
}
int main() {
    void (*a)();
    a = f1;
    a = f2;
}

It is absolutely fine. And you can't write code with lambdas in this way:

int main() {
    auto f1 = []() {
        // ...
    };
    auto f2 = []() {
        // ...
    };
    f2 = f1; // error: no viable overloaded '='
}

If some libraries accept function pointers, it does not mean that lambdas can be better optimized by the compiler than plain functions, because the question is not about common libraries and function pointers.