Comparison with the criteria for passing as a template parameter for sorting () leads to less overhead than specifying a function pointer to qsort ()?

Question

In Stroustrup, the C ++ programming language, when he discussed the design of standard libraries, said:

For example, the construction of comparison criteria in the sort function is unacceptable, since the same data can be sorted according to different criteria. This is why the standard C library qsort() takes the comparison function as an argument, rather than relying on something fixed, say, an operator. On the other hand, the overhead caused by calling the function for each comparison compromises qsort() as a building block for further building the library.

These above make sense to me. But in the second paragraph he said:

Are these serious problems? In most cases, probably not. However, function function calls may dominate the execution time for some algorithms and force users to look for alternatives. The methodology for providing comparison criteria by means of the template argument described in clause 13.4 solves the problem.

In §13.4, comparison criteria are defined as a class with static member functions (which does comparison). When these classes are used as template parameters, comparisons are still performed by their static member functions. It seems to me that there will still be overhead for calling a static member function.

What did Straustrup say when he said this?

Answer 1

std::sort is a function template. A separate instance of sort will be created for each type and comparison operator at compile time. And since for each instance of sort type and comparator are known at compile time, this allows you to embed the comparator function and, therefore, avoid the cost of calling the function.

Answer 2

There is no theoretical reason why sort should be faster than qsort . Some compilers will even embed the function pointer passed to qsort as functions: I think I saw gcc or clang (this is not for qsort ), and even when the function definition was in another cpp file.

The important part is that sort gets the function object of both type and instance. Another function is created for each such type: template are factories for functions. At the point where it is called, the exact function called is really easy to determine for each instance of such a function, so embedding is trivial.

Performing the same action using the function pointer is possible, but requires insertion from the point at which qsort is called, and careful monitoring of the immutability of the function pointer and determining the function with which it should begin. This is much more fragile than the mechanism described above in practice.

Similar problems appear with the element pitch (obviously static, when sort with an array, it’s more difficult to deal with qsort ), etc.

Answer 3

Calling a function with a pointer has two utility commands: dereferencing a pointer and overhead of a function call. This is the execution process.

Creating an instance of the template is done by the compiler. Destruction of the pointer is eliminated, since obviously there is no pointer. The overhead for functions is optimized by the compiler by nesting the call.