Msieve 1.40 Beta Feedback - Page 2

bsquared · 2009-03-02, 21:13

Quote:

Originally Posted by XYYXF

So now QS became much faster?

I've found that the version 1.40 precompiled windows binary, at least on my 3.4 GHz Xeon desktop running winXP (32bit), is around 6-10% faster than 1.39 depending on the input size.

I also found that, when compiled and run under 64 bit linux, or when the precompiled windows binary was run on 64 bit Windows (Win Server 2003), there was no change at all in speed.

- ben.

*EDIT*
Ok, the precompiled binary is running faster now on the 64 bit windows OS, for inputs >= 75 digits. About 10% again. Not sure why the lower ones are not... probably because 10% of a shorter run is in the runtime noise.

jasonp · 2009-03-02, 21:17

Alex: you can uncomment the '#define CHECK' line at the top of gnfs/poly/stage1/stage1_sieve.c ; this will print out whenever a leading rational coefficient is found that has a chance of leading to a good polynomial.

However, your 159-digit input will still use 155-digit parameters, and with this constraint you may not even be able to find a polynomial in stage 1. To have a reasonable chance of finding something, you'll need to append some entries to the table at the top of gnfs/poly/poly_skew.c . The norms and target Murphy E value match whatever is in GGNFS (which unfortunately only goes up to 155 digits) and the last entry obeys a simple power law.

Ben, the 64-bit code version does not use explicit asm containing CMOVs for modular adds and subtracts in include/mp.h (I assumed the compiler would do this, but 64-bit gcc does not). Could this be turned on by changing ASM32A to ASM64A in mp_modadd_1 and mp_modsub_1? The result may not work, but QS timings would be interesting...

akruppa · 2009-03-02, 21:36

Ok, thanks. I simply extrapolated all the entries in the table exponentially. Now (with CHECK defined) it prints stuff like

Code:

coeff 390000-392940 1415755472 1840482113 1840482114 2392626748 lattice 4290783374
p 1415755472 1840482113 1840482114 2392626748 lattice 4290783374
batch 5000 1417076053
poly 2 p 1416990017 q 1840496437 coeff 2607965077553069429
poly 36 p 1416435989 q 1840554899 coeff 2607028198673860111
poly 29 p 1416112639 q 1840843789 coeff 2606842156027549171
poly 7 p 1416245111 q 1840994947 coeff 2607300093064454117
poly 39 p 1416924391 q 1841002403 coeff 2608561208700311573
poly 5 p 1416425939 q 1841071547 coeff 2607741494725657633
poly 8 p 1416346403 q 1841142199 coeff 2607695130965160197
poly 25 p 1416436613 q 1841239921 coeff 2607999637421627573
poly 23 p 1416569069 q 1841427001 coeff 2608508532438032069
poly 48 p 1416264013 q 1841431687 coeff 2607953430695979931
poly 7 p 1416134539 q 1841473133 coeff 2607773706281840687
poly 5 p 1416330499 q 1841612149 coeff 2608331453957632351
poly 40 p 1416190619 q 1841867951 coeff 2608436113642951669
poly 8 p 1416081143 q 1841879323 coeff 2608250576981906189

so I guess it's doing something.

Alex

bsquared · 2009-03-02, 21:45

Quote:

Originally Posted by jasonp

Ben, the 64-bit code version does not use explicit asm containing CMOVs for modular adds and subtracts in include/mp.h (I assumed the compiler would do this, but 64-bit gcc does not). Could this be turned on by changing ASM32A to ASM64A in mp_modadd_1 and mp_modsub_1? The result may not work, but QS timings would be interesting...

I just tried this, everything compiled ok.

But when I run it I get lots of 'failed to read relation' errors during filtering followed by a core dump or a linear algebra failure. On the bright side, it was 12% faster on a C75 (151 sec vs 170 sec).

bsquared · 2009-03-02, 22:03

I just tried something else that may interest you.

I put in YAFU's modsub_1 and modadd_1 functionality for 64 bit compiles and I get 154 seconds for the same C75. Not quite as fast as the CMOV timings, but still a 10% improvement and now it works and finds the factors.

