mailing list of musl libc
 help / color / mirror / code / Atom feed
From: "David Wang" <>
Subject: [musl] Re:[musl] Re:Re: [musl] Re:Re: [musl] qsort
Date: Fri, 3 Feb 2023 13:22:59 +0800 (CST)	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <>

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


At 2023-02-02 10:12:53, "David Wang" <> wrote:

At 2023-02-02 02:01:15, "Markus Wichmann" <> 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


  reply	other threads:[~2023-02-03  5:23 UTC|newest]

Thread overview: 34+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2023-01-20  1:49 Guy
2023-01-20 12:55 ` alice
2023-01-30 10:04   ` [musl] " David Wang
2023-02-01 18:01     ` Markus Wichmann
2023-02-02  2:12       ` [musl] " David Wang
2023-02-03  5:22         ` David Wang [this message]
2023-02-03  8:03           ` [musl] " Alexander Monakov
2023-02-03  9:01             ` [musl] " David Wang
2023-02-09 19:03       ` Rich Felker
2023-02-09 19:20         ` Alexander Monakov
2023-02-09 19:52           ` Rich Felker
2023-02-09 20:18             ` Rich Felker
2023-02-09 20:27               ` Pierpaolo Bernardi
2023-02-10  4:10             ` Markus Wichmann
2023-02-10 10:00         ` [musl] " David Wang
2023-02-10 13:10           ` Rich Felker
2023-02-10 13:45             ` [musl] " David Wang
2023-02-10 14:19               ` Rich Felker
2023-02-11  5:12                 ` [musl] " David Wang
2023-02-11  5:44                   ` alice
2023-02-11  8:39                     ` Joakim Sindholt
2023-02-11  9:06                       ` alice
2023-02-11  9:31                         ` [musl] " David Wang
2023-02-11 13:35                         ` Rich Felker
2023-02-11 17:18                           ` David Wang
2023-02-16 15:15       ` David Wang
2023-02-16 16:07         ` Rich Felker
2023-02-17  1:35           ` [musl] " David Wang
2023-02-17 13:17           ` Alexander Monakov
2023-02-17 15:07             ` Rich Felker
2023-02-11  9:22     ` [musl] " Markus Wichmann
2023-02-11  9:36       ` [musl] " David Wang
2023-02-11  9:51       ` David Wang
2023-01-20 13:32 ` [musl] qsort Valery Ushakov

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \ \ \ \

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
Code repositories for project(s) associated with this public inbox

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).