Perl Projects - Benchmark Timeline of BigInt/BigFloat

Table of Contents

BigInt benchmarks

• Introduction
• Hexadecimal input
• Binary and Hexadecimal string output
• Sign Manipulation
• Bit-Fiddling
• Prime Sieve
• new() from a decimal string
• Power of 2
• Various Powers
• Division by a small number
• Division by a longer number
• Multiplication (factorial)
• Square-Root of a small value
• Implicit numify
• Boolean context
• Startup time

BigFloat benchmarks

• new() from decimal strings
• new() from long string
• Square-Root (non-overloaded math) with int result
• Square-Root (non-overloaded math) with float result
• Square-Root (overloaded math)
• Addition of shorter Floats
• Addition of longer Floats
• Multiplication of longer Floats
• Division of longer Floats
• Comparisation with zero
• Logarithm with integer result
• Logarithm with float result
• Startup time

Back to my BigInt pages.

Introduction

The following graphs were made on a 2Ghz AMD Athlon XP2400+, running under SuSE Linux 8.2, kernel 2.4.20, Perl v.5.8.2 compiled with gcc version 3.3 20030226.

The missing values for some specific versions are due to a number of reasons, including the method was not available, computed wrong results, spilled lots of debug output or died with an error.

About the BigInt versions

Here is a short table comparing the different Perl released and the BigInt version included in the:

Hexadecimal input

my $tries = (shift || 1024) * 0.15;     # 150 is about right
my $a = '0x';
my @hex_digits = ( '0' .. '9', 'a' .. 'f');
for ( 0 .. 256 )
  {
  $a .= $hex_digits[ rand(16) ];
  }

for (my $i = Math::BigInt->new(2); $i < $tries; $i++)
  {
  my $b = Math::BigInt->new( $a );
  }

The peak in v1.67 is due to a typo in the new %CAN code that caused the slower emulation code to be always used.

Binary and Hexadecimal string output

my $tries = (shift || 1024) / 10;               # 100 is about right
my $a = Math::BigInt->new(2) ** 256;

for (my $i = Math::BigInt->new(2); $i < $tries; $i++)
  {
  my $b = Math::BigInt->new( $a->as_hex() )->as_bin();
  }

The slight peak in v1.67 is due to a typo in the new %CAN code that caused the slower emulation code to be always used.

Sign manipulation

my $bits = (shift || 1024) * 0.4;               # 400 is about right

# generate a short number
my $a = Math::BigInt->new('1234567890');

# no BigInt, because binc() would skew the time
for (my $i = 0; $i < $bits * 100; $i ++)
  {
  $a = abs( -$a );      # when using a very long number newer versions would
                        # be slower, because "-$a" makes a copy. $a->bneg()
                        # does not, but it doesn't work in v0.01...
  $a->bneg();
  }

Bit-Fiddling

my $bits = (shift || 1024) * 1.8;       # 1800 is about right
my $a = Math::BigInt->new(2);

for (my $i = Math::BigInt->new(2); $i < $bits; $i++)
  {
  $a = ~$a;                     # bnot
  $a <<= 3;                     # blsft
  $a ||= "0x123456789";         # bior
  }

Prime sieve

This benchmarks a complicated version of the prime number sieve. It is not optimized since we want to benchmark as many features as possible.

You can see that the streamlining in the latest versions pays of for general code that uses overloaded math with a lot of scalar constants.

new() from a decimal string

my $tries = (shift || 1024) * 40;               # 40000 is about right
my $a;

# dont use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 2; $i < $tries; $i++)
  {
  my $b = Math::BigInt->new($i); $b = "$i"; $b =~ s/\+//;
  $a = Math::BigInt->new("$b$b$b$b");
  }

Power of 2

my $bits = (shift || 1024) * 345;	# 234500 is about right

my $a = Math::BigInt->new(2) ** Math::BigInt->new($bits);

Various Powers

my $bits = (shift || 1024) * 0.6;               # 600 is about right
my ($a,$b);

for (my $i = Math::BigInt->new(2); $i < $bits; $i++)
  {
  for ($j = Math::BigInt->new(2); $j < Math::BigInt->new(5); $j++)
    {
    $a = $j ** $i;
    }
  }

Division by a small number

my $bits = (shift || 1024) * 0.4;               # 400 is about right

my $a = Math::BigInt->new('1234567890' x $bits);
my $b = Math::BigInt->new('1');

while ($a > 1)
  {
  $a = $a / $b; $b += 3;
  }

Division by a longer number

