develooper Front page | perl.perl5.porters | Postings from July 2004

Re: optimizing Short circuiting sort method based on [M]

Thread Previous | Thread Next
From:
Nicholas Clark
Date:
July 12, 2004 12:14
Subject:
Re: optimizing Short circuiting sort method based on [M]
Message ID:
20040712191418.GV784@plum.flirble.org
On Fri, Jul 09, 2004 at 01:10:23PM -0400, John P. Linderman wrote:
> Dave Mitchell replied to david nicol as follows:

> > No, that's for optimising away the sort block in
> > 
> >     @x = sort {$b cmp $a } @y;
> 
> I was afraid somebody might say that.  This breaks the promise of
> stability.  The order of equal elements is now reversed from the
> input order.  (I'm about to disappear on vacation, so don't
> interpret my silence as lack of interest).  -- jpl

Gosh. It takes quite a lot of effort to contrive a test that actually
demonstrate this. The simplest scenario I can think of is tied values.

"Reverse deoptimised" has sufficient extra ops to confound the peephole
optimiser and prevent it from using the (faulty) reverse optimisation:

$ cat sortstable.pl
#!perl -w

use strict;

package Oscalar;
use overload (qw("" stringify 0+ numify fallback 1)
);

sub new {
  bless [$_[1], $_[2]], $_[0];
}

sub stringify { $_[0]->[0]}

sub numify { $_[0]->[1] }

package main;

my @orig = qw (A B A C A D A E A);

my @input;
foreach (0..$#orig) {
  push @input, new Oscalar $orig[$_], $_;
}

sub report {
  printf "$_ %d\n", $_ foreach @_;
}

report @input;

print "Forwards\n";
report sort {$a cmp $b} @input;

print "Reverse\n";
report sort {$b cmp $a} @input;

print "Reverse deoptimised\n";
report sort {$$ - $$ || $b cmp $a} @input;
__END__
$ ./perl -Ilib sortstable.pl
A 0
B 1
A 2
C 3
A 4
D 5
A 6
E 7
A 8
Forwards
A 0
A 2
A 4
A 6
A 8
B 1
C 3
D 5
E 7
Reverse
E 7
D 5
C 3
B 1
A 8
A 6
A 4
A 2
A 0
Reverse deoptimised
E 7
D 5
C 3
B 1
A 0
A 2
A 4
A 6
A 8


I think that if we negate the sort comparison for reversal, rather than
reversing the order of the sorted elements, we'd be OK.

But this also means that my proposed optimisation doesn't work (directly
as I thought) - *it* ought to set this (current) reversed flag, and
the current peephole optimiser needs to flag the negation, to keep stable
sorts correctly stable.

Nicholas Clark

Thread Previous | Thread Next


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