Also lack of generics can make it slow, e.g. qsort() requires a function call for each comparison. So C++'s std::sort() can be significantly faster on an array of integers.
You could do some macro magic instead of templates e.g. `DEFINE_QSORT(int, intcmp)` which could stamp out `qsort_int` but that's not a part of the stdlib.
C++ arguably gets this right since sort<int> and sort<string> will be separate functions, although templates are of course a footgun. And of course duping the logic for std::sort<T> for a bunch of different T impls increases the binary size.
In that case, the compiler could make a specialized qsort using intcmp automatically.
When this is done, the compiler can inline qsort, and replace the indirect function call with an inlined version of intcmp, and then things are equivalent.
In my similar experiments with std::sort with a function pointer only gcc does this with -O3.
One library I have exploits the fact that D templates are embarrassingly better than C++'s, so you can actually benchmark a template against it's parameters in a clean manner without overhead - that could be anything from a size_t parameter for a sort or a datastructure for example.
enum cpuidRange = iota(1, 10).map!(ctfeRepeater).array;
@TemplateBenchmark!(0, cpuidRange)
@FunctionBenchmark!("Measure", iota(1, 10), (_) => [1, 2, 3, 4])(meas)
static int sum(string asmLine)(inout int[] input)
{
int tmp;
foreach (i; input)
{
tmp += i;
mixin("asm { ", asmLine, ";}");
}
return tmp;
}
edit: https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet
When I once tested std::sort against qsort (sorting 4-byte integer) I measure a 2x difference. So yes, definitely non-trivial, but it won't get much worse than that.
Have you ever seen a program that was slow because of a slow sorting routine?
If you ever need a fast sort (~ never) then the last thing you should do is use std::sort anyway. You should figure out what your data looks like and hand roll an implementation. For example, a radix sort is often possible to use, easy to implement, and much faster than std::sort.