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.