Thoughts on Prime Number Generation Challenge and a Possible Spin-Off

[JamesLear92]

Hello

Really enjoying the prime number generation challenge.

Most newcomers might be creating a usable list or array of primes when comparing their results to these benchmarks. It's a more intuitive approach since anyone writing a function to produce prime numbers wants to see the numbers it produced, but this is a disadvantage in this challenge as these conversions aren't factored into the benchmark.

Currently, we're generating a bitarray to show primes as 1s and 0s, or true and false. To make it actually usable, we convert it to a list or array of primes. In the current rules, we're just creating a count to verify the results after the benchmark, but this just highlights that a bitarray isn't really what we want from the code.

So, here's an idea: A separate challenge that requires usable data generation - A list or array of primes. This way, we can bench the entire process and keep the benchmarks slightly more real world relevant.

Newcomers are going to start off with a naive implementation that returns actual primes, it's a tiny bit of a shame they can't begin their optimisation journey from there, rather than the unfamiliar deep end.

Maybe it's worth a shot?

Cheers,

James

[rbergen]

I'm converting this to an Ideas discussion.

[rbergen]

@JamesLear92 I'm not exactly sure I understand how you envisage implementing this in a practical sense? We have close to 450 benchmarked implementations in the project at the moment, all of which have been developed in accordance with the current rules.

Which are actually rules I am personally happy with - and I do acknowledge I can easily be accused of bias -, to a large extent because I think they are a good translation of the original challenge. That challenge being figuring out which language/implementation is the fastest at identifying prime numbers, which does not necessarily include the fastest approach towards converting the identified primes to an easy-to-digest format.

Still, I'd be interested to know how you'd structure this separate/spin-off challenge, in the context of the implementations that are already there.

[enki42]

There is an issue I see with the rules in this regard. This one:
Your benchmarked code returns either a list of primes or the is_prime array, containing the result of the sieve.

If you write multithreaded code does this list or just the count need to be passed into some form of controller thread? The overhead of data being shared between threads can be high (copy the data so no shared memory between threads, lock the data so there is more context switching, etc) This can also impact reuse of the memory space taken up by the array/collection of primes.

[JamesLear92]

The current setup is great and I'm not suggesting we change the essence of it. But I propose an additional property to the test results, whether it returns a collection or generates an unprocessed sieve that is just inferred to be correct based on count.
We have the existing benchmarks but add a filterable column to PrimeView for those implementations that return actual prime numbers in a collection.

This way, we maintain the integrity of the original challenge but also provide visibility into the full prime number generation process. It's optional, so there's no extra work for those who prefer to stick with the current rules. But for those who have or want to develop a method that includes the conversion step, it offers a way to demonstrate and compare that additional functionality.

The benefit is twofold: it respects the existing work and benchmarks while offering insights into the conversion performance for those interested. It might also encourage developers to consider optimization for practical applications where you need the actual primes, not just an optional inference that it's likely produced something that could then be converted to primes if needed.

I'd imagine that the implementation would need some sort of flag that can be recognised by primeview. I don't have a suggestion for how that is done, but hopefully someone who's worked on primeview might have a better idea.

[rbergen]

Adding another property to PrimeView is not just a matter of adding a column to PrimeView. One would have to:

• Add the new property to the list of "known properties" in the project documentation
• Add the property to the output of all existing implementations where it's appropriate according to the property's criteria. Note that the total number of implementations now exceeds 450, and this type of property has to be deduced through manual inspection of an implementation's source code.
• Make the benchmark tooling recognize, pick up and report the new property
• Have the back-end service that benchmark tooling and PrimeView connect to also recognize, store and return the new property
• Extend PrimeView to include it (this would be the new "column" mentioned)
• Include assessing if the property is appropriately set in every future review of new solutions or updates to existing ones

That's a lot of work, so there has to be a very good reason to indeed introduce a new property. And if I'm totally honest, I don't think this is one.

The rules of this project were drafted to on the one hand allow a somewhat fair comparison between languages and approaches, and on the other hand give solution authors the freedom to make choices about how they want to write their implementation(s). The choices authors make within the boundaries of the rules are implementation details from the perspective of this project, and we don't report on any of those. The properties we do report on (number of bits per prime candidate, algorithm and faithfulness) directly matter to what it is this project cares about: the speed with which the execution of the Sieve of Eratosthenes for a certain sieve size can be completed. Exactly how the end result is reported back isn't part of that - what we require is that the result can be validated, and that's possible with both result types that the rules allow.

[JamesLear92]

@rbergen Honestly that's a shame to hear, but I really appreciate you taking the time to address this fully - I don't think I appreciated how much work would be required to add this in.

[rbergen]

@JamesLear92 You're welcome. I genuinely don't mean to boast or complain, but getting to the current state of affairs took a lot of work. Don't get me wrong, it was fun - and I still enjoy maintaining it - but a lot of work indeed. (And we are hugely indebted to @marghidanu for all the contributions he has made, some of which made the whole project move forwards in leaps and bounds.)

And yes, it is all interconnected - like a "real" software solution would be also. 🙂 In fact, just adding a solution in a new language already requires an update to PrimeView - that one just to make the link to the web page for the language work.

[niftyhacking]

Parallelism is complicated. Also the space used to represent primes can be tuned. The array space reduction can be clever. The easy space saver is Odd/Even so the array of bits can be half the search space. With each prime the space can be reduced. Or the results of a searched block encoded into an answer structure. Is this in the mix? Hadoop can be on an N core CPU or an N core cluster. https://saturncloud.io/blog/parallel-algorithms-for-generating-prime-numbers/ It makes sense to limit these to CPU and unpaged Memory

…

On Mon, Sep 11, 2023 at 1:05 PM enki42 ***@***.***> wrote: There is an issue I see with the rules in this regard. This one: Your benchmarked code returns either a list of primes or the is_prime array, containing the result of the sieve. If you write multithreaded code does this list or just the count need to be passed into some form of controller thread? The overhead of data being shared between threads can be high (copy the data so no shared memory between threads, lock the data so there is more context switching, etc) This can also impact reuse of the memory space taken up by the array/collection of primes. — Reply to this email directly, view it on GitHub, or unsubscribe. You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- T o m M i t c h e l l (on NiftyEgg[.]com )