Re: Big GOTCHAs WITH forprime()

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

On Fri, Jan 12, 2024 at 02:27:45PM -0800, Ilya Zakharevich wrote:
> ⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜⁜ 1/10000th of a workaround
> 
> At some moment, the code which allowed to support arbitrarily large
> primelimit (up to a word size) was removed from PARI.  (Compare with
>       https://pari.math.u-bordeaux.fr/archives/pari-dev-2401/msg00008.html
> .)  So now only the (unoptimized untunable buggy) code above can be
> used in the range about [436e6, 436e6²].
> 
> This removal has advantages: when I introduced the code in question,
> it could give a slowdown of 3–5% to forprime() — due to one extra
> (very rarely taken) conditional branch inside a hot loop.
> 
> However:
> 
>   • With the progress in branch prediction in processors during the
>     last 20 years, I would not be surprised that this slowdown is
>     removed COMPLETELY nowadays.

Oups!  What I have been thinking these 20–25 years ago?!  However small
the slowdown may be, it can have be REMOVED COMPLETELY!

Just rework the current scheme of the byte
   pointer_to_primediff[0] == 0
denoting “the end of the prime difference table” to
   pointer_to_primediff[0] == pointer_to_primediff[1] == 0
denoting “the end of this table”.

Then one can encode “a prime difference of 256*n+m > 255 as a sequence of
the form
   0 n m
so one can process it in the same (rare) branch used to processing the
end of the list.

Hope this helps,
Ilya

P.S.  At the very least, I expect that this may be useful as a way to
      speed up primepi() — if needed.