Msieve 1.53 feedback

[Batalov]

Were you banned from google?

1.53 is the version in progress (the latest released was 1.52), so go to
http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/

[jasonp]

I increment the version number once a release happens on sourceforge, so this is shorthand for "whatever the latest source will build".

jyb: this may have something to do with David Cleaver adding his primality proving code to Msieve

[Anyone]

Originally Posted by Batalov

Were you banned from google?

1.53 is the version in progress (the latest released was 1.52), so go to
http://sourceforge.net/p/msieve/code/HEAD/tree/trunk/

I thought there is a new stable version which I can't find. Thank you anyway :)

[WraithX]

Originally Posted by jasonp

I increment the version number once a release happens on sourceforge, so this is shorthand for "whatever the latest source will build".

jyb: this may have something to do with David Cleaver adding his primality proving code to Msieve

I had tested Msieve+APRCL successfully locally, and I see that a few people have used it over in the NFS@Home forum (like fivemack, debrouxl, YuL). There are even some cases where 3 factors were shown as prime. I'll look at jyb's test cases to try to see if I can repeat the problem and then track down what is going wrong.

[WraithX]

Originally Posted by jyb

Sure, here are a couple of such logs. The first is especially interesting, since msieve quit even though the cofactor was composite.

> 8+7,257.log.txt
> 8-5,257.log.txt

I forgot to ask, would you happen to have those relations still available? Or know where I can download them? If they're already gone, that's fine, I'll sieve it here, but wanted to ask first to try to save some time.

[jasonp]

I don't see how it could be an issue either, but r984 is really recent. In fact the demo binary should be printing out the composite factor even if the NFS square root stopped immediately, so the odds are overwhelming that something else is going on.

Can you at least run dependencies beyond the first to recover the extra factors?

[jyb]

Originally Posted by WraithX

I forgot to ask, would you happen to have those relations still available? Or know where I can download them? If they're already gone, that's fine, I'll sieve it here, but wanted to ask first to try to save some time.

Yes, I have all the relevant files, though they're in excess of 10 GB uncompressed. I don't have a good place to leave them for you, and that's a bit of a painful upload for me, in any case. However, before we try to work that out or you go sieving yourself, I'm (slowly) doing a bit of debugging on my end. So far I can say that a debug build of msieve, running on a different machine, does not appear to be having this problem, at least not when run in the debugger.

Originally Posted by jasonp

I don't see how it could be an issue either, but r984 is really recent. In fact the demo binary should be printing out the composite factor even if the NFS square root stopped immediately, so the odds are overwhelming that something else is going on.

Can you at least run dependencies beyond the first to recover the extra factors?

Yes, I ran msieve with other dependencies and it completed just fine.

[chris2be8]

