Bug #43924 for Math-BigInt: Huge slowdown in blog(x) when x begins with 1

Sat Mar 07 06:08:02 2009 emazep [...] gmail.com - Ticket created

Subject:

Huge slowdown in blog(x) when x begins with 1

It seems that there is a huge slowdown in blog(x) whenever x is a number beginning with 1. Consider the following script: --- use strict; use warnings; use Benchmark qw(cmpthese); use Math::BigFloat; # $x is a big number beginning with 1 our $x = Math::BigFloat->new( '1234567890' x 20 ); # $x2 = $x * 2 ($x2 begins with 2) our $x2 = $x->copy->bmul(2); cmpthese( -10, { log_2x => sub { $x2->copy->blog }, log_x => sub { $x->copy->blog } }); --- It prints out: Rate log_x log_2x log_x 1.14/s -- -95% log_2x 24.4/s 2038% -- which shows that (in this case) calculating blog(x) takes more than *20 times* longer than calculating blog(2*x) (this ratio tends to diverge when the size of x increases). Whatever the reason, this can easily be avoided at least by naively implementing blog(x) by blog(2*x)-blog(2) when x is a number beginning with 1 (multiplying by 2 a number beginning with 1 always gives a number beginning with a digit != 1). Thank you for your great work, Emanuele Zeppieri

Sat Mar 07 06:11:27 2009 emazep [...] gmail.com - Correspondence added

Subject:

perl-V.txt

Summary of my perl5 (revision 5 version 10 subversion 0 patch 34065) configuration: Platform: osname=cygwin, osvers=1.5.25(0.15642), archname=cygwin-thread-multi-64int uname='cygwin_nt-5.1 reini 1.5.25(0.15642) 2008-06-12 19:34 i686 cygwin ' config_args='-de -Dmksymlinks -Dusethreads -Dmad=y -Dusedevel' hint=recommended, useposix=true, d_sigaction=define useithreads=define, usemultiplicity=define useperlio=define, d_sfio=undef, uselargefiles=define, usesocks=undef use64bitint=define, use64bitall=undef, uselongdouble=undef usemymalloc=y, bincompat5005=undef Compiler: cc='gcc', ccflags ='-DPERL_USE_SAFE_PUTENV -U__STRICT_ANSI__ -fno-strict-aliasing -pipe -I/usr/local/include', optimize='-O3', cppflags='-DPERL_USE_SAFE_PUTENV -U__STRICT_ANSI__ -fno-strict-aliasing -pipe -I/usr/local/include' ccversion='', gccversion='3.4.4 (cygming special, gdc 0.12, using dmd 0.125)', gccosandvers='' intsize=4, longsize=4, ptrsize=4, doublesize=8, byteorder=12345678 d_longlong=define, longlongsize=8, d_longdbl=define, longdblsize=12 ivtype='long long', ivsize=8, nvtype='double', nvsize=8, Off_t='off_t', lseeksize=8 alignbytes=8, prototype=define Linker and Libraries: ld='g++', ldflags =' -Wl,--enable-auto-import -Wl,--export-all-symbols -Wl,--stack,8388608 -Wl,--enable-auto-image-base -L/usr/local/lib' libpth=/usr/local/lib /usr/lib /lib libs=-lgdbm -ldb -ldl -lcrypt -lgdbm_compat perllibs=-ldl -lcrypt libc=/usr/lib/libc.a, so=dll, useshrplib=true, libperl=libperl.a gnulibc_version='' Dynamic Linking: dlsrc=dl_dlopen.xs, dlext=dll, d_dlsymun=undef, ccdlflags=' ' cccdlflags=' ', lddlflags=' --shared -Wl,--enable-auto-import -Wl,--export-all-symbols -Wl,--stack,8388608 -Wl,--enable-auto-image-base -L/usr/local/lib' Characteristics of this binary (from libperl): Compile-time options: MULTIPLICITY MYMALLOC PERL_DONT_CREATE_GVSV PERL_IMPLICIT_CONTEXT PERL_MAD PERL_MALLOC_WRAP PERL_USE_SAFE_PUTENV USE_64_BIT_INT USE_ITHREADS USE_LARGE_FILES USE_PERLIO USE_REENTRANT_API Locally applied patches: MAINT34065 CYG11 no-bs CYG12 no archlib in otherlibdirs CYG14 Dynaloader CYG15 static-Win32CORE Bug#55162 File::Spec::case_tolerant performance Built under cygwin Compiled at Jun 30 2008 16:05:15 %ENV: CYGWIN="" @INC: /usr/lib/perl5/5.10/i686-cygwin /usr/lib/perl5/5.10 /usr/lib/perl5/site_perl/5.10/i686-cygwin /usr/lib/perl5/site_perl/5.10 /usr/lib/perl5/vendor_perl/5.10/i686-cygwin /usr/lib/perl5/vendor_perl/5.10 /usr/lib/perl5/vendor_perl/5.10 /usr/lib/perl5/site_perl/5.8 /usr/lib/perl5/vendor_perl/5.8 .

