Re: OT: Re: Sieve of Erastosthenes optimized to the max

Vir Campestris <vir.campestris@invalid.invalid> writes:

On 16/08/2024 18:35, Bonita Montero wrote:
>

But basically I don't think it is a good idea to skip numbers
exept multiples of two. [...]

>
I've been running some experiments.
>
Skipping evens only is nice and simple on computation;  that's
good.
>
Skipping something else requires table lookups.  [...]

It doesn't have to.  One point of the code I've been posting is
that table lookups, including mask productions, are eliminated;
everything gets optimized away so what's left is all compile-time
constants.

I'm happy with my algorithm:
- Work out a bitmask for some small primes, only as far as is
needed to get repeats (the repeat length is the product of the
primes)
- Work out bitmasks for the next half a dozen.  Each of those will
have a repeat the length of the prime.
- Combine those together into the output bitmap.  That requires
fewer operations than doing each one into the output bitmap
- Process the larger primes.  Do the output bitmap in blocks for
cache friendliness

My experience:

* Special casing primes between 7 and 29 helps (and because it's
  the first step the results can initialize the map);

* Special purpose code where primes are taken in pairs, for the
  set of primes more than 29 and less than 360, with each pair
  being folded into the initialized map, helps (incidentally,
  that is 31 pairs, or 62 primes total);

* The combination of those two steps gives a saving of about 35%;

* Doing striping (the term I use for working in cache-sized
  blocks) seems not to help much, so I don't use striping except
  incidentally in the prime-pairs step;

* Forcing the function for the main second-level loop to be
  inlined saves another 15% or so;

* I haven't tried to measure how the speed-up tricks scale with
  overall number of primes to calculate.  My guess is that they
  are close to linear but I don't have any actual measurements.