Re: How to efficiently count Proth primes with GP parfor?

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

> ? isProth(p)=my(v=valuation(p-1,2));p>>v<2^v;
> ? export(isProth)
> ?
> 
> I tested the first 3,000 Proth primes:
> 
> ? c=0;forprime(p=3,323092481,if(isProth(p),c+=1));c
> 3000
> ? ##
>   ***   last result: cpu time 5,545 ms, real time 5,545 ms.
> ? c=0;parforprime(p=3,323092481,isProth(p),C,if(C,c+=1));c
> 3000
> ? ##
>   ***   last result: cpu time 29,142 ms, real time 18,457 ms.
> ?
> 
> 1) Why is sequential computation more than 5× faster than parallel?

> 2) Why does gp run with only 336% CPU and not wih more than 1500% or 3100% ?

The function isProth is too fast compared to the overhead of parallelism.
As you see, PARI only manage to schedule 3.36 job on average before the first
one complete, so most of the time is spent scheduling jobs.
You need to do work by batch.

isProth(p)=my(v=valuation(p-1,2));p>>v<2^v;
export(isProth);
{
  my(nbt=default(nbthreads));
  my(c=0,B=323092481\nbt);
  parforstep(i=1,323092481,B,
    my(cc=0);
    forprime(p=i,min(i+B-1,323092481),cc+=isProth(p));cc
  ,C,c+=C);c
}
%3 = 3000
? ##
  ***   last result: cpu time 17,843 ms, real time 1,070 ms.

(with 20 cores).

The best value of nbt will depend on your system. 

Cheers,
Bill.