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.
for some reason I was reason "std::function" at the title. I think std::function will kill performance :)