From: uwe@stderr.spb.ru (Valery Ushakov)
To: musl@lists.openwall.com
Subject: [musl] Re: qsort
Date: Fri, 20 Jan 2023 13:32:05 -0000 (UTC) [thread overview]
Message-ID: <tqe54l$aln$1@ciao.gmane.io> (raw)
In-Reply-To: <CAAEi2GextYuWRK-JKtpCLxewyJ2u380m5+s=M_0P=ZBDxyX-xA@mail.gmail.com>
Guy <galfandary@gmail.com> wrote:
> I have a program whose bottleneck is qsort.
> I noticed that the performance with musl is much slower then with glibc.
> Why is quick sort not used in musl?
Sorry for a random drive by remark that is only very tangentially
related to your question... quicksort is not guaranteed to be quick
and can be quadratic on "bad" input. Everyone probably knows that in
a kind of theoretical way, but you can run into these pathological
cases in quite mundane circumstances. E.g. the NNTP overviews for the
Lua mailing list archives (gmane.comp.lang.lua.general) at gmane.io
used to trigger this worst case scenario for me (~120s to enter the ng
and sort/thread articles with qsort(3) vs. ~15s for heapsort).
-uwe
prev parent reply other threads:[~2023-01-20 13:40 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-01-20 1:49 [musl] qsort 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 ` [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 ` Valery Ushakov [this message]
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='tqe54l$aln$1@ciao.gmane.io' \
--to=uwe@stderr.spb.ru \
--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).