Assembly entry

[joonicks]

The poor state of this entry makes me sad.. sadly, Im horrible at using git so I dont really feel confident about contributing.

(x86_64) A simple loop unroll boosted performance by +50%

[rbergen]

As with any entry, I'm really interested to see the improvements that existing or new contributors can make. I therefore whole-heartedly invite you to put the effort into getting better at using git and then improving the Assembly entry to the absolute best of your ability.

[joonicks]

I was wondering, since malloc in libc is essentially a C function, in an assembly environment would the use or brk() and not unallocating after each run violate the faithfullness?

[rbergen]

Yes, it would. For a fair faithful comparison, certain base rules need to be universally applied even when it feels more "natural" not to, in a specific language. This has been extensively documented in earlier PRs and discussions.

That said, if you were to implement a runtime memory allocation/deallocation approach written in Assembly that replaces the one provided by libc, then we could certainly consider it.

[joonicks]

Ive come to realise that the optimizing task here isnt so much about making the code smaller but rather to figure out clever ways of minimizing the number of bit clearing operations. sieveLoop only runs 500 times, clearBitLoop is only entered 167 times.

[joonicks]

I just submitted my unrolled solution.

The way forward now to me seems to be figuring out how to calculate,

1. the length of the pattern produced,
2. how far to extend that pattern so its in place for the next pattern to be overlaid

for the factor 3, the pattern is 3 bytes, for factor 5 its 5 bytes
so initially the first pattern only needs to be extended 15? bytes to proceed with the algoritm, instead of 125000 bytes
writing 15 bytes instead of 125000 is one heck of a timesaver

its just very hard work to implement a new/experimental algorithm in assembly

[joonicks]

in fact, now im wondering if its possible to write out the pattern only once and then only extend it as needed for the new pattern

[joonicks]

in my head this works perfectly for factor 3 and 5.
factor 3 pattern (3 bytes) only needs to be written once
for factor 5, factor 3 needs to be continued six more times to a point they will be in sync, then factor 5 probably needs to be extended to that sync point.
after that my head starts hurting trying to imagine if the same algorithm pattern continues

[rbergen]

I have not yet looked at the code in your PR in detail, but looking at these comments it sounds to me like you may be calculating a bit mask in a (small) number of bytes for prime numbers 3 and 5, and then somehow projecting that mask onto (the rest of) the sieve. If that is indeed the case, the algorithm would no longer be considered the base algorithm. The definition of that algorithm includes that "When clearing non-primes in the sieve (the second operation), the algorithm clears all non-primes individually, increasing the number with 2 * factor on each cycle."

[joonicks]

If the last line of your comment was a rule, all unrolled loop solutions would be unfaitful/non base.

As for the "calculation" of a patters, thats a no. it started as an if-then-else exercise, but it turns out that for bit patters downsized to a byte, there are only two possibilities. for your original bitshift as it was writing dwords, that one has 8 different possibilities.
that the patterns repeats after 4 bytes is a happy coincidence/quirk of the math involved.