Re: [RFC] new qsort implementation

[Bobby Bingham <koorogi@koorogi.info>]

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

Correct.

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