Here is the code for modsub_1:

Code:

#elif defined(GCC_ASM64A)
        uint32 t = a-b;
        return t += ((t >> 31) * p);

and for modadd_1

Code:

#elif defined(GCC_ASM64A)
        uint32 t = a + b;
        return t -= ((t >= p) * p);

Unpredictable branches suck :)

*EDIT*
On second thought, no reason why those need to be GCC_ASM64 protected... nothing special going on there. You could put them in the generic code path.

jasonp · 2009-03-02, 22:05

Perhaps the register allocation for 64-bit MSVC has to be different? I have no way to test though...

mdettweiler · 2009-03-02, 22:16

I'm getting a very strange error message when I try to use the 1.40 beta (specifically, the precompiled Windows binary) to search for a polynomial on a C101. I ran msieve with the following command line:

msieve -np -v 49166330342884147367327358139225399025609854308836843947823205057271599090927675596136134442517663871

At first all appeared to be well, so I walked away from the computer. I came back about 5 minutes later and saw the following error message being spewed out onto the console in what seemed to be an infinite loop at an extremely fast rate:

too many line iterations

One thing of note is that this isn't *really* a Windows system that this binary is being run on. I'm actually running it through the Wine emulator on a 32-bit Linux system. So, it's possible that running it through the emulator is somehow causing the error, though I don't have any conclusive proof either way.

If it might help, then later today I can try watching the output carefully to see exactly what msieve is doing when the infinite-error-message-loop begins.

akruppa · 2009-03-02, 22:26

The fastest addmod I managed is

(blah blah removed... never mind, Jason uses the same)

Alex

jasonp · 2009-03-02, 23:26

Quote:

Originally Posted by mdettweiler

If it might help, then later today I can try watching the output carefully to see exactly what msieve is doing when the infinite-error-message-loop begins.

Don't bother, I can reproduce the problem locally. Will do more digging tonight.

Alex: I think the issue with the CMOVs is that MSVC inline asm is a lot more primitive in the constraints it can force on input operands. The code has MSVC asm that implicitly assumes ordinary x86 calling conventions, whereas the 64-bit version has different calling conventions.

tmorrow · 2009-03-03, 02:16

I take your point on the -Wconversion option.

I did a build on a Linux server running RHAT5 x86_64 using "make x86_64 ECM=1". Again using ECM 6.2.1 and GMP 4.2.4.

Compiling with gcc version 4.1.2 20070626 (Red Hat 4.1.2-14)

In addition to the 3 benign dd_clear_precision -Wconversion warnings I got 8 warnings like this one:

Code:

gcc -D_FILE_OFFSET_BITS=64 -O3 -fomit-frame-pointer -march=k8 -DNDEBUG  -Wall -W -Wconversion -I. -Iinclude -Ignfs/poly -I/home/tmorrow/software/ecm/include -I/home/tmorrow/software/gmp/include -DHAVE_GMP_ECM -DHAVE_GMP -c -o common/smallfact/gmp_ecm.o common/smallfact/gmp_ecm.c
In file included from include/gmp_xface.h:20,
                 from common/smallfact/gmp_ecm.c:34:
/home/tmorrow/software/gmp/include/gmp.h: In function '__gmpz_getlimbn':
/home/tmorrow/software/gmp/include/gmp.h:1694: warning: passing argument 1 of '__builtin_expect' with different width due to prototype
/home/tmorrow/software/gmp/include/gmp.h:1694: warning: passing argument 2 of '__builtin_expect' with different width due to prototype
/home/tmorrow/software/gmp/include/gmp.h: In function '__gmpz_perfect_square_p':
/home/tmorrow/software/gmp/include/gmp.h:1722: warning: passing argument 1 of '__builtin_expect' with different width due to prototype
/home/tmorrow/software/gmp/include/gmp.h:1722: warning: passing argument 2 of '__builtin_expect' with different width due to prototype
/home/tmorrow/software/gmp/include/gmp.h: In function '__gmpz_popcount':
/home/tmorrow/software/gmp/include/gmp.h:1740: warning: passing argument 1 of '__builtin_expect' with different width due to prototype
/home/tmorrow/software/gmp/include/gmp.h:1740: warning: passing argument 2 of '__builtin_expect' with different width due to prototype

