From: Trizen <trizen@protonmail.com>
To: "leonerd@leonerd.org.uk" <leonerd@leonerd.org.uk>
Subject: List::Util::product() with Math::BigInt objects
Hi Paul,
First, allow me to thank you for your work on List::Util and for maintaining this great package.
Recently I came across an interesting issue with the product() function when it's called with a list of ~10^5 numerical objects (such as Math::BigInt, Math::GMP, etc...). It ends up using very large amounts of memory (more than 4 GB).
Example:
use 5.010;
use strict;
use warnings;
use Math::BigInt try => 'GMP';
use List::Util qw(product);
my @list = map { Math::BigInt->new($_) } 1..1e5;
say product(@list);
I'm not sure what is really happening under the hood, but it feels like there is a memory leak somewhere.
One suggestion for solving this issue and also to improve the performance of `List::Util::product()` when called with numerical objects, would be to use binary splitting.
Example:
use 5.010;
use strict;
use warnings;
use Math::BigInt try => 'GMP';
sub Product {
my ($s, $n, $m) = @_;
$n > $m and return 1;
$n == $m and return $s->[$n];
my $k = ($n + $m) >> 1;
Product($s, $n, $k) * Product($s, $k + 1, $m);
}
my @list = map { Math::BigInt->new($_) } 1..1e5;
say Product(\@list, 0, $#list);
It's considerably faster than a sequential product. Recursion does however use quite a bit of memory, but this can be avoided by computing the product (using binary splitting) of partial chunks of the list, say 10^4 or 10^5 elements at a time, and combining the partial products at the end.
For inspiration I also recommend taking a look at the `ntheory::vecprod()` method, which does not have a memory issue, although it works only with integers.
Best regards,
Daniel
--
Paul Evans
RT for rt.cpan.org