develooper Front page | perl.perl5.porters | Postings from September 2009

Re: dual pivot quicksort

Thread Previous
From:
demerphq
Date:
September 25, 2009 10:51
Subject:
Re: dual pivot quicksort
Message ID:
9b18b3110909251050s6755ba60pa2a7c7abd4cd80c0@mail.gmail.com
2009/9/25 Nicholas Clark <nick@ccl4.org>:
> John said to forward his comments about dual pivot quicksort to the list, if
> I thought they were interesting. *I* thought that they were interesting :-)
>
> Nicholas Clark
>
> ----- Forwarded message from "John P. Linderman" <jpl@research.att.com> -----
>
> Envelope-to: nick@ccl4.org
> Delivery-date: Fri, 25 Sep 2009 14:56:30 +0100
> X-Mailer: exmh version 2.7.2 01/07/2005 (debian 1:2.7.2-16) with nmh-1.2
> Subject: Re: dual pivot quicksort
> In-reply-to: <20090925125200.GE60303@plum.flirble.org>
> Comments: In-reply-to Nicholas Clark <nick@ccl4.org>
>   message dated "Fri, 25 Sep 2009 13:52:00 +0100."
> Date: Fri, 25 Sep 2009 09:56:04 -0400
> From: "John P. Linderman" <jpl@research.att.com>
>
>
>> I'm a bit confused whom we thank for Perl's current sort implementation.
>
> You can thank Tom for good parts of the quicksort implementation,
> Peter McIlroy for the good parts of the optimistic merge sort
> implementation, and me for any damage done to either.
>
>> However, as dual pivot quicksort appears to be the new black, I wondered if
>> either of you would consider it fun and rewarding to try to beat the current
>> implementation.
>
> Thanks!  I hadn't been keeping abreast of sorting theory.
>
> If I read 1) http://gdtoolbox.com/DualPivotQuicksort.pdf right,
> the improvements are solely in swaps, not in comparisons.
> 20% isn't chump change, but I'll wager that in perl, comparisons
> totally dominate the sort time (doesn't take long to swap
> a couple pointers relative to the time it takes to compare
> whatever is at them).  That may not be true for the timings
> is see in places like near the bottom of 2)
>
> http://www.reddit.com/r/programming/comments/9jj5z/vladimir_yaroslavskiys_dualpivot_quicksort/

Has an interesting comment:

http://www.reddit.com/r/programming/comments/9jj5z/vladimir_yaroslavskiys_dualpivot_quicksort/c0d1x7g

-----------------------
Several problems with this:

    * The implementation does not drop to a faster sort (e.g. optimal
sorting networks) for small n.
    * This has not been parallelized.
    * The new sort is slower on a third of the Server VM tests.

Using optimal sorting networks for small n will give much larger real
performance gains. Three-way recursion will degrade the performance of
a parallel implementation.
----------------------------------

I bet perl sort is used on short lists /a lot/. Maybe precomputing a
set of optimal sorting networks for small size arrays is worth looking
into.

Yves


-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

Thread Previous


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About