[musl] Re:[musl] Re:Re: [musl] Re:Re: [musl] qsort

["David Wang" <00107082@163.com>]

I think I was not reading the mail carefully enough,  and did not notice the O(1) "in place" space complexity.
Sorry about those boring tests report,   I was just shocked to know that qsort is not quick-sort in musl.....
Please ignore my comments

David









At 2023-02-02 10:12:53, "David Wang" <00107082@163.com> wrote:



At 2023-02-02 02:01:15, "Markus Wichmann" <nullplan@gmx.net> wrote:
>On Mon, Jan 30, 2023 at 06:04:39PM +0800, David Wang wrote:

>> Is there any story about the implementation of qsort in musl?  I feel
>> it focused on performance improvement for some special kind of domain,
>> but not clear what it is.
>>
>
>Smoothsort has the desirable property of being adaptive. Its runtime
>gets closer to O(n) the more sorted the input already is. glibc uses
>mergesort or quicksort (the latter as fallback) and neither of them has
>that property. Plus, mergesort requires scratch storage and has a
>significantly harder time sorting arrays with large elements, because
>you end up constantly copying stuff. glibc tries to mitigate this by
>indirectly sorting once the elements go above 32 bytes in size.
>
>Basically, glibc is optimized for the comparisons, musl more for the
>number of swaps. Although we really shouldn't loose sight of the
>compares entirely, since those are indirect function calls, and current
>processors seem to dislike those.

Thanks for the information, but the state of things (the average performance, measure in total runtime, could be about 5~6-factor slower than c++ sort in alpine, 8~9-factor slower than qsort in debian-glibc) is very disturbing,  when I use qsort, I would expect O(nlogn) average performance with small const factor (but care less about its O(n) cases, to be honest...)  because I meant to use quick sort... and if I have concern about worst case preformance, I would switch to C++ sort (which is said to switch to merge sort when recursive depth is too deep for quicksort, but I have not confirmed it myself...).  
I time the sorting of 200000 elements randomly shuffled for 1024 rounds, the timing report for qsort on alpine is:
 # time ./a.out 
real	3m 3.20s
user	3m 3.19s
sys	0m 0.00s
c++ sort on alpine is:
real	0m 35.79s
user	0m 35.78s
sys	0m 0.00s
While qsort on debian is way much faster:
real	0m19.783s
user	0m19.783s
sys	0m0.000s

David