A few questions spring to mind (I've spent more time than I want to remember trying to pin down this sort of problem):

What command lines did you call msieve with? (I've often wished msieve put out a log message saying what parms it was called with.)
What OS are you running?
Is the "other machine" where it worked under the debugger running *exactly* the same OS?
Does a non-debug build on that machine produce the error?

Chris

[jyb]

Originally Posted by chris2be8

A few questions spring to mind (I've spent more time than I want to remember trying to pin down this sort of problem):

What command lines did you call msieve with? (I've often wished msieve put out a log message saying what parms it was called with.)
What OS are you running?
Is the "other machine" where it worked under the debugger running *exactly* the same OS?
Does a non-debug build on that machine produce the error?

Chris

Well that turned out to be interesting. I was wrong when I said that the debug build didn't have the problem. It did have the problem, it just manifested differently. More on that below.

The issue is with MSIEVE_FLAG_NFS_ONLY, the flag which tells msieve to skip right to NFS processing and forgo other methods (e.g. trial factoring, ECM). This flag can be set with the -z command line option, though I never used it myself. Due to *another* problem which was present in r984, but subsequently fixed in r986, msieve acted like that flag was set. So the problem occurs in r984, but it doesn't happen with r986 or later unless you explicitly set that flag. Has no one else run into this? That would be surprising, unless nobody else has used r984 or r985.

In msieve_run(), the factor_list variable is set up to store factors of the given composite (N) as they are found. For most processing (Pollard rho, ECM, NFS), the variable contains N, then as factors are found they are reconciled with N via a GCD. NFS processing completes when there are no more composites in factor_list (at least, none above a certain size).

But the initial trial-factoring is done without N in factor_list, so factor_list actually starts out empty, then N is inserted after trial-factoring is done. Okay, fine. Problem is, with MSIEVE_FLAG_NFS_ONLY set, msieve jumps right to NFS, skipping over the other methods. And it does so without remembering to first add N to factor_list. So when factors are found, the test for whether to keep going short-circuits. If the first factor added is prime, there's nothing to do a GCD with, so the prime just gets added without its cofactor being added. Then NFS processing just stops, because there are no composites left in the list. If the first factor added is composite then processing continues, but if a prime factor of the remaining composite is added, then the list will end up with the two primes that make up that composite, but the remaining primes are omitted in the same way.

This problem will occur any time the -z flag is used. But given that I wasn't running with the -z flag, why did I hit this? In r984, when this flag was introduced, it was defined in msieve.h without a correct value. Specifically, it was just added to an enum without an explicit value set, so it was given the value one more than the previous item. So it got the value 0x4001, which is problematic for flags which are supposed to be bit-fields. The test for the presence of this flag is:

if (obj->flags & MSIEVE_FLAG_NFS_ONLY)

So if obj->flags includes 0x0001 (MSIEVE_FLAG_USE_LOGFILE), which it always will unless you use the -q flag, then the test will evaluate to true.

This last issue was fixed in r986, when MSIEVE_FLAG_NFS_ONLY was correctly defined as 0x8000. But as mentioned, the -z flag will still cause factors to not be reported.

Finally, a word about optimized vs. non-optimized builds. I saw a difference in the behavior of this bug depending on whether or not I compiled with optimizations. I was testing with a composite N that had three factors: a p53, a p62, and a p80. During the square root phase, the first dependency split N into p80 and c115. If msieve first tries to add the p80 to its factor list, then it will immediately stop processing, as described above, and just print out that p80. OTOH, if it first adds the c115 then it will go on to dependency 2, which splits N into p62 and c133. If it adds the p62 to the factor list, then msieve will stop and print out the p53 and the p62. If it adds the c133, then after the appropriate GCDs, the factor list will have all the prime factors so it will stop and appear to be correct.

In practice I only ever saw the first two scenarios. With optimizations, msieve always added the p80 first and quit. Without optimizations, it always added the c115 first, then with the second dependency it added the p62 first. So the behavior was different, but either way the output was wrong. But the question is, why would there be a difference in behavior depending on optimizations? I know that without this bug, it shouldn't matter at all which order the factors are added, but I still would have thought that the choice of factor to add would be deterministic.

Jason, can you think of any reason there should be a difference? It may not matter, but I've found that a difference in behavior which depends on optimization level usually indicates a bug somewhere.

[debrouxl]

A wish list item: some form of support for affinity setting for LA.

Rationale: on most quad-core processors, msieve LA scales best with 4 threads. On my Sandy Bridge and Ivy Bridge Core i7, when I set up the following affinities for these 4 threads after the three additional workers are spawned:
* affinity 11 for thread 1;
* affinity 22 for thread 2;
* affinity 44 for thread 3;
* affinity 88 for thread 4
LA is consistently 20-30% faster than if I don't constrain the scheduler not to screw up. IOW, wall clock time savings quickly add up to a whole day.
Affinities 10, 20, 40 and 80 seem to yield worse results than 11, 22, 44 and 88.

I'm aware of numactl and hwloc, but they don't seem to be what I'm looking for.

The affinity could be specified by the user through the command line, e.g. by
* -t 4 affinity=11:22:44:88 (affinity masks);
* -t 4 cores=0:1:2:3 (physical core IDs);
* -t 4 processors=04:15:26:37 (processor IDs).
(or rather an argument to -nc2 / -ncr ?)
The former is easiest to deal with programmatically: affinity masks are the main way to set affinities, across all OS. The two other forms, as well as automatic affinity setting, would require parsing processor and core info in order to compute the affinity masks, which is more complex.

WDYT about the general direction ? Prototyping with a static core assignment is easy, for instance by fiddling with threadpool_init() or by adding a new function for setting affinities in the thread pool.

[jyb]

Originally Posted by jyb

Well that turned out to be interesting. I was wrong when I said that the debug build didn't have the problem. It did have the problem, it just manifested differently. More on that below.

The issue is with MSIEVE_FLAG_NFS_ONLY, the flag which tells msieve to skip right to NFS processing and forgo other methods (e.g. trial factoring, ECM). This flag can be set with the -z command line option, though I never used it myself. Due to *another* problem which was present in r984, but subsequently fixed in r986, msieve acted like that flag was set. So the problem occurs in r984, but it doesn't happen with r986 or later unless you explicitly set that flag. Has no one else run into this? That would be surprising, unless nobody else has used r984 or r985.

In msieve_run(), the factor_list variable is set up to store factors of the given composite (N) as they are found. For most processing (Pollard rho, ECM, NFS), the variable contains N, then as factors are found they are reconciled with N via a GCD. NFS processing completes when there are no more composites in factor_list (at least, none above a certain size).

But the initial trial-factoring is done without N in factor_list, so factor_list actually starts out empty, then N is inserted after trial-factoring is done. Okay, fine. Problem is, with MSIEVE_FLAG_NFS_ONLY set, msieve jumps right to NFS, skipping over the other methods. And it does so without remembering to first add N to factor_list. So when factors are found, the test for whether to keep going short-circuits. If the first factor added is prime, there's nothing to do a GCD with, so the prime just gets added without its cofactor being added. Then NFS processing just stops, because there are no composites left in the list. If the first factor added is composite then processing continues, but if a prime factor of the remaining composite is added, then the list will end up with the two primes that make up that composite, but the remaining primes are omitted in the same way.

This problem will occur any time the -z flag is used. But given that I wasn't running with the -z flag, why did I hit this? In r984, when this flag was introduced, it was defined in msieve.h without a correct value. Specifically, it was just added to an enum without an explicit value set, so it was given the value one more than the previous item. So it got the value 0x4001, which is problematic for flags which are supposed to be bit-fields. The test for the presence of this flag is:

if (obj->flags & MSIEVE_FLAG_NFS_ONLY)

So if obj->flags includes 0x0001 (MSIEVE_FLAG_USE_LOGFILE), which it always will unless you use the -q flag, then the test will evaluate to true.

This last issue was fixed in r986, when MSIEVE_FLAG_NFS_ONLY was correctly defined as 0x8000. But as mentioned, the -z flag will still cause factors to not be reported.

Finally, a word about optimized vs. non-optimized builds. I saw a difference in the behavior of this bug depending on whether or not I compiled with optimizations. I was testing with a composite N that had three factors: a p53, a p62, and a p80. During the square root phase, the first dependency split N into p80 and c115. If msieve first tries to add the p80 to its factor list, then it will immediately stop processing, as described above, and just print out that p80. OTOH, if it first adds the c115 then it will go on to dependency 2, which splits N into p62 and c133. If it adds the p62 to the factor list, then msieve will stop and print out the p53 and the p62. If it adds the c133, then after the appropriate GCDs, the factor list will have all the prime factors so it will stop and appear to be correct.

In practice I only ever saw the first two scenarios. With optimizations, msieve always added the p80 first and quit. Without optimizations, it always added the c115 first, then with the second dependency it added the p62 first. So the behavior was different, but either way the output was wrong. But the question is, why would there be a difference in behavior depending on optimizations? I know that without this bug, it shouldn't matter at all which order the factors are added, but I still would have thought that the choice of factor to add would be deterministic.

Jason, can you think of any reason there should be a difference? It may not matter, but I've found that a difference in behavior which depends on optimization level usually indicates a bug somewhere.

Ping.

Jason, any thoughts on this? And can this bug be fixed?