my $bits = (shift || 1024) * 0.2;               # 200 is about right

my $a = Math::BigInt->new('123456789012345678901234567890' x $bits);
my $b = Math::BigInt->new('1234567890');

while ($a > 1)
  {
  $a = $a / $b; $b += 3;
  }

Multiplication (factorial)

my $tries = (shift || 1024) * 3;        # 3000 is about right

# factorial (non-native). the mul() will dominate the time for long numbers

my $a = Math::BigInt->new('1');
my $b = Math::BigInt->new('1');

# no BigInt for $i to not skew the test
for ($i = 0; $i < $tries; $i++)
  {
  $b = $b * $a; $a ++;
  }

Square-Roots with small numbers

Before v1.27, the code was not able to take the square root of a BigInt, e.g. bsqrt() did not exist.

Because it is hard to see the data for the later versions, here is a graph excluding the slow BigInt versions:

Square-Roots with big numbers

my $tries = (shift || 1024) / 3;
my $a = Math::BigInt->new('123456789' x 12);
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = $a->copy()->bsqrt();
  }

Implicit numify

my $tries = (shift || 1024) * 700;

my $a = Math::BigInt->new(2);
my @x = (1,2,3,4);

my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = $x[$a];          # implicit convert to scalar
  }

Boolean context

First with a small number:

my $tries = (shift || 1024) * 700;

my $a = Math::BigInt->new(2);
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = 1 if $a;		# boolean context
  }

And now with a huge number:

my $tries = (shift || 1024) * 1000;

my $a = Math::BigInt->new('1234567890' x 200);
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = 1 if $a;		# boolean context
  }

I excluded v1.11 through v1.15 because the are so slow (over 3 seconds) that the other bars would be very hard to see.

Startup time

require Math::BigInt;

if ($ARGV[1])
  {
  Math::BigInt->import( lib => $ARGV[1] );
  }
else
  {
  Math::BigInt->import();
  }

my $i = Math::BigInt->new(3);

print "\$i = $i ";

BigFloat benchmarks

In the following graphs the versions v1.11 through v1.14 are generally missing because the code of the rewritten BigFloat was not complete enough nor working properly to make meaningfull benchmarks.
In addition, some of the other versions might be missing due to incomplete or buggy implementations.

While the new BigInt versions are generally faster than the original, BigFloat is usually slower. Further work on streamlining BigFloat's math operations needs to be done.

new() from decimal strings

my $tries = (shift || 1024) * 40;               # 40000 is about right
my $a;

# dont use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 2; $i < $tries; $i++)
  {
  my $b = Math::BigFloat->new($i); $b = "$i"; $b =~ s/\+//;
  $a = Math::BigFloat->new("$b$b$b$b");
  }

We see that the rewritten versions are much slower than the original. The reason is that the original did a very casual checking of the input and then simply blessed the string into a BigFloat. The new version checks it very carefully, and separates it into two parts, the mantissa and the exponent. These parts are then created as BigInts.

new() from long string

my $tries = (shift || 1024) * 4;                # 4000 is about right
my $a;

my $b = '1234567890' x 10 . 'e-13';

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $a = Math::BigFloat->new($b);
  }

Square-Root (non-overloaded math) with integer result

Non-overloaded square-root ala Math::BigFloat->new(144)->sqrt() was always supported, but the early rewritten versions either died (pre v1.22), calculated wrong results (pre v1.24) or had sleep() and/or spilled lots of debug output. The first usable version after v0.01 was v1.37.

my $tries = (shift || 1024) / 4;	# 250 are enough
my $a = Math::BigFloat->new(144*144);
my $z = Math::BigFloat->new(0);
my $b;

# dont use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 2; $i < $tries; $i++)
  {
  # original BigFloat had no copy() so trick it into making one via overload
  $b = $a - $z; $b = $b->fsqrt();
  }

Unfortunately, v1.37 to v1.47 were so slow that the bars for the newer versions are barely visible. For this reason I made another graph, excluding v1.37 through v1.47:

Square-Root (non-overloaded math) with float result

Computing a perfect square (e.g. where the result is an integer) is easier than computing a result to roughly 40 digits accuracy. So the sqrt() test was also done with a non-perfect result. Versions are excluded on the same grounds as above.

my $tries = (shift || 1024) / 4;        # 250 are enough
my $a = Math::BigFloat->new(144*144 + 1);
my $z = Math::BigFloat->new(0);
my $b;

# dont use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 2; $i < $tries; $i++)
  {
  # original BigFloat had no copy() so trick it into making one via overload
  $b = $a - $z; $b = $b->fsqrt();
  }

