Re: Big GOTCHAs WITH forprime() (correction to the “new end-encoding scheme”)

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

On Wed, Jan 24, 2024 at 03:45:45AM -0800, Ilya Zakharevich wrote:
> 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”.

Thinking about this more, it seems to be better to encode
the-end-of-the-list as a sequence of bytes 0x0, 0xFF.  (In particular,
the code

    NEXT_PRIME_VIADIFF(p, d); /* starts at p = 3 */
    if (p > lim) break;

 — discussed elsewhere on this thread (in the context of
segfaults) — would be able to go up to the last prime in the list as
well, when lim is the this largest prime.)

> 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.

With the correction above, this can encode ANY prime difference > 0.
So one can use this to introduce 0-cost¹⁾ “hiccups” in looping over
primes.  (For example, putting such hiccups at powers of 2 gives a
chance to switch between different algorithms tuned for particular
magnitudes of primes.)

  ¹⁾ I mean that the cost is 0 INSIDE the hot loop.  

Hope this helps,
Ilya