primelimit and forprime()

[Ilya Zakharevich <nospam-abuse@ilyaz.org>]

On Sun, Jan 07, 2024 at 09:14:25AM -0800, Ilya Zakharevich wrote:
> P.S.  High primelimit speeds up sieving about 1.5 orders of magnitude
>       (up to primelimit²).

I completely lost!  With my old implementation of forprimes() the
semantic of the speed was quite simple.  I THOUGHT that I understand
the semantic of the speed of the new implementation as this:

  • up to primelimit² what is used is on-the-fly sieving.
  • after this, nextprime() is used (which is way slower — but the
    speed does not depend MUCH on the argument — up to 1 word overflow).

And this is what works with the default primelimit=500000:

  (09:26) gp > my(s=24*10^10); forprime(p=s,s+10^8,)
  time = 453 ms.
  (09:26) gp > my(s=26*10^10); forprime(p=s,s+10^8,)
  time = 16,521 ms.
  (09:31) gp > my(s=15*10^16); forprime(p=s,s+10^8,)
  time = 16,818 ms.
  (09:26) gp > my(s=17*10^18); forprime(p=s,s+10^8,)
  time = 18,189 ms.
  (10:03) gp > my(s=19*10^18); forprime(p=s,s+10^8,)
  time = 1min, 41,026 ms.
  
About 10 years ago, I tested this with primelimit about 10^7 as well.
However, with the limit of 4*10^9 (about 2^32 — the limit of the old
implementation on 32-bit¹⁾ machines) what I observe is very different,
and very non-monotonic:

  (09:23) gp > my(s=15*10^10); forprime(p=s,s+10^8,)
  time = 436 ms.
  (09:23) gp > my(s=15*10^12); forprime(p=s,s+10^8,)
  time = 1,030 ms.
  (09:23) gp > my(s=15*10^14); forprime(p=s,s+10^8,)
  time = 5,352 ms.
  (09:30) gp > my(s=15*10^16); forprime(p=s,s+10^8,)
  time = 43,415 ms.
  (09:13) gp > my(s=15*10^18); forprime(p=s,s+10^8,)
  time = 18,096 ms.
  (09:22) gp > my(s=17*10^18); forprime(p=s,s+10^8,)
  time = 18,238 ms.
  (10:02) gp > my(s=19*10^18); forprime(p=s,s+10^8,)
  time = 1min, 41,120 ms.

    ¹⁾ My computer is 64-bit.

Why the slow-down at about 10^16?  Why the speed returning back to the
speed of default primelimit around 10^19?  (And not after primelimit²?)

Thanks,
Ilya

  P.S.  This is somewhat similar to what would happen if
          • the advantage of sieving-on-the-fly gradually disappears,
  	    and it has no advantage over nextprime() at some moment;
	  • gp/PARI knows about this, and switches to the nextprime()
  	    after a certain threshold;
  	  • However, the threshold is hardwired into gp/PARI, and its
  	    value is way off for my computer.
	    
        Is it so?