SPUG: Packed Default Sort

[Colin Meyer]

Yitzchak,

On Wed, Sep 20, 2000 at 03:23:26PM -0700, Yitzchak Scott-Thoennes wrote:
> 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.

Only the simplest sort blocks are optimized in 5.6.0.  Looking at
S_simplify_sort(pTHX_ OP *o) in perl-5.6.0/op.c, it seems that in order for a
sort block to be "optimized away" it must consist of a single comparison
operator (either cmp, <=>, or <=> under use integer) and only the non
de-referenced $a and $b on either side of the comparison operator.

These blocks would be optimized:
{$a cmp $b}
{$b cmp $a}
{$a <=> $b}

These ones wouldn't:
{$a->[0] <=> $b->[0]}
{lc $a cmp lc $b}

It seems that the optimization in 5.7 will be the benefit (or detriment) of
all sorts: block, subs, or built-in asciibetical/numerical/.

-C.

 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
     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/