4 ms·

> qsort() versus STL sorting algoritms with templates This is one of the most popular examples for superiority of template instantiation. Yet when I measured t

> qsort() versus STL sorting algoritms with templates This is one of the most popular examples for superiority of template instantiation. Yet when I measured the speedup on integer arrays (where arguably you can expect the largest speedup) it was less than 2x. Now considering also the tradeoffs that come with using C++ (larger compile times, larger binaries), and the fact that sorting is rarely a bottleneck, I'm not so sure anymore that std::sort is generally superior.

pjmlp 7y ago
That is a popular example, because it is a simple way to describe the difference between templates versus bare bones C coding. And in some scenarios even a little 2x speedup does impact With template specializations that speedup can be increased even further and since compiler does see template bodies, there are even more opportunities for the optimizer to do its work. C++ can be used in something like a Commodore 64 just fine, in fact with smaller binaries thanks to constexpr all things. CppCon 2016: Jason Turner “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17” https://www.youtube.com/watch?v=zBkNBP00wJE https://www.youtube.com/watch?v=zBkNBP00wJE
patrec 7y ago
A decent C++ compiler will also inline the sorting for something like: constexpr size_t N = 3; void sort_N(std::array<int, N> a){ std::sort(std::begin(a), std::end(a)); } but I haven't checked if it does the same with qsort. But I agree with your larger point; I find the efficiency claims for C++ frequently overblown and the compile time burden substantial (OTOH it's still very hard, but slightly easier to write robust code in C++ compared to C).
flukus 7y ago
2x is actually pretty significant consider the only difference is the way the comparer is called. Also consider how is easy it is to apply similar boosts in many scenarios with little mental overhead and it's a significant win for c++. C has _Generic though which can do the same, it seems a bit unfair to be comparing an old method kept for backward compatibility with C89 with whatever version of c++ and the compiler gained this advantage.
- jstimpfle 7y ago
  2x is only for integers, of course. Often you'll have bigger structs to sort. But anyway. If performance matters (it mostly doesn't; sorting is usually not a bottleneck), you can reap much more than 2x by various tricks - Improve the data by adding easier to compare fields - tailor sorting algorithm to the data (what machine types? can we optimize with CPU-specific assembly? Can we do radix sort?, etc) - avoid the need for sorting altogether. Often, the data can be constructed in a better way such that it falls out sorted.

pjmlp 7y ago

That is a popular example, because it is a simple way to describe the difference between templates versus bare bones C coding. And in some scenarios even a little 2x speedup does impact With template specializations that speedup can be increased even further and since compiler does see template bodies, there are even more opportunities for the optimizer to do its work. C++ can be used in something like a Commodore 64 just fine, in fact with smaller binaries thanks to constexpr all things. CppCon 2016: Jason Turner “Rich Code for Tiny Computers: A Simple Commodore 64 Game in C++17” https://www.youtube.com/watch?v=zBkNBP00wJE https://www.youtube.com/watch?v=zBkNBP00wJE

patrec 7y ago

A decent C++ compiler will also inline the sorting for something like: constexpr size_t N = 3; void sort_N(std::array<int, N> a){ std::sort(std::begin(a), std::end(a)); } but I haven't checked if it does the same with qsort. But I agree with your larger point; I find the efficiency claims for C++ frequently overblown and the compile time burden substantial (OTOH it's still very hard, but slightly easier to write robust code in C++ compared to C).

flukus 7y ago

2x is actually pretty significant consider the only difference is the way the comparer is called. Also consider how is easy it is to apply similar boosts in many scenarios with little mental overhead and it's a significant win for c++. C has _Generic though which can do the same, it seems a bit unfair to be comparing an old method kept for backward compatibility with C89 with whatever version of c++ and the compiler gained this advantage.

jstimpfle 7y ago
2x is only for integers, of course. Often you'll have bigger structs to sort. But anyway. If performance matters (it mostly doesn't; sorting is usually not a bottleneck), you can reap much more than 2x by various tricks - Improve the data by adding easier to compare fields - tailor sorting algorithm to the data (what machine types? can we optimize with CPU-specific assembly? Can we do radix sort?, etc) - avoid the need for sorting altogether. Often, the data can be constructed in a better way such that it falls out sorted.