Re: Re: Converting an array of bytes into a BigInt

Cool benchmark. I did a couple of variants of your routine to see if removing the map and simplifying the code helped. Interestingly it didn't really. The one called "unpack" is the furthest departure from your code but is neglibly faster when averaged over a few benchmarks. Also interesting was that the "clean" version without the map was consistently slower than yours, as well as any of the modifier versions.

It would be interesting to put the other offered solutions into the benchmark, but sleep calls.

BTW, you get a more accurate average if you use a negative timing. Benchmark.pm will run the benchmark until the clock ticks over, whereas unless your count is really high you stand a good chance of being on the misleading side of the tick.

Cheers,

#!/usr/bin/perl -w
use strict;
use warnings;

use Math::BigInt;
use Benchmark 'cmpthese';

our $bigint;
our @bytes;

sub bigint_to_bytearray {
  my $bigint = shift;
  my @bytes;
  while(1) {
    my ($q,$r) = $bigint->brsft(8);
    push(@bytes,$r+0);
    last if $q == 0;
    $bigint = Math::BigInt->new($q);
  }
  return @bytes;
}
## This is the one I would like to speed up
## The array looks something like (127,6,64,27,166,33 .... )
sub bytearray_to_bigint {
  my @array = @_;
  my $count = Math::BigInt->new('0');
  my $result = Math::BigInt->new('0');
  foreach my $a (@array) {
    $result += $a * (256**$count++);
  }
  return $result;
}

sub bytearray_to_bigint2 {
    my $result = Math::BigInt->new('0');
    for my $byte (reverse @_) {
        my $tmp  = Math::BigInt->new($byte);
        $result  = $result->blsft(8);
        $result += $tmp;
    }
    return $result;
}