I'm not certain whether -Wconversion is spitting out harmless errors here or not.

I'm testing with QS with a C97 now to see how it goes.

jasonp · 2009-03-03, 13:22

Quote:

Originally Posted by jasonp

Don't bother, I can reproduce the problem locally. Will do more digging tonight.

Found the problem, and it was somewhat silly. Beta #2 will have it fixed.

tmorrow: those warnings actually look like an oversight in GMP, though they also look harmless.

2009-03-02, 21:17	#13
jasonp Tribal Bullet Oct 2004 3,541 Posts	Alex: you can uncomment the '#define CHECK' line at the top of gnfs/poly/stage1/stage1_sieve.c ; this will print out whenever a leading rational coefficient is found that has a chance of leading to a good polynomial. However, your 159-digit input will still use 155-digit parameters, and with this constraint you may not even be able to find a polynomial in stage 1. To have a reasonable chance of finding something, you'll need to append some entries to the table at the top of gnfs/poly/poly_skew.c . The norms and target Murphy E value match whatever is in GGNFS (which unfortunately only goes up to 155 digits) and the last entry obeys a simple power law. Ben, the 64-bit code version does not use explicit asm containing CMOVs for modular adds and subtracts in include/mp.h (I assumed the compiler would do this, but 64-bit gcc does not). Could this be turned on by changing ASM32A to ASM64A in mp_modadd_1 and mp_modsub_1? The result may not work, but QS timings would be interesting... Last fiddled with by jasonp on 2009-03-02 at 21:29

2009-03-02, 22:03	#16
bsquared "Ben" Feb 2007 DB9₁₆ Posts	I just tried something else that may interest you. I put in YAFU's modsub_1 and modadd_1 functionality for 64 bit compiles and I get 154 seconds for the same C75. Not quite as fast as the CMOV timings, but still a 10% improvement and now it works and finds the factors. Here is the code for modsub_1: Code: #elif defined(GCC_ASM64A) uint32 t = a-b; return t += ((t >> 31) * p); and for modadd_1 Code: #elif defined(GCC_ASM64A) uint32 t = a + b; return t -= ((t >= p) * p); Unpredictable branches suck :) EDIT On second thought, no reason why those need to be GCC_ASM64 protected... nothing special going on there. You could put them in the generic code path. Last fiddled with by bsquared on 2009-03-02 at 22:12

2009-03-02, 22:26	#19
akruppa "Nancy" Aug 2002 Alexandria 2,467 Posts	The fastest addmod I managed is (blah blah removed... never mind, Jason uses the same) Alex Last fiddled with by akruppa on 2009-03-02 at 23:32

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.51 feedback	xilman	Msieve	256	2014-01-26 22:06
Msieve v1.46 feedback	em99010pepe	Msieve	153	2010-12-12 14:21
Msieve 1.44 feedback	xilman	Msieve	111	2010-09-14 21:50
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53

2009-03-02, 22:05	#17
jasonp Tribal Bullet Oct 2004 3,541 Posts	Perhaps the register allocation for 64-bit MSVC has to be different? I have no way to test though...

2009-03-02, 22:16	#18
mdettweiler A Sunny Moo Aug 2007 USA (GMT-5) 3·2,083 Posts	I'm getting a very strange error message when I try to use the 1.40 beta (specifically, the precompiled Windows binary) to search for a polynomial on a C101. I ran msieve with the following command line: msieve -np -v 49166330342884147367327358139225399025609854308836843947823205057271599090927675596136134442517663871 At first all appeared to be well, so I walked away from the computer. I came back about 5 minutes later and saw the following error message being spewed out onto the console in what seemed to be an infinite loop at an extremely fast rate: too many line iterations One thing of note is that this isn't really a Windows system that this binary is being run on. I'm actually running it through the Wine emulator on a 32-bit Linux system. So, it's possible that running it through the emulator is somehow causing the error, though I don't have any conclusive proof either way. If it might help, then later today I can try watching the output carefully to see exactly what msieve is doing when the infinite-error-message-loop begins.