SPUG: Packed Default Sort

[Yitzchak Scott-Thoennes]

Colin Meyer <cmeyer at helvella.org> wrote:
> For example, this is a common schwartz for sorting filenames by size:
> 
> map $_->[1], sort { $a->[0] <=> $b->[0] } map [-s,$_], @files;
> 
> As a packed default sort it might look like:
> 
> map substr($_,4), sort map pack("N",-s).$_, @files;
> 
> What's the benefit?  Well, calling perl subs is expensive.  When sort uses its
> built in asciibetical comparison, it doesn't need to make that expensive 
> call to a perl sub.  use Benchmark shows:

IIRC, the actual sub call is optimized away.  But it is still slower, anyway.
Oops, upon checking, I see that that optimization was only added in 5.6.0.

Stuff of interest from the 5.6.0 doc:

=head2 Enhanced support for sort() subroutines

Perl subroutines with a prototype of C<($$)>, and XSUBs in general, can
now be used as sort subroutines.  In either case, the two elements to
be compared are passed as normal parameters in @_.  See L<perlfunc/sort>.

For unprototyped sort subroutines, the historical behavior of passing
the elements to be compared as the global variables $a and $b remains
unchanged.

=head2 C<sort $coderef @foo> allowed

sort() did not accept a subroutine reference as the comparison
function in earlier versions.  This is now permitted.

=head2 Improved diagnostics

$foo::a and $foo::b are now exempt from "possible typo" warnings only
if sort() is encountered in package C<foo>.

=head2 Simple sort() using { $a <=> $b } and the like are optimized

Many common sort() operations using a simple inlined block are now
optimized for faster performance.


And from 5.7.0:

=head1 Performance Enhancements

sort() has been changed to use mergesort internally as opposed to the
earlier quicksort.  For very small lists this may result in slightly
slower sorting times, but in general the speedup should be at least
20%.  Additional bonuses are that the worst case behaviour of sort()
is now better (in computer science terms it now runs in time O(N log N),
as opposed to quicksort's Theta(N**2) worst-case run time behaviour),
and that sort() is now stable (meaning that elements with identical
keys will stay ordered as they were before the sort).

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
     POST TO: spug-list at pm.org       PROBLEMS: owner-spug-list at pm.org
      Subscriptions; Email to majordomo at pm.org:  ACTION  LIST  EMAIL
  Replace ACTION by subscribe or unsubscribe, EMAIL by your Email-address
 For daily traffic, use spug-list for LIST ;  for weekly, spug-list-digest
  Seattle Perl Users Group (SPUG) Home Page: http://www.halcyon.com/spug/