Square-Root (overloaded math)

Overloaded square-root ala sqrt(Math::BigFloat->new(144)) was actually not possible until v1.50 - not even with v0.01.

my $tries = (shift || 1024) * 40;               # 40000 is about right
my $a = Math::BigFloat->new(144*144);
my $b;

# dont use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 2; $i < $tries; $i++)
  {
  $b = sqrt($a);
  }

Addition of shorter Floats

Addition of two "small" float values (their mantissas are very short), and incrementing a short float (which is a special form of addition).

my $tries = (shift || 1024) * 4;
my $a = Math::BigFloat->new("5.2");
my $b = Math::BigFloat->new("1.23");
my $x;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $x = $a + $b;
  }

my $tries = (shift || 1024) * 4;
my $a = Math::BigFloat->new("5.2");

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $a++;
  }

Addition of longer Floats

Addition of two longer floats with non-zero exponents.

my $tries = (shift || 1024);
my $a = Math::BigFloat->new('1234567890' x 10 . '.1234567890');
my $x = Math::BigFloat->new('1234567890' x 8 . "e-5");
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = $a + $x;
  }

Multiplication of longer Floats

Multiplication of two longer floats with non-zero exponents.

Both v1.27 and v1.30 fail the benchmark with the following error message:

Can't call method "is_zero" on an undefined value at BigFloat.pm line 651.

The other versions pass and correctly calculate the result, altough some output diferrences ("12e-1" vs "1.2") can be observed.

my $tries = (shift || 1024) * 2;
my $a = Math::BigFloat->new('1234567890' x 10 . '.1234567890');
my $x = Math::BigFloat->new('1234567890' x 8 . "e-5");
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = $a * $x;
  }

Division of longer Floats

Division of two longer floats with non-zero exponents, resulting on a large number with small mantissa and big positive exponent.

Version v1.31 through v1.36 fail the benchmark by computing wrong results.

my $tries = (shift || 1024) * 2;
my $a = Math::BigFloat->new('1234567890' x 10 . '.1234567890');
my $x = Math::BigFloat->new('1234567890' x 8 . "e-5");
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = $a / $x;
  }

Comparisation of a long and a small float with zero

my $tries = (shift || 1024) * 8;
my $a = Math::BigFloat->new('5.2');
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = 1 if $a != 0;
  }

my $tries = (shift || 1024) * 2;
my $a = Math::BigFloat->new('1234567890' x 10 . '.1234567890');
my $b;

# don't use BigInts in the for() loop, because that skews the test (binc()
# got a lot faster in subsequent versions)
for (my $i = 1; $i < $tries; $i++)
  {
  $b = 1 if $a != 0;
  }

Power of 2

my $bits = (shift || 1024) * 345;	# 234500 is about right

my $a = Math::BigFloat->new(2) ** Math::BigFloat->new($bits);

Apart from a small constant overhead the time for BigFloat should be the same as for BigInt, comparing this graph with the one from BigInt show that this is the case.

Power of two floats

my $x = Math::BigFloat->new('1.234');
my $y = Math::BigFloat->new('0.23456');
my $a;

for (my $i = 0; $i < $tries; $i++)
  {
  $a = $x ** $y;
  }

Earlier versions that v1.57 were not able to calculate the proper result at all.

Logarithm with integer result

my $x = Math::BigFloat->new('123') ** 123;
my $y = Math::BigFloat->new('123');

my $a = $x->copy()->blog($y);		# result is exactly 123

Earlier versions that v1.64 were not able to calculate the proper result at all. v1.68 is so fast that you barely see the bar :) Note that the graph here is for calculating the result only once!

Logarithm with float result

my $x = Math::BigFloat->new('13') ** 13 + 1234;
my $y = Math::BigFloat->new('13');
my $a;

for (my $i = 0; $i < $tries; $i++)
  {
  $a = $x->copy()->blog($y);
  }

Startup time

BEGIN
  {
  $| = 1;
  require Math::BigInt;
  my $x = $Math::BigInt::VERSION;

  # earlier versions are not working
  exit (-1) if $x < 1.15 && $x != 0.01;
  }

require Math::BigFloat;

if ($ARGV[1])
  {
  Math::BigFloat->import( lib => $ARGV[1] );
  }
else
  {
  Math::BigFloat->import();
  }

$b = Math::BigFloat->new(1);

Back to my BigInt pages.

Tels Created: 2003-12-22 Last modified: 2003-12-25