5 ms·

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

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.

mh7 6y ago
It's more to do with the fact that std::sort's definition is visible to the compiler and qsort() is not. Put qsort() code in stdlib.h, make it static and write a static intcmp() and you'll see the compiler inline that no problem.
- ryanianian 6y ago
  Sure you can hard-code intcmp into qsort but then it would only work for arrays of ints. 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.
  - marvy 6y ago
    I think mh7 did not mean to hard-code intcmp into qsort. The idea is to move the definition of qsort directly into the stdlib.h header file. That way, the compiler can see the definition of qsort and intcmp at the same time. In that case, the compiler could make a specialized qsort using intcmp automatically.
  - TheNewAndy 6y ago
    The poster you are replying to didn't suggest hardcoding intcmp into qsort - just making it so the implmentation of qsort is available to the compiler when the comparison function is known (i.e. just like with C++). 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.
    - bluGill 6y ago
      Only if inlining qsort is best. Sometimes it is sometimes it isn't, based on complex rules that I trust the compiler to know.
  - deleted 6y ago
    [deleted]
- deleted 6y ago
  [deleted]
- jjgreen 6y ago
  I've done this a few times using http://www.corpit.ru/mjt/qsort.html http://www.corpit.ru/mjt/qsort.html
- steerablesafe 6y ago
  I'm skeptical. I doubt that the whole of qsort gets inlined (it's big), and the best the compiler can do is to clone qsort to const-propagate the function pointer for it to get inlined. In my similar experiments with std::sort with a function pointer only gcc does this with -O3.
bluecalm 6y ago
I benchmarked it several times in the past and couldn't replicate std::sort being faster (GCC with high optimization settings). Anyway both are slow. If you need fast sort you need an implementation without any function calls (no recursive calls) and both the pivot choice and the chunk size at which insert sort kicks in optimized to your data and hardware. My experience is that you can beat built in sort by 2x to 3x.
- lumost 6y ago
  How would you perform this optimization? If it’s the same data getting sorted, why not put it in an ordered data structure?
  - mhh__ 6y ago
    Andrei Alexanrescu has a talk on doing this - he calls them metaparameters e.g. where a hybrid sort chooses to change algorithm. 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; } This made-up (pointless) benchmark measures how insert a number of cpuid instructions into the loop of a summing function affects it's runtime. My library writes the code from your specification as above to generate the instantiations and loop to measure the performance. As you might guess, the answer is a lot (CPUID is slow and serializing). edit: https://github.com/maxhaton/chimpfella https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet
jstimpfle 6y ago
I love qsort! It's easy to use. 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.

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.

mh7 6y ago

It's more to do with the fact that std::sort's definition is visible to the compiler and qsort() is not. Put qsort() code in stdlib.h, make it static and write a static intcmp() and you'll see the compiler inline that no problem.

ryanianian 6y ago
Sure you can hard-code intcmp into qsort but then it would only work for arrays of ints. 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.
- marvy 6y ago
  I think mh7 did not mean to hard-code intcmp into qsort. The idea is to move the definition of qsort directly into the stdlib.h header file. That way, the compiler can see the definition of qsort and intcmp at the same time. In that case, the compiler could make a specialized qsort using intcmp automatically.
- TheNewAndy 6y ago
  The poster you are replying to didn't suggest hardcoding intcmp into qsort - just making it so the implmentation of qsort is available to the compiler when the comparison function is known (i.e. just like with C++). 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.
  - bluGill 6y ago
    Only if inlining qsort is best. Sometimes it is sometimes it isn't, based on complex rules that I trust the compiler to know.
- deleted 6y ago
  [deleted]
deleted 6y ago
[deleted]
jjgreen 6y ago
I've done this a few times using http://www.corpit.ru/mjt/qsort.html http://www.corpit.ru/mjt/qsort.html
steerablesafe 6y ago
I'm skeptical. I doubt that the whole of qsort gets inlined (it's big), and the best the compiler can do is to clone qsort to const-propagate the function pointer for it to get inlined. In my similar experiments with std::sort with a function pointer only gcc does this with -O3.

bluecalm 6y ago

I benchmarked it several times in the past and couldn't replicate std::sort being faster (GCC with high optimization settings). Anyway both are slow. If you need fast sort you need an implementation without any function calls (no recursive calls) and both the pivot choice and the chunk size at which insert sort kicks in optimized to your data and hardware. My experience is that you can beat built in sort by 2x to 3x.

lumost 6y ago
How would you perform this optimization? If it’s the same data getting sorted, why not put it in an ordered data structure?
- mhh__ 6y ago
  Andrei Alexanrescu has a talk on doing this - he calls them metaparameters e.g. where a hybrid sort chooses to change algorithm. 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; } This made-up (pointless) benchmark measures how insert a number of cpuid instructions into the loop of a summing function affects it's runtime. My library writes the code from your specification as above to generate the instantiations and loop to measure the performance. As you might guess, the answer is a lot (CPUID is slow and serializing). edit: https://github.com/maxhaton/chimpfella https://github.com/maxhaton/chimpfella - I haven't bothered to add pmc support yet

jstimpfle 6y ago

I love qsort! It's easy to use. 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.