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 ClarkThread Previous | Thread Next