http://www.perlmonks.org?node_id=32042


in reply to Re (tilly) 1: sort performance
in thread sort performance

The 'Schwartzian Transform' is for expensive operations.
A hash lookup is not an expensive operation, so just do a plain sort.

Replies are listed 'Best First'.
RE (tilly) 3: sort performance
by tilly (Archbishop) on Sep 12, 2000 at 05:59 UTC
    You are right. I just benchmarked it. The overhead of the maps far outweighs the cost of the sort. In fact it is so slow I will have to ask p5p about it. Here is my test: 
    use strict;
use Benchmark;
use vars qw(%hash %test);

for (1..1000) {
    $hash{"key$_"}{this} = "num$_";
}

%test = (
    schwartz => sub {
        my @sorted = map $_->[0],
            sort {$a->[1] cmp $b->[1]}
            map [$_, $hash{$_}{this}], keys %hash; 
    },
    straight => sub {
        my @sorted = sort
            { $hash{$a}{this} <=> $hash{$b}{this} }
            keys %hash;
    },
    stupid => sub {
        my @sorted = sort
            {
                my $foo = [$a, $hash{$a}{this}];
                $hash{$a}{this} <=> $hash{$b}{this}
            } keys %hash;
    },
);

timethese (-1, \%test);

    [download]
    Believe it or not, stupid is several times faster for me than schwartz. IMO there is simply no possible good reason for that!
[reply]
[d/l]

      I suspect that the optimizer is just removing the whole $foo bit from "stupid" for you.

      I was wondering if $a->[1] would be much faster than $hash{$a}{this}. I didn't think it would be by a big enough factor.

      If you want raw speed here, create a side array for comparison and sort a list of indices: 

      my @list= keys %hash;
my @sort= map { $hash{$_}{this} } @list;
my @sorted= @list[
    sort { $sort[$a] cmp $sort[$b] } 0..$#sort  ];

      [download]
              - tye (but my friends call me "Tye")
[reply]
[d/l]
[select]
        I suspected that, but it cannot be because the straight method without that line is much faster, and as you change the $foo line you see the speed of the stupid sort change.

        I suspect a more fundamental issue with how map and grep are implemented, and it should IMO be fixable.

[reply]
      When faced with the ridiculous, look for the obvious. If you change all three to use the same kind of sort, Schwartz runs faster than the other two.

      *sigh*

      (Stupid user tricks.)

[reply]

        I get "schartz" 5%-30% faster than "straight" with "tye" (which you didn't time) being 50%-100% faster still (all using "cmp"). (:

                - tye (but my friends call me "Tye")
[reply]

In Section Seekers of Perl Wisdom