[tpm] OID sorting

[Fulko Hew]

I just thought I'd follow up on the discussion I started last week.
(Thanks to all who participated!)

Attached is my current version of the test harness based on
Abram's work, and most if not all supplied routines and
suggestions (even your's Uri, now that I had the time to
look!)

My conclusions:

1/ Abram's 'nounpacksort' was the most efficient.
2/ Uri's rehash of my original code wins as the most readable.
   (I know it had ugly 'C' constructs, but I couldn't think of a better
   more Perl'ish way (see bonus points below))
3/ My original code wasn't all that bad :-)
4/ Adding the tuple idea yields noticeable improvements.

Uri also gets bonus points for showing me that I could do this
kind of in-place substitution... on a list:

   s/ //g foreach @oids;

Uri also gets extra bonus points for teaching me to use
regex's with embedded code.  I always knew it could be done
but never spent the time to learn it, nor recognize when
it would be useful.  Now (dammit), thanks to Uri, I know.

    s/(\d+)/sprintf('%8s', $1)/ge foreach @oids;

And oh yes... printing the 'number as a string' _is_ faster
than printing a 'number as a number'!

Here's the benchmark results:

                     s/iter    Improvement
abram_whilecmp         7.05             --
indy_slow_sort         6.89             2%
henrys_sort            5.52            28%
fulko_sort_uri         1.79           294%
fulko_sort_orig        1.77           299%
abram_swartzpacksort   1.55           356%
abram_packsort         1.41           400%
fulko_sort             1.14           519%
abram_nounpacksort    0.905           679%

Oh... another thing I learned...

When running benchmarks... turn off Centrino auto-CPU-speed-mechanism!
I was having a hell of a time trying to figure out
why my results were always all over the map.  :-(

Finally, for those who want to see the (current) winners,
without having to look at the attachment, they are:

For Readability:

sub fulko_sort_uri {
    my @oids = @_;

    s/(\d+)/sprintf('%8s', $1)/ge foreach @oids;
    @oids = sort @oids;
    s/ //g foreach @oids;
    return @oids;
}

For Fastest:

sub abram_nounpacksort {
    my @data = map { [ split(/\./, $_) ] } @_;
    my @sorted = map { $_->[1] }
        sort { $a->[0] cmp $b->[0] }
            map { [pack("N*",@$_),$_] } @data;
    @sorted = map { join(".",@$_) } @sorted;
    return @sorted;
}
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/toronto-pm/attachments/20090506/2fb17034/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: fulko.pl
Type: application/x-perl
Size: 6389 bytes
Desc: not available
URL: <http://mail.pm.org/pipermail/toronto-pm/attachments/20090506/2fb17034/attachment.bin>