primesieve-7.2

primesieve-7.2 features a new algorithm for medium sieving primes that improves the CPU's branch prediction rate by sorting the sieving primes (before using them). On AMD EPYC CPUs I have measured a speedup of up to 20% and on Intel Skylake CPUs I have measured a speedup of up to 10%. Ever since primesieve was created in 2010 its algorithm for medium sieving primes has been slower than yafu's algorithm for medium sieving primes. This performance issue has now been fixed!

Benchmark primesieve 7.1 vs 7.2

Start	primesieve 7.1 AMD EPYC 7401P	primesieve 7.2 AMD EPYC 7401P	primesieve 7.1 Intel Xeon 8124M	primesieve 7.2 Intel Xeon 8124M
1010	2.73 sec	2.27 sec	1.97 sec	1.83 sec
1011	3.18 sec	2.65 sec	2.25 sec	2.06 sec
1012	4.00 sec	3.25 sec	2.64 sec	2.39 sec
1013	5.24 sec	4.11 sec	3.22 sec	2.92 sec
1014	6.44 sec	5.03 sec	3.82 sec	3.53 sec
1015	7.67 sec	6.04 sec	4.40 sec	4.08 sec
1016	8.81 sec	7.22 sec	5.03 sec	4.72 sec
1017	10.53 sec	8.51 sec	5.84 sec	5.60 sec

At each start offset primesieve counted the primes inside an interval of size 10^10 using a single thread.