Sat Mar 07 08:53:26 2009 nospam-abuse [...] bloodgate.com - Correspondence added

Subject:	Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date:	Sat, 7 Mar 2009 14:52:43 +0100
To:	bug-Math-BigInt [...] rt.cpan.org
From:	Tels <nospam-abuse [...] bloodgate.com>

On Saturday 07 March 2009 12:08:03 Emanuele Zeppieri via RT wrote: Show quoted text

> Sat Mar 07 06:08:02 2009: Request 43924 was acted upon. > Transaction: Ticket created by emazep > Queue: Math-BigInt > Subject: Huge slowdown in blog(x) when x begins with 1 > Broken in: 1.89 > Severity: Normal > Owner: Nobody > Requestors: emazep@gmail.com > Status: new > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > > It seems that there is a huge slowdown in blog(x) whenever x is a > number beginning with 1. > > Consider the following script: > > --- > > use strict; > use warnings; > > use Benchmark qw(cmpthese); > use Math::BigFloat; > > # $x is a big number beginning with 1 > our $x = Math::BigFloat->new( '1234567890' x 20 ); > # $x2 = $x * 2 ($x2 begins with 2) > our $x2 = $x->copy->bmul(2); > > cmpthese( -10, { > log_2x => sub { $x2->copy->blog }, > log_x => sub { $x->copy->blog } > }); > > --- > > It prints out: > > Rate log_x log_2x > log_x 1.14/s -- -95% > log_2x 24.4/s 2038% -- > > which shows that (in this case) calculating blog(x) takes more than > *20 times* longer than calculating blog(2*x) (this ratio tends to > diverge when the size of x increases). > > Whatever the reason, this can easily be avoided at least by naively > implementing blog(x) by blog(2*x)-blog(2) when x is a number > beginning with 1 (multiplying by 2 a number beginning with 1 always > gives a number beginning with a digit != 1).

I haven't looked (and I currently have almost zero time for Perl, sorry :( but it might be a simple case of the code accidentily using BigIntegers internally when the number begins with 1, by not converting some small number to a scalar or so. Thank you for your report! Tels -- Signed on Sat Mar 7 14:51:51 2009 with key 0x93B84C15. Get one of my photo posters: http://bloodgate.com/posters PGP key on http://bloodgate.com/tels.asc or per email. "Now, admittedly, it's critical software. This is the 'let's go kill people' software." -- Mark A. Welsh III

Download signature.asc
application/pgp-signature 481b

Message body not shown because it is not plain text.

Sat Mar 07 08:53:27 2009 The RT System itself - Status changed from 'new' to 'open'

Mon Jul 09 13:41:41 2012 BBYRD [...] cpan.org - Correspondence added

Confirmed that this is still an issue: use strict; use warnings; use Benchmark qw(cmpthese); use Math::BigFloat; our $x = Math::BigFloat->new( '1234567890' x 20 ); our $x2 = Math::BigFloat->new( '2234567890' x 20 ); cmpthese( -10, { log_2x => sub { $x2->copy->blog }, log_x => sub { $x->copy->blog } }); Rate log_x log_2x log_x 1.18/s -- -98% log_2x 47.2/s 3914% --

Tue Oct 22 15:19:42 2013 DANAJ [...] cpan.org - Correspondence added

