possible speedup for mpz_nextprime_small

[Seth Troisi]

I looked at mpz_probab_prime_p today and for numbers <= 1M it checks all
odds up to 1000 using very similiar code as nextprime_small.
So now I'm thinking maybe we should add a medium static list and share it
with mpz_probab_prime_p.

afterwards mpz_nextprime_small could be simplified to

static unsigned
mpz_nextprime_small (unsigned t)
{
  /* Start from next candidate (2 or odd) */
  t = (t + 1) | (t > 1);
  for (; ; t += 2)
    if (mpz_probab_prime_p_internal_small_case(t))
      return t;
}

I'm not sure how to share a list between two source files but if you point
me at an example I'm happy to try something.
I also adding probab_prime_p to speed see speed_probab_prime.patch note I
didn't get the time to look other the patch so it might be extra rought.


On Thu, Mar 26, 2020 at 7:20 AM Marco Bodrato <bodrato at mail.dm.unipi.it>
wrote:

> Ciao,
>
> Il 2020-03-26 01:06 Seth Troisi ha scritto:
> > Marco was interested in what using dynamically allocating primes would
> > look like.
> > I've attached a couple of screenshots.
>
> I'd like to understand the reason why the line "dynamic" is 5-10% lower
> than the other lines in the range above 27...
>
There's a certain amount of noise in the benchmark (remember that it
chooses a random start between 2^(n-1) to 2^n which is a big range)
Sometimes I forget to pause music in chrome which is another source of
variation.
I reran (with -p100000000) being careful that nothing was running in the
background and with 2 runs to show a sense of variation.


> > I think a good balance would be to add 70 primes and increase
> > SMALL_LIMIT to 1,000,000
>
> Adding back the primes we just removed, because they are useful again!
>
> > We would need a new constant to differentiate
> > if (nbits / 2 < NUMBER_OF_PRIMES)
> >   and
> > ASSERT (i < NUMBER_OF_PRIMES);
>
> Yes. The first is a threshold to switch from a method to another. Should
> it be tuned on different CPUs?
>
I've never done this so I'm not sure how much work it is. If you think it's
a good idea I'm happy to try it out.

NUMBER_OF_PRIMES is the hard limit for that threshold.
>
> Ĝis,
> m
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 12-41-14.png
Type: image/png
Size: 45206 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/206d1b94/attachment-0004.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: speed_probab_prime.patch
Type: text/x-patch
Size: 4423 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/206d1b94/attachment-0001.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 13-29-36.png
Type: image/png
Size: 31353 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/206d1b94/attachment-0005.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 13-31-16.png
Type: image/png
Size: 31030 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/206d1b94/attachment-0006.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Screenshot from 2020-03-27 13-32-49.png
Type: image/png
Size: 31364 bytes
Desc: not available
URL: <https://gmplib.org/list-archives/gmp-devel/attachments/20200327/206d1b94/attachment-0007.png>