Front page | perl.perl5.porters |
Postings from July 2004
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