develooper Front page | perl.perl5.porters | Postings from December 2017

Subject: Re: [perl #119635] deprecate and remove qsort?

From:
John P. Linderman
Date:
December 19, 2017 14:31
Subject:
Subject: Re: [perl #119635] deprecate and remove qsort?
Message ID:
CAC0cEp_vWBgkuO6DgopHP_6m23arB1nv1sop=Wv08E2vMON-vg@mail.gmail.com
​>​
On 12/18/2017 01:18 PM, Zefram wrote:
​>​
> Sawyer X wrote:
​>​
>> In other words, why avoid deprecating this cleanly as we usually do?
​>​
> Because it's never been a fully supported feature.  It has never incurred
>> the compatibility obligations that stable features do.

Long term, the _qsort subpragma surely deserves to die. It asks the users
to understand the innards of pp_sort.c, which they almost certainly won't,
and which are, in any event, subject to change. But I have long been
puzzled by the observation in perldoc -f sort that

... benchmarks indicated that for some inputs, on some platforms, the
original quicksort was faster.


​I'm now convinced that this had much less to do with platform than with
the inputs, and that

...the ability to characterize the input or output in implementation
independent ways

​
​is a worthy goal for the sort pragma. Many of us would consider a 10%
speedup in something as common as sorting ​as worth some maintainability
loss, and I believe there will be inputs for which quicksort will be
multiple times faster than mergesort. I'm trying to instrument a version of
pp_sort.c where quicksort is still present to replace "I believe" with "I
can show". In a similar vein, "I believe" that the Bentley/McIlroy quicksort

https://algs4.cs.princeton.edu/references/papers/bentley-mcilroy.pdf

with its sophisticated selection of pivot elements, will do an even better
job on such inputs. My current goal is to instrument a version of pp_sort.c
with *both* quicksort implementations, and with mergesort implementations
with and without stability enforced, and then beat the daylights out all
options to prove correctness and get an objective measure of performance.
I'll then strip out the losing implementations, and try to integrate it
with the evolving pp_sort.c. If it's decided to discard whichever quicksort
algorithm wins out, that should be easy. If it looks like it's worth
keeping, we can discuss how "characterize the input" in ways that allow
pp_sort.c to select the appropriate algorithm.



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