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);
    Believe it or not, stupid is several times faster for me than schwartz. IMO there is simply no possible good reason for that!

      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 ];
              - tye (but my friends call me "Tye")
        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.

      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.


      (Stupid user tricks.)

        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")