Front page | perl.perl5.porters |
Postings from September 2009
Re: dual pivot quicksort
September 25, 2009 10:51
Re: dual pivot quicksort
Message ID: email@example.com
2009/9/25 Nicholas Clark <firstname.lastname@example.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" <email@example.com> -----
> Envelope-to: firstname.lastname@example.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 <email@example.com>
> message dated "Fri, 25 Sep 2009 13:52:00 +0100."
> Date: Fri, 25 Sep 2009 09:56:04 -0400
> From: "John P. Linderman" <firstname.lastname@example.org>
>> 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
> 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)
Has an interesting comment:
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
perl -Mre=debug -e "/just|another|perl|hacker/"