Function or functor for std::sort?

Or avoiding dynamism for optimal performance.

Rumor has it that ~25% of CPU cycles are spent on sorting, so no wonder so much research and development went into improving its algorithms and implementations. C++ has a number of overloads for std::sort and is very flexible thanks to comparator parameter that establishes which iterator value should go first. This comparator can be a plain function, functor class or a lambda, so which one should we use and does it even matter? Let’s find out.

As expected, since lambda is essentially just a syntactic sugar for functors, their performance is identical, but the fact that they are 4X faster than sorting using a plain function may come as surprise.

But why? Well, the answer boils down to the types. When we pass a function, all compiler knows about the comparator is that it’s a

But when we pass a functor, compiler knows the concrete class that should be used for comparisons, e.g. std::less. And why does it matter? Inlining!

Inlining is a very simple yet extremely powerful compiler optimization. In our simple case, we mostly save the function call overhead but for more complicated comparators inlining may enable further optimizations.