Comparability between implementations

[dnlmlr]

The problem

I just took a look at the implementations for C, C++ & Rust as those are commonly known for getting highly optimized versions in benchmarks. And indeed there are quite highly optimized versions to be found.
But after looking at the C implementations, I was wondering at what point the implementations are no longer comparable.

In my opinion it is not really possible to compare the languages in any meaningful way, when some versions optimize the algorithm itsef in the way that most of the C implementations do. Of course the meaningful comparison is debatable in any case, but I would argue that it may still produce interesting results when all implementations use the same base algorithm.

The original implementation was optimized to skip even numbers which is quite reasonable and results in no cpu time overhead while calculating or counting since it just increments by 2 instead of 1.

Almost all C versions on the other hand further optimized the skipping part, with not only skipping even numbers but instead also skipping higher multiples of other primes (2, 3, 5) or even skipping multiples of all primes up to 13 in one example. This of course provides a significant boost to performance (at least the first few) but is now no longer comparable to the original version (and in turn any language that doesn't use the same optimizations). This optimization is of course quite clever and would be valid in any other case, but here it is basically just using existing knowledge to highly decrease the workingset to a much smaller size than the other implementations have to deal with. (Just skipping the multiples of 3 decreases the unchecked values from about 500_000 to only about 166_667)

Besides the counting part now no longer being trivial (and not being timed), this of course makes C/C++ and in turn all languages with implementations that use this optimization seem much faster in relation to other languages than they are.

A language that is inherntly slower than another language could implement this change an in turn look faster on paper, while the other just doesn't have this optimization.

Considerations for a solution

Ok I don't really have a solution, but here are some of my considerations:

• Constructs and optimizations that a language provides are fine and wanted (for example using iterators / filters in rust instead of the normal for loops, or C++ vector find) since those represent the languages features
• The base algorithm should have to be the same if any cross language comparison is wanted (outer loop, find next factor, set values for this factor, increment factor)
• The factor checking HAS to start with 3 and not 5, 7, or even higher to stay comparable
• The way how the smaller tasks in the algorithm, like setting / clearing or storing the values can be changed as needed

[flo80]

Considerations for a solution

Ok I don't really have a solution, but here are some of my considerations:

• Constructs and optimizations that a language provides are fine and wanted (for example using iterators / filters in rust instead of the normal for loops, or C++ vector find) since those represent the languages features
• The base algorithm should have to be the same if any cross language comparison is wanted (outer loop, find next factor, set values for this factor, increment factor)
• The factor checking HAS to start with 3 and not 5, 7, or even higher to stay comparable
• The way how the smaller tasks in the algorithm, like setting / clearing or storing the values can be changed as needed

Well this would exactly be my understanding of the rules in CONTRIBUTING.md. If an implementation wants to be base, it has to use the algorithm as in the original solution and it has to start checking at 3. If it want's to be faithful it also has to stick to some memory management rules.

So a comparison of results using base and being faithful should still be valid I think.

[rbergen]

So a comparison of results using base and being faithful should still be valid I think.

On top of that, Dave's leaderboard will only include solutions that use 1 bit per prime candidate.

[sglienke]

I think what's considered faithful and what not is a bit of a nitpick when it comes to some details.
The space for the storage for example can be halfed without changing the algorithm itself and goes in line with the inc by 2 loop. When even numbers are not even counted except 2 then why put them into the sieve at all.

Also the fact that vector<bool> is implemented as bitpacked storage and the C++ compilers know about that is an implementation detail and should not force other implementations to do the same - whether this fact even matters highly depends on your L1 cache size and the bit-twiddling can even be detrimental for performance.

[rbergen]

This is also my response to your comment on #398: the rules are indeed somewhat arbitrary. They're based on a) the 3 implementations that started this project, and b) what Dave has explicitly indicated is important to him (bit twiddling is one of them). They've been in place for a while now, and they've served us to the point that there are now well over 100 implementations in 53 languages in this repo dealing with them.

[yellowcub]

@sglienke That makes sense, but it also turned out the validation failed so it was turning off more bits than it was supposed to. After I fixed it, it did run slower 😕 than the 8bit default.

[ManDeJan]

Eg ZIG2 probably shouldn’t be faithful (the sieve size / memory is constant/ compile time as far as I understand zig).

I think that's actually correct. The combined use of const and comptime do effectively translate to sieve and memory size being set at compile time, which goes against the clarified guidelines.
@ityonemo / @ManDeJan would you care to comment on this?

Yes, as it stands, there are two sieves benchmarked in solution_2, the first sieve does indeed use the zig bool type that is 8 bits in size therefore not making it faithfull. The second sieve (bit sieve) does use 1 bit per prime making it more faithfull. It is true however that both these sieves know their size at compile time making the memory allocation slightly cheaper (since it can allocate it quickly on the stack). I could change it to make it dynamically allocate memory, though I doubt it'll make much of a difference in the rankings since most of the time is spent in the actually calculating of primes.

[sglienke]

@ManDeJan Stack vs heap allocation is indeed something I personally think should be left as an implementation detail. And this is why I was rather disappointed that using a class was a requirement as that for some languages forces heap allocation while in the original C++ implementation by Dave it was stack-allocated. Depending on the memory model being used underneath heap allocations can have more or less impact (GC, aggressive memory reuse etc).

[rbergen]

I could change it to make it dynamically allocate memory

@ ManDeJan Please do. I accept that the rules are somewhat arbitrary, but due to the nature of the project we do have to make a genuine effort to apply them in a consistent fashion. In that context, I am actually happy that you don't expect it to make much of a difference, performance-wise.

[rbergen]

@ManDeJan I've opened #483 to mark Zig/solution_2 as unfaithful. I'm now holding and won't merge if you're able to make the changes you've indicated within the next few days.

[rbergen]

Is there any timeframe for the leaderboard?

My expectation would be that the "final leaderboard" will be announced/discussed after Dave concludes discussing all the languages in the repo. Considering the fact we're at around 60 languages at the moment, that might take some time still.
There's one big disclaimer with that statement: Dave has complete liberty on how he puts his videos/series together. and part of that is that he's also allowed to change his mind. So the word "expectation" in the first sentence should in no way be read as "guarantee".

Can you point me to a good example how I might incorporate both solutions using the same Docker as you had mentioned?

PrimeBASIC/solution_1 could be used as an example.

[yellowcub]

I appreciate the acknowledgment on timeframe - I am supposed to be on vacation 😁. I have a solution but I would like to work on it just a little bit 🤔 before submitting. I will look at the example you gave for using a single Docker. Thx!