YAFU Poly Select Deadline

amphoria · 2016-09-14, 15:32

I am using the YAFU factor() command to factor some C99s on a computer with 8 cores, so threads is set to 8. In factor.log I get the following messages for poly select:

commencing poly select with 8 threads
setting deadline of 148 seconds
completed 8 ranges of size 250 in 875 seconds

The third message is printed 875 seconds after the second message.

My query is that YAFU is spending almost 15 minutes on poly select when the lattice sieving is only taking about 10 minutes on 8 threads. This is excessive.

This is with YAFU v1.34 on Windows 10 64-bit. Is there a problem with the poly select deadline that YAFU is passing to msieve? I know that I can override the poly select deadline in YAFU but I can't work out how to do this with multiple threads.

bsquared · 2016-09-14, 16:21

Something is wrong... it should be doing way more than 8 ranges of 250. Here is test I just ran:

Code:

nfs: commencing nfs on c100: 18027160975221650182578588284151114970600...
nfs: commencing poly selection with 8 threads
nfs: setting deadline of 152 seconds
nfs: completed 350 ranges of size 250 in 160.2835 seconds

Yafu asks msieve to find polys in small ranges at a time precisely to avoid this problem (any one range taking excessively long to search). In your case it asked for a small range (for each thread, thus 8 total ranges) and those ranges for some reason took a very long time to complete.

Is there something non-standard about your msieve installation? Does it do this on every C99 you've tried or just this one?

bsquared · 2016-09-14, 16:24

The YAFU option, btw, that might help here is -pbatch. Change it to something much smaller than 250 (say, 10), and see what that does.

e.g.:
./yafu "nfs(foo)" -pbatch 10 -threads 8 -v

amphoria · 2016-09-14, 16:47

Quote:

Originally Posted by bsquared

Is there something non-standard about your msieve installation? Does it do this on every C99 you've tried or just this one?

It's the compiled in msieve contained in yafu 1.34 as posted on SourceForge. I have seen the same behaviour on every C99 on this computer and another one with 16 cores and 16 threads with the same yafu version.

I will try reducing the batch size as suggested in your other post.

henryzz · 2016-09-14, 17:03

Quote:

Originally Posted by amphoria

It's the compiled in msieve contained in yafu 1.34 as posted on SourceForge. I have seen the same behaviour on every C99 on this computer and another one with 16 cores and 16 threads with the same yafu version.

I will try reducing the batch size as suggested in your other post.

That in itself is a bit old.

amphoria · 2016-09-14, 18:35

Quote:

Originally Posted by bsquared

The YAFU option, btw, that might help here is -pbatch. Change it to something much smaller than 250 (say, 10), and see what that does.

e.g.:
./yafu "nfs(foo)" -pbatch 10 -threads 8 -v

I had to reduce it to pbatch=5 to get close to the deadline.

Quote:

Originally Posted by henryzz

That in itself is a bit old.

I agree but I did not want to build it from source at the time. I am now going to bite the bullet. I have already built mpir and ecm with VS2013 so this should be doable. ~~The only possible complication is that there is no VS2013 non-gpu build directory for msieve, so I am hoping that I can start with the VS2012 one.~~

bsquared · 2016-09-14, 22:21

Good to know that -pbatch helps, but this doesn't really fix the problem. The problem is that msieve should be able to search leading coefficients up to the 10's of thousands in 150 seconds with 8 threads on a C99. From the sound of it you are searching a range 50x less than that. So we can make it stay around the deadline with this method but you may be finding subpar polys.

Questions:
Can you post the same output you did before with pbatch=5?
This is with the prebuild windows executables correct? Was it actually YAFU 1.34.5 or 1.34?
Can you post a test number? I'll see if I can reproduce this here.

LaurV · 2016-09-15, 05:19

Same here.
We never found this issue because in all cases, our C99s are done by SIQS, as the crossover is over 100. But if forced to GNFS, it seems that the "long time for poly" behavior is the "normal" one.

amphoria · 2016-09-15, 08:59

Quote:

Originally Posted by bsquared

Good to know that -pbatch helps, but this doesn't really fix the problem. The problem is that msieve should be able to search leading coefficients up to the 10's of thousands in 150 seconds with 8 threads on a C99. From the sound of it you are searching a range 50x less than that. So we can make it stay around the deadline with this method but you may be finding subpar polys.

Questions:
Can you post the same output you did before with pbatch=5?
This is with the prebuild windows executables correct? Was it actually YAFU 1.34.5 or 1.34?
Can you post a test number? I'll see if I can reproduce this here.

Code:

yafu "nfs(741244879109376246366513985428555418845913568310626508732412421094649581664407020182598936240636611)" -v -pbatch 5

Code:

