mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Rich Felker <dalias@libc.org>
To: Alexander Monakov <amonakov@ispras.ru>
Cc: musl@lists.openwall.com, David Wang <00107082@163.com>
Subject: Re: [musl] qsort
Date: Fri, 17 Feb 2023 10:07:00 -0500	[thread overview]
Message-ID: <20230217150700.GX4163@brightrain.aerifal.cx> (raw)
In-Reply-To: <e1295590-bf80-6716-eb90-31f7fdecacb6@ispras.ru>

On Fri, Feb 17, 2023 at 04:17:05PM +0300, Alexander Monakov wrote:
> On Thu, 16 Feb 2023, Rich Felker wrote:
> 
> > Mergesort is simply not a candidate unless there's a way to make
> > in-place merge practical, but as I understand it that's prohibitively
> > costly, and I've never really seen a comprehensible implementation
> > that was convincingly correct. If I'm wrong on this and it is doable,
> > we could consider that.
> 
> *** gestures at https://www.openwall.com/lists/musl/2014/09/01/2

Thank you for reminding me of this. I had completely forgotten it. I
think I had some confusion over the performance figures that, glancing
at it now, might have been the exact same sort of "memcpy vs inline
swap" issue we've been discussing in this thread. I'm also not sure if
the bugs mentioned later in the thread were ever resolved.

I really do like the size and "simplicity" of the code, and I'm
optimistic that this might be the path to try taking for getting qsort
performance more comparable to other implementations.

Rich

  reply	other threads:[~2023-02-17 15:07 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         ` [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 [this message]
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=20230217150700.GX4163@brightrain.aerifal.cx \
    --to=dalias@libc.org \
    --cc=00107082@163.com \
    --cc=amonakov@ispras.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).