Re: Pari Slowdown?

["Jason Moxham" <jason@njkfrudils.plus.com>]

----- Original Message ----- 
From: "Bill Allombert" <Bill.Allombert@math.u-bordeaux1.fr>
To: <pari-dev@list.cr.yp.to>
Sent: Wednesday, July 08, 2009 11:05 PM
Subject: Re: Pari Slowdown?


> On Sun, Jun 28, 2009 at 09:16:30PM +0200, Bill Allombert wrote:
> > On Sun, Jun 28, 2009 at 01:02:57AM +0100, Jason Moxham wrote:
> > > Hi
> > >
> > > Doing some very rough benchmarks of Pari on 64bit linux with GMP
> > > pari-2.4.2-alpha
> > > ? gettime() ; isprime(2^127-1,2);gettime()
> > > %3 = 4
> > > ? gettime() ; isprime(2^521-1,2);gettime()
> > > %4 = 332
> > > ? gettime() ; isprime(2^607-1,2);gettime()
> > > %5 = 857
> > > ? gettime() ; isprime(2^1279-1,2);gettime()
> > > %6 = 9845
> > >
> > > pari-svn
> > > ? gettime() ; isprime(2^127-1,2) ; gettime()
> > > %1 = 8
> > > ? gettime() ; isprime(2^521-1,2) ; gettime()
> > > %2 = 420
> > > ? gettime() ; isprime(2^607-1,2) ; gettime()
> > > %3 = 1108
> > > ? gettime() ; isprime(2^1279-1,2) ; gettime()
> > > %4 = 12885
> > >
> > >
> > > This is all on the same machine with gcc-4.2.2,MPIR-1.2.1, nehalem 
> > > 2.6Ghz
> > >
> > > I tried make tune , but it didn't make any significant difference.
> >
> > Thanks, this is a slowdown caused by this change:
> >
> >   BA 35- direct implementation of ZX_mul, ZX_sqr using Kronecker's trick 
> > + mul
> >
> > We really need to tune ZX_mul and ZX_sqr.
>
> However, there might be a problem with GMP itself (or the GMP kernel):
>
> for(i=1,20,a=random(2^(100000+10000*i));gettime();for(j=1,1000,a^2);print(i,":",gettime()))
> 1:745
> 2:849
> 3:925
> 4:1028
> 5:1156
> 6:1248
> 7:1372
> 8:1485
> 9:1569
> 10:1740
> 11:1825
> 12:1945
> 13:1408
> 14:1409
> 15:1624
> 16:1625
> 17:1629
> 18:1624
> 19:1969
> 20:1965
>
> entry 12 is much slower than entry 13.

Depending on cpu and limb size your at about the FFT range , which is well 
known for timings that don't smoothly increase.


> (This interfers with my attempts at tuning ZX_sqr).
>
> Cheers,
> Bill.