Msieve 1.53 feedback

[Dubslow]

Got a segfault while attempting filtering.

skipped 130 relations with b > 2^32
skipped 2795 relations with composite factors
found 49597092 hash collisions in 240782473 relations
added 1218076 free relations
commencing duplicate removal, pass 2
found 49638605 duplicates and 192361944 unique relations
memory use: 1321.5 MB
reading ideals above 179896320
commencing singleton removal, initial pass
memory use: 3012.0 MB
reading all ideals from disk
memory use: 3195.8 MB
commencing in-memory singleton removal
begin with 192361944 relations and 156762241 unique ideals
reduce to 125054811 relations and 82631540 ideals in 13 passes
max relations containing the same ideal: 36
reading ideals above 720000
commencing singleton removal, initial pass
memory use: 2756.0 MB
reading all ideals from disk
memory use: 3924.2 MB
Segmentation fault (core dumped)

I went back and remdups'd it to cut the error messages, then ran it again, and it worked fine that time (well it failed to build a matrix, but didn't segfault).

Just under 200M unique rels, SNFS(235).

[Dubslow]

Originally Posted by Dubslow

I went back and remdups'd it to cut the error messages, then ran it again, and it worked fine that time (well it failed to build a matrix, but didn't segfault).

Correction: I had some issues doing the remdups correctly (relating to limited space on the 40 GB SSD), and after fixing those unrelated issues, filtering with only the 192M uniques did commence to a full merge, which is well past the point that segfaulted. Matrix build failed with too few cycles, but that's just my TD.

[debrouxl]

Today, in order to reduce filtering time for a highly oversieved dataset, I wanted to raise the initial max weight used for filtering, as I knew that 20 or 25 wouldn't yield a workable matrix. I made the initial max weight configurable, like the target density and several other filtering parameters; the patch against SVN r1018 is attached.

FWIW, in the end, the dataset was so severely oversieved (360+M relations for a 31-bit LPs task, after over 3M free relations were added by earlier filtering stages) that even at max weight=40, filtering produced a matrix with density ~41. I remembered about the filtering collapse issue, I just didn't expect it to be so bad
So I added filter_maxrels=300000000, lowered target_density from 110 to 100, and filtering succeeded.

[jasonp]

Patches merged into SVN trunk.

[jyb]

Here's an interesting problem. I've just had two different NFS@Home jobs hang during the initial reading of the relations file. Turns out to have been caused by the same issue. In both cases there are quite a few corrupt lines in the relations file. Usually msieve is good about just ignoring them, but each of these particular jobs had a killer line in it. Here are the two lines:

1,0,4C38,44200F,3:09ADAB0,1452B8,B,12FB92AF,17FD1B,199678,177D596D7A032,3805DD:CE98B2B:4E2066D1:2A3C0F,1

1,0C5553,21730724:6DAB96731BD,7766B6,3DFF8138A5A,15B187E30815AB:E5CC747817ACF29310AD4B,22F359DA456EE9

The problem here is the beginning of the lines. Msieve is looking for two decimal numbers (a and b), separated by a comma. In each of these cases it will interpret the input as a = 1 and b = 0. The latter causes this line to be interpreted as a free relation (I think), which in turn results in a call to mp_is_prime_1() with an argument of 1. That function has the following (p is the argument):

        uint32 d = p - 1;
...
	while (!(d & 1)) {
                s++;
                d >>= 1;
	}

With p = 1, this is an infinite loop.

I suspect that the combination a = 1 and b = 0 could never be correct, so the test in nfs_read_relation() could have this patch:

--- gnfs/relation.c	(revision 1028)
+++ gnfs/relation.c	(working copy)
@@ -127,7 +127,7 @@
 		   be given p < 2^32 */
 
 		p = (uint64)a;
-		if (p == 0 || p >= ((uint64)1 << 32))
+		if (p <= 1 || p >= ((uint64)1 << 32))
 			return -2;
 
 		if (test_primality && !mp_is_prime_1((uint32)p))

But it's probably also worth putting a guard in mp_is_prime_1(), which I suppose could be something like this:

--- common/mp.c	(revision 1028)
+++ common/mp.c	(working copy)
@@ -1765,6 +1765,7 @@
 	uint32 r;
 	uint32 s = 0;
 
+	if (d == 0) return 0;
 	while (!(d & 1)) {
 		s++;
 		d >>= 1;

[jasonp]

Thanks for tracking this down, the relation parsing code has been a hotspot for bugs because messed up relations can take so many different forms. Will commit the changes soon.

[jyb]

Originally Posted by jasonp

Thanks for tracking this down, the relation parsing code has been a hotspot for bugs because messed up relations can take so many different forms. Will commit the changes soon.

Thanks. While you're at it, can you go ahead and address the problem detailed in post #75? Here's a patch that fixes that:

Index: common/driver.c
===================================================================
--- common/driver.c	(revision 1028)
+++ common/driver.c	(working copy)
@@ -219,7 +219,8 @@
 	   what you're doing) */
 
 	if (obj->flags & MSIEVE_FLAG_NFS_ONLY) {
-		factor_gnfs(obj, &n, &factor_list);
+		if (factor_list_add(obj, &factor_list, &n) > 0)
+			factor_gnfs(obj, &n, &factor_list);
 		goto clean_up;
 	}