From: Rich Felker <dalias@libc.org>
To: Bobby Bingham <koorogi@koorogi.info>
Cc: musl@lists.openwall.com
Subject: Re: [musl] [RFC] new qsort implementation
Date: Fri, 17 Feb 2023 10:51:14 -0500 [thread overview]
Message-ID: <20230217155113.GY4163@brightrain.aerifal.cx> (raw)
In-Reply-To: <20140901071243.GA6828@duality.lan>
On Mon, Sep 01, 2014 at 02:12:43AM -0500, Bobby Bingham wrote:
> Hi all,
>
> As I mentioned a while back on IRC, I've been looking into wikisort[1]
> and grailsort[2] to see if either of them would be a good candidate for
> use as musl's qsort.
I'd forgotten about this until Alexander Monakov mentioned it in the
context of the present qsort performance thread (introduced with
Message-ID: <CAAEi2GextYuWRK-JKtpCLxewyJ2u380m5+s=M_0P=ZBDxyX-xA@mail.gmail.com>)
and think it's probably worth pursuing.
Apparently there was a bug with constant blocks that would need to be
addressed.
Since then, we've also added qsort_r. Between this changing the
interface needs of the bsearch_pos function and the general avoidance
in musl of special cross-component internal interfaces, I suspect it
would make sense to just duplicate the bsearch code with the suitable
interface as a static function in qsort.c.
On performance, it looks like this already has something of an inlined
element swap, which may be a big part of the difference. So to
evaluate the degree to which it might be better, we really need to do
the same with the existing smoothsort code and compare them apples to
apples.
Regarding the sqrt, nowadays musl's sqrt is basically all integer code
except on targets with a native sqrt instruction, so it's probably not
catastrophic to performance on softfloat archs. However, it is a
little bit sketchy with respect to determinism since it's affected by
(and in turn alters) the floating point environment (rounding mode,
exception flags). I assume only an approximation within some
reasonable bounds (to ensure the desired big-O) is needed, so it
probably makes sense to do a fast integer approximation. Maybe even
something that's essentially just "wordsize minus clz, >>1, 1<<that,
multiply by 1.4 if shifted-out bit was 1" would suffice.
Rich
next prev parent reply other threads:[~2023-02-17 15:51 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2014-09-01 7:12 Bobby Bingham
2014-09-01 11:17 ` Szabolcs Nagy
2014-09-01 18:20 ` Bobby Bingham
2014-09-01 20:53 ` Rich Felker
2014-09-01 21:46 ` Bobby Bingham
2014-09-01 11:25 ` Alexander Monakov
2014-09-01 18:27 ` Bobby Bingham
2023-02-17 15:51 ` Rich Felker [this message]
2023-02-17 22:53 ` [musl] " Rich Felker
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=20230217155113.GY4163@brightrain.aerifal.cx \
--to=dalias@libc.org \
--cc=koorogi@koorogi.info \
--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).