2 ms·
The qsort() performance example in the beginning is a bit misleading. If you give the C compiler enough information (for instance an inline-able implementation
by flohofwoe 5y ago
The qsort() performance example in the beginning is a bit misleading. If you give the C compiler enough information (for instance an inline-able implementation of qsort()) then the compiler will happily "disolve" the comparison callback and custom types into a specialized "stamped out" version of qsort, just like std::qsort(). No fancy template magic needed for that, just an optimizing compiler.
The only difference between the two is that the C++ qsort implementation lives as inline code in a header file, while C's qsort lives "out of reach" in the C runtime library. If C's qsort implementation is in the same compilation unit (or LTO is used), a C compiler has the same optimization opportunities as C++.
For example here's a C qsort example where the compiler can see the qsort implementation (using an inline copy of MUSL's qsort). Note in the assembly window how the comparison callbacks have disappeared completely, this is basically C's version of "zero cost abstractions" (which really is just a fancy name for "compiler optimization passes", which isn't unique to C++):
https://www.godbolt.org/z/Mn4PfE9q7 https://www.godbolt.org/z/Mn4PfE9q7
- account42 5y agoFirst of all, qsort in C is not in-lineable and not even visible with LTO since it tends to be implemented in the C library while std::sort is always visible. Yes you can bring your own qsort, but that misses the point - you could just manually inline the comparison function at that point. Secondly. std::sort is a template with the type of the comparator being a template parameter. This means that if you use a lambda or functor as the comparator, the template will create a std::sort instance that always calls that comparater and the decision to inline the comparator is relatively simple. In controst, for the qsort example the compiler will need to either inline the whole qsort at the call site (which happens in your example) or create a specialized copy of the qsort function for your comparator. If you switch the compiler to GCC neither happens in this case (it does specialize it for some of the other parameters, but not the comparison function).