How to make this parallel prime sieve faster?

26

I wrote my own version from scratch to demonstrate parallel chunks. I only sieved odds to keep it simple, rather than using a higher modulus and residue like yours, but it should be possible to do more. Call it an exercise for the reader.

My results:

  serial: 5218023786 ns
parallel: 741314228 ns
-> 7.04x speedup

This is on an i7-4600U -- dual-core with hyperthreading, so only 4 logical CPUs. Bonus points if you figure out how this achieved a super-linear speedup!

(Note that this does require current rayon.git for the as-yet unpublished par_chunks_mut.)

1 Like