sub ba2bi2 {
    my @ba = reverse (@_, (0) x (4 - ( @_%4 || 4 ) ) );
    my $result = Math::BigInt->new(0);
    $result *= 4294967296
    , $result += $_
        for map{
                unpack 'N'
                , pack 'C4'
                , @ba[4*$_ .. 4*$_+3]
            } 0 .. ($#ba/4);
    return $result;
}

sub ba2bi2_clean {
    my @ba = reverse (@_, (0) x (4 - ( @_%4 || 4 ) ) );
    my $result = Math::BigInt->new(0);
    for (0 .. ($#ba/4)) {
        $result *= 4294967296;
        $result += unpack 'N', pack 'C4', @ba[4*$_ .. 4*$_+3]
    }
    return $result;
}

sub ba2bi2_nomap {
    my @ba = reverse (@_, (0) x (4 - ( @_%4 || 4 ) ) );
    my $result = Math::BigInt->new(0);
    $result *= 4294967296,
      $result += unpack 'N', pack 'C4', @ba[4*$_ .. 4*$_+3]
        for (0 .. ($#ba/4));
    return $result;
}

sub ba2bi2_unpack {
    my $result = Math::BigInt->new(0);
    $result *= 4294967296,
      $result += $_
        for unpack 'N*', reverse pack 'C'.(4*int(@_/4+1)), @_;
    return $result;
}

$|++;

$bigint = Math::BigInt->new('12345678' x 10);
@bytes  = bigint_to_bytearray($bigint);

my $comphash={
  'mult'   => 'bytearray_to_bigint(@bytes)',
  'shift'  => 'bytearray_to_bigint2(@bytes)',
  'ba2bi2' => 'ba2bi2(@bytes)',
  'nomap'  => 'ba2bi2_nomap(@bytes)',
  'clean'  => 'ba2bi2_clean(@bytes)',
  'unpack' => 'ba2bi2_unpack(@bytes)',
};

foreach my $comp (values %$comphash) {
    eval <<EVAL or die $@;
    print '$comp',"\n",$comp,"\n";
    1
EVAL
}

cmpthese(-10, $comphash);
__END__
[download]

ba2bi2(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
bytearray_to_bigint2(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
ba2bi2_nomap(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
ba2bi2_unpack(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
bytearray_to_bigint(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
ba2bi2_clean(@bytes)
+123456781234567812345678123456781234567812345678123456781234567812345
+67812345678
Benchmark: 
running
 ba2bi2, clean, mult, nomap, shift, unpack, each for at least 10 CPU s
+econds...

    ba2bi2: 13 wallclock secs (10.76 usr +  0.01 sys = 10.77 CPU) @ 69
+.21/s (n=745)
     clean: 12 wallclock secs (10.29 usr +  0.00 sys = 10.29 CPU) @ 68
+.55/s (n=705)
      mult: 12 wallclock secs (10.12 usr +  0.00 sys = 10.12 CPU) @  5
+.24/s (n=53)
     nomap: 12 wallclock secs (10.08 usr +  0.00 sys = 10.08 CPU) @ 69
+.48/s (n=700)
     shift: 12 wallclock secs (10.28 usr +  0.02 sys = 10.30 CPU) @  6
+.99/s (n=72)
    unpack: 12 wallclock secs (10.13 usr +  0.00 sys = 10.13 CPU) @ 71
+.05/s (n=720)

         Rate   mult  shift  clean ba2bi2  nomap unpack
mult   5.24/s     --   -25%   -92%   -92%   -92%   -93%
shift  6.99/s    33%     --   -90%   -90%   -90%   -90%
clean  68.5/s  1208%   881%     --    -1%    -1%    -4%
ba2bi2 69.2/s  1221%   890%     1%     --    -0%    -3%
nomap  69.5/s  1226%   894%     1%     0%     --    -2%
unpack 71.0/s  1256%   917%     4%     3%     2%     --
[download]

--- demerphq
my friends call me, usually because I'm late....

Comment on Re: Re: Converting an array of bytes into a BigInt - 1500% quicker. Select or Download Code

Replies are listed 'Best First'.
Re: Re: Re: Converting an array of bytes into a BigInt - 1500% quicker. by BrowserUk (Patriarch) on Jan 24, 2003 at 05:36 UTC
That's interesting. I did have a go at coming up with my own 'clean' version after posting. That's generally the way it works with me. I get something to work, post then try and clean it up and optimise it without breaking it. The biggest headache was working out where and how much padding to add. The rest came relatively easily, if convoluted. I guess I'm a messy thinker. Anyway, my best effort at a cleaner version is this, which is somewhat different again. TIMWTDI indeed. `sub ba2bi3 { my $ba = pack 'C', (@_, (0) x (4 - ( @_ % 4 \|\| 4 ) ) ); my $result = Math::BigInt->new(0); my $p = length($ba) - 4; do { $result <<= 32; #!4294967296; $result += unpack 'V', substr $ba, $p , 4; } while ($p-=4) >= 0; $result; } print ba2bi3( bigint_to_bytearray( Math::BigInt->new('1234567890' x 8) + ) );` [download] I had thought that be getting rid of the reverse, this would be be a benefit. It is on smaller numbers: 11: +1234567890 <<Length and value under test Benchmark: running best, clean, new, org , each for at least 10 CPU seconds best: 11 wallclock secs (10.59 usr + 0.00 sys = 10.59 CPU) @ 20 +8.58/s (n=2208) clean: 11 wallclock secs (10.55 usr + 0.00 sys = 10.55 CPU) @ 21 +3.94/s (n=2256) new: 11 wallclock secs (10.51 usr + 0.00 sys = 10.51 CPU) @ 60 +.26/s (n=633) org: 11 wallclock secs (10.35 usr + 0.00 sys = 10.35 CPU) @ 24 +.36/s (n=252) Rate org new best clean org 24.4/s -- -60% -88% -89% new 60.3/s 147% -- -71% -72% best 209/s 756% 246% -- -3% clean 214/s 778% 255% 3% -- The results are the same [download] However, when the numbers get larger, the benefit disappears, swamped by the gains of 4-bytes-at -a-time processing and the cost of BigInt math as here. 301: +1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 1234567890123456789012345678901234567890 12345678901234567890 Benchmark: running best, clean, new, org , each for at least 10 CPU seconds ... s/iter org new clean best org 5.82 -- -77% -94% -94% new 1.31 344% -- -73% -73% clean 0.352 1555% 273% -- -1% best 0.349 1569% 276% 1% -- The results are the same [download] I'm intrigued by the differences in the benchmarks on your machine and mine. Even when I run mine on an 80-byte number as you did, I still get gains of well over 1000%. I can only assume that your machine is using a compiled big int library, rather than the pure perl versionI am stuck with. Still, iif the performance difference is only a factor of 2, perl's doing pretty damn well I think. For comaprison I stuck your quickest version into my benchmark and ran it with the 300 digit number of my original benchmark and got these results. C:\test>229290 Name "main::ba" used only once: possible typo at C:\test\229290.pl lin +e 67. 301: +12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 12345678901234567890123456789012345678901234567890 Benchmark: running best, clean, demerphq, new, org , each for at least + 10 CPU seconds Rate org new clean demerphq best org 0.173/s -- -78% -94% -94% -94% new 0.770/s 345% -- -73% -73% -73% clean 2.83/s 1533% 267% -- -1% -1% demerphq 2.86/s 1553% 272% 1% -- -0% best 2.86/s 1553% 272% 1% 0% -- The results are the same [download] Well done for cracking the no-intermediate-string version (ba2bi2_unpack), I was certain that was possible, but didn't succeed in getting there. BTW. I realise I had snipped it off on my original post, but as you can see from the above, I do generally use the clock-tick seconds, rather than the iteration's method of benchmarking these days. Mostly because it gives me a reasonable indication of how long the run is likely to take. I always do nice long run (make myself a cup of coffee and drink it long) before I come to a conclusion. Now just think of the numbers you could get on a 64 bit machine :^) Examine what is said, not who speaks. The 7th Rule of perl club is -- pearl clubs are easily damaged. Use a diamond club instead.*	[reply] [d/l] [select]
Re: Re: Re: Re: Converting an array of bytes into a BigInt - 1500% quicker. by demerphq (Chancellor) on Jan 24, 2003 at 18:14 UTC
Well done for cracking the no-intermediate-string version (ba2bi2_unpack), I was certain that was possible, but didn't succeed in getting there. Why thank you, but I cant claim much credit as I just systematically tried simplified versions until one worked. pack / unpack still cause me brain aches. Now just think of the numbers you could get on a 64 bit machine :^) Until my pay check needs 64bits I dont even want to think about it... grin Regards, --- demerphq my friends call me, usually because I'm late....	[reply]