Sujet : Re: Sieve of Erastosthenes optimized to the max
De : vir.campestris (at) *nospam* invalid.invalid (Vir Campestris)
Groupes : comp.lang.c++Date : 18. Jun 2024, 21:56:04
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <v4sool$1grge$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
User-Agent : Mozilla Thunderbird
OK, I'm getting some weird results.
Firstly, whatever I do my original algorithm storing odds only is faster than using mod30. Quite a bit faster. I think this is because mod30 requires it to access each byte in the map individually, rather than eight at a time.
How much is when I got weird.
Going through the large primes I've got a cache size.
I go through each of the primes, adding a modulo and a word index to get the bit that needs to be set next. When the modulo overflows the word index gets incremented too.
I do that for a block of memory, then repeat for the next prime, and so on until I've done all the primes. I then go onto the next block of memory - which is tuned to fit in the cache.
Rather than do some arithmetic I though I'll just run through a loop with different sizes of that memory block, and pick the best one. That's a bit under a megabyte.
I then remove the loop, instead having a constexpr for the size.
The code now runs a third slower.
I can have the loop go around exactly once, and it is still way faster than the hard coded constant!
Andy