The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Message from discussion Benchmark: ST vs OM

From:
To:
Cc:
Followup To:
Subject:
 Validation: For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon.

More options Oct 2 1998, 3:00 am
Newsgroups: comp.lang.perl.misc
From: John Porter <jdpor...@min.net>
Date: 1998/10/02
Subject: Benchmark: ST vs OM
I've recently been benchmarking the relative performance of
the Schwartzian Transform (ST) (aka. map-sort-map) vs.
the Orcish Maneuver (say "OR-cache").

I recently posted some results that indicate that ST is
more than an order of magnitude slower than OM.
However, those tests were not quite realistic, in that they
discarded the results of the operation.  Apparently Perl can
optimize for this, under the right conditions.  What follows
is a benchmark wherein the results are not discarded.

#!/usr/local/bin/perl -w
use Benchmark;

# read 3100 7-letter words.  shuffle them.
my \$file = 'words.7';
open F, \$file or die "open \$file: \$!\n";
my @in = shuffle( <F> ); chomp @in; close F;
my @out;

sub control {  # explicit comparison
@out = sort { \$a cmp \$b } @in

}

sub control0 { # default comparison
@out = sort @in

}

sub ST {
@out =
map { \$_->[0] }
sort { \$a->[1] cmp \$b->[1] }
map  { [ \$_, \$_ ] }
@in;

}

sub OM {
my %c = (); # the cache
@out = sort { (\$c{\$a} ||= \$a) cmp (\$c{\$b} ||= \$b) } @in;

}

timethese( 10, {
'ST' => \&ST,
'OM' => \&OM,
'ct' => \&control,
'c0' => \&control0,

} );

sub shuffle {  # the usual Fisher-Yates shuffle.
my @i = @_;
for my \$i ( reverse ( 0 .. \$#i ) ) {
my \$j = int( rand( \$i ));
@i[\$i,\$j] = @i[\$j,\$i];
}
@i;

}

Benchmark: timing 10 iterations of OM, ST, c0, ct...
OM: 33 secs (32.51 usr  0.05 sys = 32.56 cpu)
ST: 30 secs (29.70 usr  0.09 sys = 29.79 cpu)
c0:  2 secs ( 2.52 usr  0.00 sys =  2.52 cpu)
ct: 12 secs (11.48 usr  0.00 sys = 11.48 cpu)

In these tests, I am trying to compare the underlying
algorithms of ST and OM.  Therefore, the compare keys
are identical to the original strings, rather than
keys.
Note how using an explicit {\$a cmp \$b} adds an order
of magnitude overhead.  Perl clearly optimizes for
the default sort (the implicit {\$a cmp \$b}).

--
John "Many Jars" Porter