mailing list of musl libc
 help / color / mirror / code / Atom feed
From: Alexander Monakov <>
Subject: Re: [RFC] new qsort implementation
Date: Mon, 1 Sep 2014 15:25:18 +0400 (MSK)	[thread overview]
Message-ID: <> (raw)
In-Reply-To: <20140901071243.GA6828@duality.lan>


It seems you forgot to commit changes to sorter.h in your repo.

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 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?

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?



  parent reply	other threads:[~2014-09-01 11:25 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 [this message]
2014-09-01 18:27   ` Bobby Bingham
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 \ \ \ \

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