Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Sorting blocks and efficiency (in Re to Re: Algorithm::Treap)

by bart (Canon)
on Sep 08, 2003 at 09:23 UTC ( #289724=note: print w/ replies, xml ) Need Help??


in reply to Re: Algorithm::Treap
in thread Algorithm::Treap

As an aside. I've long wished that perl had a numeric sort option built in (would one extra built-in called sortn be any great burden?), so that many cases where sorting numerically currently requires the overhead of a trivial callback or user block ...
Not true. Perl does optimize some trivial sort code blocks, so if it sees something that looks like
@sorted = sort { $a <=> $b } @list;
it will turn it into a native numerical sort. Benchmarks will show that there is no significant speed difference between native sorting as string, and sorting numerically with this block: there simply is no callback overhead.

I don't know the exact list, but it looks like at least normal and reversed numerical and string comparisons are in the list of blocks that get optimized away.

Here are some benchmarks. See how close the results are, numerical sorting is typically even faster than string sortings due to a faster comparison operator. reversed_string and native are even as good as equally fast!

For comparison I've also added a "messed up" callback block which doesn't use one of the idiomatic callback blocks, and doesn't get optimized away. See how efficiency falls back to one fifth of the optimized numerical sort, from 375 iterations / second, to a mere 75, and a third of the built-in native sort. The latter is the result you were expecting for the general case.

#!/usr/bin/perl -w use strict; use Benchmark; my(@sorted, @unsorted); push @unsorted, rand 10000 for 1 .. 1000; timethese(-3, { native => sub { @sorted = sort @unsorted }, string => sub { @sorted = sort { $a cmp $b } @unsorted }, reversed_string => sub { @sorted = sort { $b cmp $a } @unsorted }, numerical => sub { @sorted = sort { $a <=> $b } @unsorted }, reversed_numerical => sub { @sorted = sort { $b <=> $a } @unsorted + }, messed_up=> sub { @sorted = sort { my $cmp = $a <=> $b; $cmp } @un +sorted }, });
Results with a Perl 5.6.1:
Benchmark: running messed_up, native, numerical, reversed_numerical, r +eversed_string, string, each for at least 3 CPU seconds... messed_up: 3 wallclock secs ( 3.29 usr + 0.00 sys = 3.29 CPU) @ 75 +.99/s (n=250) native: 3 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 CPU) @ 24 +0.89/s (n=754) numerical: 3 wallclock secs ( 3.18 usr + 0.00 sys = 3.18 CPU) @ 37 +5.16/s (n=1193) reversed_numerical: 2 wallclock secs ( 3.13 usr + 0.00 sys = 3.13 C +PU) @ 379.87/s (n=1189) reversed_string: 4 wallclock secs ( 3.62 usr + 0.00 sys = 3.62 CPU) + @ 239.78/s (n=868) string: 3 wallclock secs ( 3.24 usr + 0.00 sys = 3.24 CPU) @ 22 +6.54/s (n=734)


Comment on Sorting blocks and efficiency (in Re to Re: Algorithm::Treap)
Select or Download Code
Re: Sorting blocks and efficiency (in Re to Re: Algorithm::Treap)
by hardburn (Abbot) on Sep 08, 2003 at 14:22 UTC
    $ perl -MO=Deparse -e 'my @a = 0 .. 10; sort @a;' my(@a) = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10); sort @a; $ perl -MO=Deparse -e 'my @a = 0 .. 10; sort { $a cmp $b } @a;' my(@a) = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10); sort @a;

    So sort { $a cmp $b } @array is optimized away.

    ----
    I wanted to explore how Perl's closures can be manipulated, and ended up creating an object system by accident.
    -- Schemer

    Note: All code is untested, unless otherwise stated

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://289724]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others cooling their heels in the Monastery: (11)
As of 2014-10-02 13:15 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    What is your favourite meta-syntactic variable name?














    Results (59 votes), past polls