[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <5856a8f9.1e21.18615ba5922.Coremail.00107082@163.com>
Date: Fri, 3 Feb 2023 13:22:59 +0800 (CST)
From: "David Wang" <00107082@....com>
To: musl@...ts.openwall.com
Subject: Re:Re:Re: Re:Re: qsort
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@....com> wrote:
At 2023-02-02 02:01:15, "Markus Wichmann" <nullplan@....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
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
