From: "alice" <alice@ayaya.dev>
To: <musl@lists.openwall.com>
Subject: Re: [musl] qsort
Date: Fri, 20 Jan 2023 13:55:39 +0100 [thread overview]
Message-ID: <CPX182QJK5D6.2Y2DE5NACZ1I@sumire> (raw)
In-Reply-To: <CAAEi2GextYuWRK-JKtpCLxewyJ2u380m5+s=M_0P=ZBDxyX-xA@mail.gmail.com>
On Fri Jan 20, 2023 at 2:49 AM CET, Guy wrote:
> Hi,
>
> I have a program whose bottleneck is qsort.
> I noticed that the performance with musl is much slower then with glibc.
diagnosing why this is the case is somewhat difficult without either seeing
the program, or (better), a specific corpus of things that are being sorted in
both cases (to have a solid test case).
> Why is quick sort not used in musl?
presumably, because:
/* Smoothsort, an adaptive variant of Heapsort. Memory usage: O(1).
Run time: Worst case O(n log n), close to O(n) in the mostly-sorted case. */
vanilla quicksort is O(log(n)) additional memory use, and so the optimisation
is more likely to be on memory use. on top of that, the worst-case performance
of quicksort is O(n^2) (apparently), but i'm not an expert on sorting
algorithms :). so, your specific (problem) case needs a specific example to
diagnose.
commit 22263709eda9f7d692a0f484fd759f757418dbd7 is the one that replaced the
old heapsort with this custom smoothsort implementation, with
52cf5c18f4ad3a7a59fb7113cf115c6fc05c7494 being the one that added the above
comment.
>
> Thanks,
> Guy
next prev parent reply other threads:[~2023-01-20 12:55 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 [this message]
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 ` [musl] " David Wang
2023-02-03 8:03 ` 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:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=CPX182QJK5D6.2Y2DE5NACZ1I@sumire \
--to=alice@ayaya.dev \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* 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
https://git.vuxu.org/mirror/musl/
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).