mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Bobby Bingham <>
Subject: Re: [RFC] new qsort implementation
Date: Mon, 1 Sep 2014 13:27:27 -0500	[thread overview]
Message-ID: <20140901182727.GB7301@duality.lan> (raw)
In-Reply-To: <>

[-- Attachment #1: Type: text/plain, Size: 2228 bytes --]

On Mon, Sep 01, 2014 at 03:25:18PM +0400, Alexander Monakov wrote:
> Hi,
> It seems you forgot to commit changes to sorter.h in your repo.

Yes, that's fixed now.

> Comparing musl-heapsort to musl-smoothsort, the former appears significantly
> better than the latter except on "sorted" input, and even then it's not 20x
> faster like the musl commit adding smoothsort claims (about 6.6x for me).  It
> does reduce the number of comparisons by 20x there, as the commit says.

There is one difference between the musl heapsort in my repo compared to
what was used in musl, and that's the swap function.  The one in musl
worked with 3 memcpys in a loop with a 256 byte temporary buffer.  When
I added it to my test program, I made it use the swap function I'd
already written for grailsort/wikisort, which essentially inlines the
same concept.  That could explain the speed discrepancy.

> There is variation on how divide-and-conquer algorithms in your test handle
> sorting on the lowest level; for instance grailsort_ref uses insertion sort
> and your implementations use a sorting network (is that correct?).  Would your


> comparison be more apples-to-apples if all compared approaches used the same
> sorter on the last level, if appropriate (assuming sorting networks improve
> performance in some cases)?
> Why did you choose to use sorting networks in your implementations?

Primarily because of I've heard Rich say on IRC a few times now that
sorting networks are a better choice for small sizes than insertion
sort, and I trust his opinion on this sort of thing.

It would be interesting to do a more apples to apples comparison.

> For wikisort and grailsort, their "ref" variants perform about 2x faster
> on some tests for me .  Is that due to last-level sorter choice, or are there
> other significant differences?

TBH, I haven't spent as much time as I should deciphering everything
that's going on in the reference implementations.  I suspect that a
large part of their complexity comes from optimizing for all sorts of
different cases, and even if it does account for a 2x speedup, I don't
think we'd want to introduce that much bloat in musl.

> Thanks.
> Alexander

Bobby Bingham

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

  reply	other threads:[~2014-09-01 18:27 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 [this message]
2023-02-17 15:51 ` [musl] " Rich Felker
2023-02-17 22:53   ` 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:

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

  git send-email \
    --in-reply-to=20140901182727.GB7301@duality.lan \ \ \

* 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).