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

[perl #119635] deprecate and remove qsort?

Thread Next
Nicholas Clark
September 6, 2013 12:42
[perl #119635] deprecate and remove qsort?
Message ID:
# New Ticket Created by  Nicholas Clark 
# Please include the string:  [perl #119635]
# in the subject line of all future correspondence about this issue. 
# <URL: >

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 <>
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:*%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)


1) nothing will break if we removed _qsort.

2)'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/, 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

Nicholas Clark

Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About