Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Vir Campestris <vir.campestris@invalid.invalid>
Newsgroups: comp.lang.c++
Subject: Re: OT: Re: Sieve of Erastosthenes optimized to the max
Date: Tue, 20 Aug 2024 17:55:33 +0100
Organization: A noiseless patient Spider
Lines: 53
Message-ID: <va2hq5$3f1gl$1@dont-email.me>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org>
 <utoh9d$6lrr$1@raubtier-asyl.eternal-september.org>
 <utq0ag$hvrl$3@dont-email.me>
 <utq0os$ibqn$1@raubtier-asyl.eternal-september.org>
 <utq11p$icmm$1@dont-email.me> <v25c87$1ld9m$1@dont-email.me>
 <86r0duwqgg.fsf@linuxsc.com> <v39o3l$1lvju$1@dont-email.me>
 <86o78mpnlf.fsf@linuxsc.com> <v3fv2u$2ursd$1@dont-email.me>
 <86ttibod7n.fsf@linuxsc.com> <86h6eaoi2r.fsf@linuxsc.com>
 <v4sool$1grge$1@dont-email.me> <867celixcw.fsf@linuxsc.com>
 <v5sg9s$mat4$1@dont-email.me> <86zfr0b9hw.fsf@linuxsc.com>
 <v638ud$25623$1@dont-email.me> <861q3o5do1.fsf@linuxsc.com>
 <v7tdts$29195$1@dont-email.me> <868qx45v5g.fsf@linuxsc.com>
 <v9lbns$11alj$1@dont-email.me> <86r0aojx1m.fsf@linuxsc.com>
 <v9o2kf$1gqv1$1@raubtier-asyl.eternal-september.org>
 <va09jq$30cvv$1@dont-email.me>
 <va2ca2$3e60e$1@raubtier-asyl.eternal-september.org>
 <va2cfr$3e9l1$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Tue, 20 Aug 2024 18:55:34 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="fa6adec55a411a22e0ad067099c2adf6";
	logging-data="3638805"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/oCs+BDO86CVBwmMXdJPo501dNCBw9rMg="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:hu7iSk1z+ck7Z3uih4X9vkqETrs=
In-Reply-To: <va2cfr$3e9l1$1@raubtier-asyl.eternal-september.org>
Content-Language: en-GB
Bytes: 4314

On 20/08/2024 16:24, Bonita Montero wrote:
> Am 20.08.2024 um 17:21 schrieb Bonita Montero:
>> Am 19.08.2024 um 22:23 schrieb Vir Campestris:
>>> On 16/08/2024 18:35, Bonita Montero wrote:
>>> <snip>
>>>> But basically I don't think it is a good idea to skip numbers exept
>>>> multiples of two. With the three you save a sixth of memory, with
>>>> the five you save a 15-th and at the end you get about 20% less
>>>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
>>>> for a lot of computation. That's the point where I dropped this
>>>> idea and I think this extra computation is higher than the time
>>>> for the saved memory loads.
>>>>
>>> It's not just storage you save, it's also computation.
>>>
>>> That program I published up-thread is almost as fast as yours - 
>>> within 10% of the elapsed time - while only using a single core. The 
>>> amount of CPU used is much lower.
>>>
>>> Andy
>>
>> On my AMD 7990X all primes up to 2 ^ 32 are calculated with my code
>> with a 65W-setting of the CPU in 0.168s. The total CPU-time is 3.688s.
>> With your code all primes up to 2 ^ 32 take nearly exactly four seconds
>> with a single thread. So the overall computation time with my algorithm
>> is about seconds less.
> 
> And if I run my code with a single core:
> 
>      C:\Users\Boni\Documents\Source\bitmapSieve>timep 
> "x64\Release-clang++\bitmapSieve.exe" 0x100000000 "" 1
>      real   1.795s
>      user   1.766s
>      sys    0.000s
>      cylces 8.011.804.500
> 
> Thats less than half the computation time.

That's really odd. I too have an AMD - although my AMD Ryzen 5 3400G is 
chosen for low power, not speed. Surely it can't be because I use Linux, 
not Windows?

I'm leaning towards thinking you may have a point on the mod30 code. 
There are more operations on the innermost loop with mod30, although the 
loop goes around fewer times. It also means that the store is forced to 
be byte wide - I find that my original odd-only code is significantly 
faster - about 30% - when the store is 64 bit wide rather than byte.

Speed of writing the primes out? I don't care. The only reason I put it 
in there was to allow me to check the output. If I did care I'd be 
putting a more efficient enumeration function too.

Andy