G'day rootcho,
There may be a better algorithm; however, just rearranging your code, without changing the basic logic, produced significant speed improvements: more than 30% for 8 bits and almost 50% for 64 bits.
Here's my version of your subroutine:
sub hd_Ken {
my ($diff, $bits, $count, $mask) = ($_[0] ^ $_[1], $_[2] || 8, 0);
$mask = 1 << $_, $diff & $mask && ++$count for 0 .. $bits - 1;
$count;
}
As you can see, I've eliminated a number of variables completely ($d1, $d2 and $b) and declared the reminder only once; there's less assignments and the return has been removed.
Here's my test and benchmark code:
#!/usr/bin/env perl
use strict;
use warnings;
use Benchmark qw{cmpthese};
my $x = 1 << 0;
my $y = 1 << 1 ^ 1 << 4 ^ 1 << 7 ^ 1 << 15 ^ 1 << 31 ^ 1 << 63;
my @test_results = (
hd_OP($x, $y),
hd_Ken($x, $y),
hd_OP($x, $y, 16),
hd_Ken($x, $y, 16),
hd_OP($x, $y, 32),
hd_Ken($x, $y, 32),
hd_OP($x, $y, 64),
hd_Ken($x, $y, 64),
);
print "Test results: @test_results\n";
cmpthese(-1, {
hd_OP_8 => sub { hd_OP($x, $y) },
hd_Ken_8 => sub { hd_Ken($x, $y) },
});
cmpthese(-1, {
hd_OP_16 => sub { hd_OP($x, $y, 16) },
hd_Ken_16 => sub { hd_Ken($x, $y, 16) },
});
cmpthese(-1, {
hd_OP_32 => sub { hd_OP($x, $y, 32) },
hd_Ken_32 => sub { hd_Ken($x, $y, 32) },
});
cmpthese(-1, {
hd_OP_64 => sub { hd_OP($x, $y, 64) },
hd_Ken_64 => sub { hd_Ken($x, $y, 64) },
});
sub hd_Ken {
my ($diff, $bits, $count, $mask) = ($_[0] ^ $_[1], $_[2] || 8, 0);
$mask = 1 << $_, $diff & $mask && ++$count for 0 .. $bits - 1;
$count;
}
sub hd_OP {
my ($d1,$d2,$bits) = @_;
$bits ||= 8;
my $diff = $d1 ^ $d2;
my $count = 0;
for my $b ( 0 .. $bits-1 ) {
my $mask = 1 << $b;
++ $count if $diff & $mask
}
return $count
}
Obviously, you'll want to run that on your system.
I usually run benchmarks several times to identify outliers; here's a fairly representative result:
$ pm_hamming.pl
Test results: 4 4 5 5 6 6 7 7
Rate hd_OP_8 hd_Ken_8
hd_OP_8 344926/s -- -24%
hd_Ken_8 454209/s 32% --
Rate hd_OP_16 hd_Ken_16
hd_OP_16 231849/s -- -26%
hd_Ken_16 314139/s 35% --
Rate hd_OP_32 hd_Ken_32
hd_OP_32 139183/s -- -30%
hd_Ken_32 198422/s 43% --
Rate hd_OP_64 hd_Ken_64
hd_OP_64 77282/s -- -32%
hd_Ken_64 113551/s 47% --
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.