Front page | perl.perl5.porters |
Postings from September 2013
[perl #119635] deprecate and remove qsort?
Thread Next
From:
Nicholas Clark
Date:
September 6, 2013 12:42
Subject:
[perl #119635] deprecate and remove qsort?
Message ID:
rt-3.6.HEAD-1873-1378471338-1466.119635-75-0@perl.org
# New Ticket Created by Nicholas Clark
# Please include the string: [perl #119635]
# in the subject line of all future correspondence about this issue.
# <URL: https://rt.perl.org:443/rt3/Ticket/Display.html?id=119635 >
tl;dr: Nothing current uses C<use sort 'quicksort';> - should we remove it?
The sort pragma was added by this commit in 5.7.x times:
commit 84d4ea48280f6b54fdc70fe4c8b9494e3331071e
Author: Jarkko Hietaniemi <jhi@iki.fi>
Date: Wed Nov 21 22:25:14 2001 +0000
Implement the sort pragma. Split sort code from pp_ctl.c
to pp_sort.c. Includes the quicksort stabilizing layer
from John P. Linderman. -Msort=qsort or -Msort=fast is
faster than without (or with -Msort=mergesort or -Msort=safe)
for short random inputs, but for some reason not quite as fast
as 5.6.1 qsort. More benchmarking, profiling, tuning, and
optimizing definitely needed.
p4raw-id: //depot/perl@13179
Part of the reason, I think, was that v5.6 and earlier's sort was a
quicksort, and hence not a stable sort.
By the time v5.8.0 shipped, the only options offered were 'stable',
'_mergesort', '_quicksort' and the alias '_qsort', with the default as
mergesort (which is stable).
qw(_qsort) gets you a quicksort, qw(_qsort stable) gets you a quicksort with
a fallback comparison to guarantee stability. (Slower, but stable)
Of the 28 distributions that mention C<use sort>, most are in documentation:
http://grep.cpan.me/?q=%5Cbuse%5Cs%2Bsort.*%28stable%7Cqsort%7Cquicksort%7Cmergesort%7Csafe%7Cfast%29
All the code is C<use sort 'stable'> with 3 exceptions.
1) This commented-out code in a regression test:
# uncomment to enable compatibility with perl versions prior to 5.8
#use sort '_quicksort';
2) 3 examples in Module-Pragma-0.02/example/sort.t
(which is a copy of the core sort pragma from v5.10.0)
3) 2 uses in Class::Std::Containers, which fails tests with v5.10.0 and later
(and hasn't been updated to fix this)
So,
1) nothing will break if we removed _qsort.
2) sort.pm's documentation, from the start, has stated this:
You can force the
choice of algorithm with this pragma, but this feels heavy-handed,
so the subpragmas beginning with a C<_> may not persist beyond Perl 5.8.
3) We shave off some source code:
embed.fnc | 3 +-
embed.h | 3 +-
pp_sort.c | 866 -------------------------------------------------------------
proto.h | 7 +-
4 files changed, 6 insertions(+), 873 deletions(-)
[plus a bit in lib/sort.pm, which I didn't touch for this prototype]
4) We reduce the size of pp_sort.o by about 3K (or about 0.25% of perl)
but it's not exactly high maintenence code.
So, should we put _qsort through a deprecation cycle, and drop it in v5.23?
I'm not actually sure if it's worth it. Do the small gains outweigh the small
churn?
Nicholas Clark
Thread Next