nfs: commencing nfs on c99: 741244879109376246366513985428555418845913568310626508732412421094649581664407020182598936240636611
nfs: commencing poly selection with 8 threads
nfs: setting deadline of 148 seconds
nfs: completed 67 ranges of size 5 in 200.9028 seconds
nfs: best poly = # norm 1.646415e-013 alpha -4.744248 e 1.356e-008 rroots 4

I haven't managed to get Yafu to print a version number, but the name of the file is yafu-1.34.zip as posted at https://sourceforge.net/projects/yafu/. I am using the executable yafu-x64.exe.

EdH · 2016-09-15, 13:42

Quote:

Originally Posted by amphoria

[CODE]I haven't managed to get Yafu to print a version number, but the name of the file is yafu-1.34.zip as posted at https://sourceforge.net/projects/yafu/. I am using the executable yafu-x64.exe.

That's v1.34.5. It should open up in a console window by just double-clicking it:

amphoria · 2016-09-15, 14:13

Quote:

Originally Posted by EdH

That's v1.34.5. It should open up in a console window by just double-clicking it:

You are correct as I have just realised that the version number is also printed on every line in factor.log.

For completeness I have also built yafu and msieve using VS2013. Yafu and msieve were built from the latest trunk code. This built Yafu 1.34.5 also. However the issue with poly select deadline still exists, so it might be something related to "small" composites.

2016-09-14, 15:32	#1
amphoria "Dave" Sep 2005 UK 2³·347 Posts	YAFU Poly Select Deadline I am using the YAFU factor() command to factor some C99s on a computer with 8 cores, so threads is set to 8. In factor.log I get the following messages for poly select: commencing poly select with 8 threads setting deadline of 148 seconds completed 8 ranges of size 250 in 875 seconds The third message is printed 875 seconds after the second message. My query is that YAFU is spending almost 15 minutes on poly select when the lattice sieving is only taking about 10 minutes on 8 threads. This is excessive. This is with YAFU v1.34 on Windows 10 64-bit. Is there a problem with the poly select deadline that YAFU is passing to msieve? I know that I can override the poly select deadline in YAFU but I can't work out how to do this with multiple threads.

2016-09-14, 16:21	#2
bsquared "Ben" Feb 2007 7276₈ Posts	Something is wrong... it should be doing way more than 8 ranges of 250. Here is test I just ran: Code: nfs: commencing nfs on c100: 18027160975221650182578588284151114970600... nfs: commencing poly selection with 8 threads nfs: setting deadline of 152 seconds nfs: completed 350 ranges of size 250 in 160.2835 seconds Yafu asks msieve to find polys in small ranges at a time precisely to avoid this problem (any one range taking excessively long to search). In your case it asked for a small range (for each thread, thus 8 total ranges) and those ranges for some reason took a very long time to complete. Is there something non-standard about your msieve installation? Does it do this on every C99 you've tried or just this one? Last fiddled with by bsquared on 2016-09-14 at 16:21 Reason: truncated input number

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Running YAFU via Aliqueit doesn't find yafu.ini	EdH	YAFU	8	2018-03-14 17:22
A Desperate appeal! (by Richard K. Guy)... deadline is September 30, 2016	philmoore	Factoring	102	2016-10-01 12:16
msieve poly select: choosing Stage1norm	VBCurtis	Msieve	0	2016-04-11 21:33
Starting NFS skipping poly select	jux	YAFU	5	2016-01-02 01:01
Time it takes to select polynomials for 154 digits	John5788	Factoring	23	2008-08-27 07:54

2016-09-14, 16:24	#3
bsquared "Ben" Feb 2007 2·3·17·37 Posts	The YAFU option, btw, that might help here is -pbatch. Change it to something much smaller than 250 (say, 10), and see what that does. e.g.: ./yafu "nfs(foo)" -pbatch 10 -threads 8 -v

2016-09-14, 22:21	#7
bsquared "Ben" Feb 2007 2×3×17×37 Posts	Good to know that -pbatch helps, but this doesn't really fix the problem. The problem is that msieve should be able to search leading coefficients up to the 10's of thousands in 150 seconds with 8 threads on a C99. From the sound of it you are searching a range 50x less than that. So we can make it stay around the deadline with this method but you may be finding subpar polys. Questions: Can you post the same output you did before with pbatch=5? This is with the prebuild windows executables correct? Was it actually YAFU 1.34.5 or 1.34? Can you post a test number? I'll see if I can reproduce this here.

2016-09-15, 05:19	#8
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 2·5,179 Posts	Same here. We never found this issue because in all cases, our C99s are done by SIQS, as the crossover is over 100. But if forced to GNFS, it seems that the "long time for poly" behavior is the "normal" one.