Sr2sieve on PPC/Linux

[Cruelty]

Here are my results on C2D@2.4GHz running version 1.5.10 of linux.x86-64 binary

sr2sieve 1.5.10 -- A sieve for multiple sequences k*b^n+/-1.
L1 data cache 32Kb (detected), L2 cache 2048Kb (detected).
Read 233216 terms for 14 sequences from dat format file `riesel.dat'.
Split 14 base 2 sequences into 425 base 2^60 subsequences.
Using 16 Kb for the baby-steps giant-steps hashtable, maximum density 0.16.
Best time for baby step method gen/2: 36891.
Best time for baby step method gen/4: 28404.
Best time for baby step method gen/8: 29061.
Best time for baby step method gen/1: 42660.
Best time for giant step method gen/2: 18009.
Best time for giant step method gen/4: 16902.
Best time for giant step method gen/8: 16911.
Best time for giant step method gen/1: 22446.
Best time for ladder method gen/2: 1467.
Best time for ladder method gen/4: 1143.
Best time for ladder method gen/8: 1269.
Best time for ladder method gen/1: 2538.
Best time for ladder method add/1: 2943.
Using baby step method gen/4, giant step method gen/4, ladder method gen/4.
Using 1024Kb for the Sieve of Eratosthenes bitmap.
Expecting to find factors for about 4552.40 terms in this range.
sr2sieve started: 680004 <= n <= 1000000, 11000000000000 <= p <= 20000000000000
p=11000122028941, 2040651 p/sec, 0 factors, 0.00% done, ETA 20 Aug 06:13

[geoff]

I have had a look at the code produced for the ppc64, it seems that GCC is unable to move some constants outside of the critical loops due to aliasing issues, and so it does some redundant reloading of registers. In version 1.5.12 I have made a few changes that might help, but the real solution is probably to code the whole loop in assembly, not just the loop body as we do now.

BlisteringSheep: If you can send me the assembled bsgs.s file for 1.5.12 as before, I will check whether the changes have had the expected effect.

[BlisteringSheep]

Here are the gcc-4.1.1 and gcc-4.1.2 versions. Everything did compile cleanly. I haven't done correctness or performance testing yet, but will start right away.

A couple of questions:

1. Is the sr5check.txt test with p from 5e9 to 5.1e9 sufficient for exercising the code with factors > 2^32?
2. Do you have any opinions on the quality of the code generated by gcc-4.1.1 vs. that generated by gcc-4.1.2? I don't see any measurable difference in execution times.
3. Does including the output from multiple compilers as I've been doing help or just add noise? I haven't done timing checks with gcc-3.x compilers in a while because in the beginning gcc-4.x was demonstrably faster.

[geoff]

Originally Posted by BlisteringSheep

Here are the gcc-4.1.1 and gcc-4.1.2 versions. Everything did compile cleanly.

The changes worked, I've attached the new loop for comparison: three less loads and one less subtraction. Whether it makes much difference I don't know.

Is the sr5check.txt test with p from 5e9 to 5.1e9 sufficient for exercising the code with factors > 2^32?

Not entirely, each of the combinations of baby and giant step methods could have different bugs :-(. A comprehensive test would require running with switches `-Bgen/x -Ggen/y' for each combination of x and y in {1,2,4,8}. That would be quite tedious. A lot of the code for the gen/8 methods is just cut and paste from gen/4, and gen/4 is cut and paste from gen/2, etc. So I expect any bugs would be likely to show up in the gen/8 methods.

Do you have any opinions on the quality of the code generated by gcc-4.1.1 vs. that generated by gcc-4.1.2? I don't see any measurable difference in execution times.

I can't see any significant difference, but I only looked at a few spots in the code. I have found with the x86 builds that GCC 3.4 is faster than GCC 4.1, which is a change since the 1.4.x verisons of sr2sieve.

Does including the output from multiple compilers as I've been doing help or just add noise? I haven't done timing checks with gcc-3.x compilers in a while because in the beginning gcc-4.x was demonstrably faster.

It is probably not necessary to do both versions unless you notice a performance difference between them. Even then it may be hard to figure out why one is faster than the other.

[BlisteringSheep]

sr5check passed with both 100e6-150e6 and 5e9-5.1e9. I will setup a test to run the comprehensive list of methods. Is there any way to tell it to not print the factors to the screen? I'd like to capture the output from -vv, to confirm that I'm passing the command-line flags correctly, but don't really need to see all 10000 factors .

Timing results for riesel.dat and SoB.dat with 1.5.10 EXP 1 vs. 1.5.12. Another measurable speedup.

Summary:
v1.5.10 riesel.dat: 301294 p/sec
v1.5.12 riesel.dat: 314009 p/sec
v1.5.10 SoB.dat: 504277 p/sec
v1.5.12 SoB.dat: 521006 p/sec

Full results with -vv output is attached. I also did some testing with gcc-3.4.6, and gcc-4.1.x is still measurably faster.

[BlisteringSheep]

Originally Posted by geoff

Not entirely, each of the combinations of baby and giant step methods could have different bugs :-(. A comprehensive test would require running with switches `-Bgen/x -Ggen/y' for each combination of x and y in {1,2,4,8}. That would be quite tedious. A lot of the code for the gen/8 methods is just cut and paste from gen/4, and gen/4 is cut and paste from gen/2, etc. So I expect any bugs would be likely to show up in the gen/8 methods.

I ran all permutations of x & y with both the 100e6-150e6 and 5e9-5.1e9 ranges and every one passed. Good work!

[geoff]

Version 1.5.13 has a few small changes, it should be a little faster than 1.5.12, but if not then I will undo them. There are no changes to the assembler routines, so just a brief test should suffice.

I realise now that testing each of the 16 combinations of -Bgen/x and -Ggen/y options was not necessary, just testing the 4 combinations with -Bgen/x and -Ggen/x would have been enough to exercise all the assembler routines.

[BlisteringSheep]

Passed both of my sr5check tests fine. It is indeed faster (timings from 2.0 GHz 970FX):

1.5.12 SoB.dat: 250971 p/sec
1.5.13 SoB.dat: 258296 p/sec

1.5.12 riesel.dat: 417483 p/sec
1.5.13 riesel.dat: 435247 p/sec

sr5check timings:
1.5.12 100e6-150e6: 84.432 cpu sec
1.5.13 100e6-150e6: 80.542 cpu sec

1.5.12 5e9-5.1e9: 141.644 cpu sec
1.5.13 5e9-5.1e9: 135.267 cpu sec


Looks like I'll be deploying this version. :)