This happens because _log_10 first moves the decimal place over (so XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right before the "if $twos != 0" loop. If X >= 2, we divide by two *and round to $scale+4*. So in the case of '2234567890' x 20, we have divided by two with rounding, so we send to _log: '1.11728394511172839451117283945111728394511172839' In the case of '1234567890' x 20, we send: '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' The former is much faster. Adding the line: $x->bround($scale+4) on line ~1480 of BigFloat.pm, right after the while statements and before the 'if ($twos != 0)' will speed up the first case in the benchmark by about 20x. With that change, the test suite passes. I'm not sure if it is the *right* fix.

Wed Oct 23 13:56:26 2013 nospam-abuse [...] bloodgate.com - Correspondence added

Subject:	Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date:	Wed, 23 Oct 2013 13:56:02 -0400
To:	bug-Math-BigInt [...] rt.cpan.org
From:	"Tels" <nospam-abuse [...] bloodgate.com>

On Tue, October 22, 2013 3:19 pm, Dana Jacobsen via RT wrote: Show quoted text

> Queue: Math-BigInt > Ticket <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > This happens because _log_10 first moves the decimal place over (so > XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right > before the "if $twos != 0" loop. If X >= 2, we divide by two *and round > to $scale+4*. > > So in the case of '2234567890' x 20, we have divided by two with rounding, > so we send to _log: > '1.11728394511172839451117283945111728394511172839' > > In the case of '1234567890' x 20, we send: > '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' > > The former is much faster. Adding the line: > > $x->bround($scale+4) > > on line ~1480 of BigFloat.pm, right after the while statements and before > the 'if ($twos != 0)' will speed up the first case in the benchmark by > about 20x. > > With that change, the test suite passes. I'm not sure if it is the > *right* fix.

IIRC the routine is asked to return a precision of scale, so it keeps internally $scale + 4 (to have enough digits to avoid rounding). So rounding the input in both cases is the "right" thing todo, e.g. at least it will have the same possible output inaccuraries in both cases. Not rounding in one path was probably an oversight on my part, and the testsuite wouldn't catch it if the final result is rounded to $scale before output, unless the intermidiate rounding produces errors due to accumulating them. Hope this helps, tels -- http://bloodgate.com/galleries/

Wed Jun 04 04:23:31 2014 emazep [...] gmail.com - Correspondence added

Subject:	Re: [rt.cpan.org #43924] Huge slowdown in blog(x) when x begins with 1
Date:	Wed, 04 Jun 2014 10:23:19 +0200
To:	bug-Math-BigInt [...] rt.cpan.org
From:	Emanuele Zeppieri <emazep [...] gmail.com>

To the maintainer: can we apply this fix please? Thanks! -Emanuele On 2013-10-22 21:19, Dana Jacobsen via RT wrote: Show quoted text

> <URL: https://rt.cpan.org/Ticket/Display.html?id=43924 > > > This happens because _log_10 first moves the decimal place over (so XYYYYYY.ZZZ becomes X.YYYYYYZZZ) then we do a comparison of X >= 2 right before the "if $twos != 0" loop. If X >= 2, we divide by two *and round to $scale+4*. > > So in the case of '2234567890' x 20, we have divided by two with rounding, so we send to _log: > '1.11728394511172839451117283945111728394511172839' > > In the case of '1234567890' x 20, we send: > '1.234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789' > > The former is much faster. Adding the line: > > $x->bround($scale+4) > > on line ~1480 of BigFloat.pm, right after the while statements and before the 'if ($twos != 0)' will speed up the first case in the benchmark by about 20x. > > With that change, the test suite passes. I'm not sure if it is the *right* fix. >

Fri Apr 24 09:49:52 2015 peter.john.acklam [...] gmail.com - Correspondence added

Patch submitted: https://rt.perl.org/Ticket/Display.html?id=124382

Tue Sep 15 07:17:47 2015 peter.john.acklam [...] gmail.com - Correspondence added

Fixed in Math-BigInt-1.999701.

Tue Sep 15 07:17:49 2015 peter.john.acklam [...] gmail.com - Status changed from 'open' to 'resolved'

Tue Sep 15 07:17:55 2015 peter.john.acklam [...] gmail.com - Fixed in 1.999701 added