What optimization allows Functors to be inlined?

Question

At compile-time, I want to pass a (stateless) function as efficiently as possible. I see two options:

template<typename Functor>
bool PassAsArgument(int arg1, int arg2, Functor functor);

and

template<bool (*Function)(int, int)>
bool PassAsTemplateParameter(int arg1, int arg2);

The second option seemed like the obvious choice for compile-time computation, however, Effective STL #39, the C++ standard library (std::sort, std::make_heap), the C++ Core Guidelines (T.40), and this stackoverflow answer disagree. I tested the both versions on godbolt and found that the optimizations I wanted were applied (i.e., std:less<int> was inlined).

#include <functional>

template<typename Functor>
bool PassAsArgument(int arg1, int arg2, Functor functor){
    return functor(arg1, arg2);
}

template bool PassAsArgument(int, int, std::less<int>);

results in

bool PassAsArgument<std::less<int> >(int, int, std::less<int>):
        cmp     edi, esi
        setl    al
        ret

and

inline bool LessThan(int a, int b){
    return a < b;
}

template<bool (*Function)(int, int)>
bool PassAsTemplateParameter(int arg1, int arg2){
    return Function(arg1, arg2);
}

template bool PassAsTemplateParameter<LessThan>(int, int);

results in

bool PassAsTemplateParameter<&(LessThan(int, int))>(int, int):
        cmp     edi, esi
        setl    al
        ret

I want to follow the guidelines, but I'm worried that in more complicated code, I may make a mistake that disables some optimizations. For example,

1. What if Functor is not the last argument?
2. What if I call PassAsArgument with a stateful Functor?
3. What if I need to pass multiple Functors?
4. What if I need to pass Functor to func2 in the body of PassAsArgument?
5. What if I save a copy of Functor as a data member of a class?

As a starting point, I need to know what optimizations the compiler is using. The question is: What optimization allows Functors passed-by-value to be inlined?

Answer 1

Constant propagation is the key optimization.

When the lambda or functor is called, the compiler still knows which code runs, and thus it's as straightforward as inlining a function by name. If not, it's like a runtime-variable function pointer; the compiler can't inline¹.

After inlining PassAsArgument(1, 2, LessThan) into the caller that passed functor = LessThan, the functor(arg1, arg2); can be seen to be calling LessThan. So the compiler can inline your LessThan as well.

The T.40 rule you linked (In general, passing function objects gives better performance than passing pointers to functions), about using lambdas instead of raw function pointers, is only true when things inline. They do inline just as easily as function pointers when visible at compile time. But if they don't inline, a bare function pointer may be cheapest.

It doesn't need any special permission from the ISO C++ standard beyond the as-if rule since there's no change in observable behaviour.

What if I save a copy of Functor as a data member of a class?

That's likely to defeat constant-propagation, unless the compiler can prove that every member of that class could only ever had the same value assigned (this lambda, not some other in a different compilation unit it can't see).

---

Footnote 1:

If a compiler doesn't know the value of a function pointer for sure, but it has a good guess, it might compare/branch on the function pointer having that value. If it matches, it can run an inlined version of that function, with constant propagation and whatnot. Otherwise just call through the function pointer. You could call this speculative inlining.

When the function pointer in question is in a vtable, this is called "speculative devirtualization". AFAIK, that's the only time real compilers will actually attempt this, since that's when it's common to have function pointers that only ever have one value.

(Constant propagation into the function being inlined can be great if it turns runtime branches into if(false), or otherwise greatly simplifies way beyond just avoiding the call/ret and calling convention overhead.)

---

Related:

• What does the compiler optimization "constant propagation" mean? (for numeric variables)

• Are lambdas inlined like functions in C++?

• C++ Lambda Overhead - Jérôme Richard says at least some compilers might fail to inline if you wrap a lambda in a std::function. I'd assume that's based on practical experience looking at the asm, although I'm surprised; I'd expect GCC and clang at least to not have a problem inlining. But I'd easily believe MSVC did a worse job. Still looking for a better duplicate about constprop and inlining.