Running Msieve

[JHansen]

With only one core the LA took 1hr9mins, with max memory usage at about 232MB.

The dual core LA was 52 mins, max mem usage 417MB.

Mon May 21 12:52:45 2007  
Mon May 21 12:52:45 2007  
Mon May 21 12:52:45 2007  Msieve v. 1.22
Mon May 21 12:52:45 2007  random seeds: 0bc3a62c 1506c228
Mon May 21 12:52:45 2007  factoring 419623832897771350700010781466963547592960694394751245814861806724281650265191070069221647901484064031010752997237754619 (120 digits)
Mon May 21 12:52:45 2007  commencing number field sieve (120-digit input)
Mon May 21 12:52:46 2007  R0: -143733799094117939873204
Mon May 21 12:52:46 2007  R1:  1571675241229
Mon May 21 12:52:46 2007  A0: -13301770869023917069542383757
Mon May 21 12:52:46 2007  A1: -3354843473866079084112555
Mon May 21 12:52:46 2007  A2: -86225108642303173709
Mon May 21 12:52:46 2007  A3:  180020813747795
Mon May 21 12:52:46 2007  A4:  13713426042
Mon May 21 12:52:46 2007  A5:  6840
Mon May 21 12:52:46 2007  size score = 2.310744e-012, Murphy alpha = -5.631304, combined = 1.509964e-011
Mon May 21 12:52:46 2007  
Mon May 21 12:52:46 2007  commencing linear algebra
Mon May 21 12:52:46 2007  factor base loaded:
Mon May 21 12:52:46 2007  330960 rational ideals (max prime = 4730729)
Mon May 21 12:52:46 2007  330655 algebraic ideals (max prime = 4730729)
Mon May 21 12:52:47 2007  read 646484 cycles
Mon May 21 12:52:49 2007  cycles contain 1742683 unique relations
Mon May 21 12:53:19 2007  read 1742683 relations
Mon May 21 12:53:22 2007  using 32 quadratic characters above 134215748
Mon May 21 12:54:26 2007  matrix is 646284 x 646484 with weight 60100338 (avg 92.96/col)
Mon May 21 12:54:27 2007  filtering completed in 1 passes
Mon May 21 12:54:28 2007  matrix is 646284 x 646484 with weight 60100338 (avg 92.96/col)
Mon May 21 12:54:31 2007  saving the first 48 matrix rows for later
Mon May 21 12:54:32 2007  matrix is 646236 x 646484 with weight 46217476 (avg 71.49/col)
Mon May 21 12:54:32 2007  matrix includes 64 packed rows
Mon May 21 12:54:32 2007  using block size 65536 for processor cache size 2048 kB
Mon May 21 13:55:39 2007  lanczos halted after 10220 iterations
Mon May 21 13:55:40 2007  recovered 40 nontrivial dependencies
Mon May 21 13:55:41 2007  
Mon May 21 13:55:41 2007  commencing square root phase
Mon May 21 13:55:41 2007  reading relations for dependency 1
Mon May 21 13:55:41 2007  read 322340 cycles
Mon May 21 13:55:42 2007  cycles contain 1074603 unique relations
Mon May 21 13:56:13 2007  read 1074603 relations
Mon May 21 13:56:20 2007  multiplying 1703646 relations
Mon May 21 14:03:59 2007  multiply complete, coefficients have about 77.19 million bits
Mon May 21 14:04:03 2007  initial square root is modulo 347099
Mon May 21 14:13:54 2007  reading relations for dependency 2
Mon May 21 14:13:55 2007  read 323518 cycles
Mon May 21 14:13:56 2007  cycles contain 1077382 unique relations
Mon May 21 14:14:27 2007  read 1077382 relations
Mon May 21 14:14:35 2007  multiplying 1708202 relations
Mon May 21 14:22:17 2007  multiply complete, coefficients have about 77.39 million bits
Mon May 21 14:22:21 2007  initial square root is modulo 358931
Mon May 21 14:32:07 2007  prp56 factor: 10331079714165495587348393993849306277311230762925348159
Mon May 21 14:32:07 2007  prp65 factor: 40617616406773309930157031809690324332672374273933632071917743941
Mon May 21 14:32:07 2007  elapsed time 01:39:22

[jasonp]

Originally Posted by JHansen

With only one core the LA took 1hr9mins, with max memory usage at about 232MB.

The dual core LA was 52 mins, max mem usage 417MB.

Are you sure about the memory use? Using two threads for this size problem should only take up about 3MB more than using one thread. 232MB sounds about right though.

Using 2 threads on a core2duo seems to consistently speed things up about 25%. Using 2 threads on a dual-CPU (not dual-core) opteron speeds things up by ~35%, but the test machine has slower DDR333 memory so the core2duo time is still a lot faster.

[JHansen]

Originally Posted by jasonp

Are you sure about the memory use? Using two threads for this size problem should only take up about 3MB more than using one thread. 232MB sounds about right though.

I restarted it and now the memory does indeed stay low. I have no idea why Task Manager would report the higher value for max mem usage before.

--
Cheers,
Jes

[jasonp]

Originally Posted by JHansen

I restarted it and now the memory does indeed stay low. I have no idea why Task Manager would report the higher value for max mem usage before.

Maybe proceeding from the filtering straight to the linear algebra causes windows to retain allocated memory, either that or there's a memory leak somewhere.

[ewmayer]

Originally Posted by jasonp

Maybe proceeding from the filtering straight to the linear algebra causes windows to retain allocated memory, either that or there's a memory leak somewhere.

Jason, do you have a reliable program for detecting memory leaks on that platform? Ever use the Valgrind package?

[jasonp]

Originally Posted by ewmayer

Jason, do you have a reliable program for detecting memory leaks on that platform? Ever use the Valgrind package?

I love valgrind, use it at work and at home. It's found msieve bugs before but I haven't run it recently. The time needed for some of these jobs means I have to use it sparingly; the NFS square root takes 10x longer if run with a debug binary, and valgrind adds another 3-10x on top of that.

[Andi47]

Originally Posted by jasonp

Now available. Highlights include:

Are there some important differences to the 1.22alpha you linked here last week? I.e.: Should I upgrade to 1.22 to continue my c10x's?

P.S.: I had paused the work on the c101 and a c103 for I few days, and continued since yesterday in the morning.

I have experienced this at the very start of NFS:

for the c101 I have interrupted it half a minute from start because I had forgotten to add the "-v". (I want to see on the screen what it does). Due to this interruption Msieve has stopped the poly selection and started sieving on restart.
for the c103 which I started approx. 20 hours after starting the c101, I allowed the poly selection to finish (no interruption for adding -v to the command line ).

Current state of the sieving: for both numbers 3.7M relations have been found, and for both filtering wanted ~1.2M more relations. (for the c101 this number was a little bit bigger).

the c101 is currently at: b = 583380, found 3808221 relations, need 4952856

the c103 is currently at: b = 397610, found 4371503 relations, need 4923186

so the c103 is of course faster than the c101 (with interrupted poly selection).

Suggestion / feature request: If the poly selection is interrupted early (for example for such stupid things like adding a forgotten -v to the command line), it would be nice if the program asks if the poly selection should be continued, or if it should start sieving immediately.

[smh]

Originally Posted by Andi47

for the c101 I have interrupted it half a minute from start because I had forgotten to add the "-v". (I want to see on the screen what it does). Due to this interruption Msieve has stopped the poly selection and started sieving on restart.

I guess it found a poly in during the first half a minute. In this case, i would have started all over again.

Originally Posted by Andi47

for the c103 which I started approx. 20 hours after starting the c101, I allowed the poly selection to finish (no interruption for adding -v to the command line ).

After sieving starts, you should be able to interupt and continue with -v

Originally Posted by Andi47

the c101 is currently at: b = 583380, found 3808221 relations, need 4952856

the c103 is currently at: b = 397610, found 4371503 relations, need 4923186

so the c103 is of course faster than the c101 (with interrupted poly selection).

i guess the poly for the c101 wasn't a really good one.

[Andi47]

Originally Posted by smh

i guess the poly for the c101 wasn't a really good one.

obviously, yes. When I run poly selection for half a minute, it finds a poly, but to find a better poly, it needs time.
I did not know, that it starts with sieving immediately when I interrupt after half a minute to add the -v to the input line - otherwise I would have waited for sieving to begin or deleted the savefiles to restart from scratch. (that's why I asked for a feature that the program asks if I really want to stop searching a polynomial and start with sieving if poly selection is interrupted early.)

[jasonp]

Originally Posted by Andi47

obviously, yes. When I run poly selection for half a minute, it finds a poly, but to find a better poly, it needs time.
I did not know, that it starts with sieving immediately when I interrupt after half a minute to add the -v to the input line - otherwise I would have waited for sieving to begin or deleted the savefiles to restart from scratch. (that's why I asked for a feature that the program asks if I really want to stop searching a polynomial and start with sieving if poly selection is interrupted early.)

Andi,

v1.22 has a few small multithreading improvements and bug fixes compared to the alpha version I posted, I'd recommend switching to it.

I'll think about what you suggest, but any solution is going to have to give up if you used some other tool to generate the polynomial. Msieve will find a suitable polynomial in a fraction of a second, and will find a decent one within a minute or so. Finding a good one, i.e. better than these, is what takes minutes-to-hours.

Sander, the runs that are giving me problems include a C129 and C136 via GNFS, and a C200 vis SNFS.

[Andi47]

Originally Posted by jasonp

Andi,

v1.22 has a few small multithreading improvements and bug fixes compared to the alpha version I posted, I'd recommend switching to it.

Is it intended that it tries filtering when I stop and restart after having found more relations than needed for the first filtering attempt, but less than for the second one? (originally it needed 3.7M relations, then it filtered and wanted 1.2M more relations, so it restarted sieving and now needs 4.9M relations. I stopped after having found 4.04M relations and tried restarting both with 1.22 and 1.22alpha. (I experienced a problem, see below, so I switched back to 1.22alpha, but the 1.22alpha has the same problem, so I am now continueing with 1.22)

Did you change anything in saving the relations between versions 1.21 and 1.22alpha? During filtering it gave a series of error -14 and one error-3 reading certain relations (totals to 55 bad relations):

1.22 logfile reads:

Sun May 27 20:25:05 2007  Msieve v. 1.22
Sun May 27 20:25:05 2007  random seeds: 551b5afc 85b4f970
Sun May 27 20:25:05 2007  factoring 59851368441126867505175036119618017965374014823386475353855554519233951829509128116614500240090827807 (101 digits)
Sun May 27 20:25:05 2007  commencing number field sieve (101-digit input)
Sun May 27 20:25:05 2007  R0: -175286939562562530
Sun May 27 20:25:05 2007  R1:  1
Sun May 27 20:25:05 2007  A0:  2954919142613807
Sun May 27 20:25:05 2007  A1: -3053237587397760
Sun May 27 20:25:05 2007  A2:  2379165919791292
Sun May 27 20:25:05 2007  A3:  2488888495499642
Sun May 27 20:25:05 2007  A4: -2775280927915645
Sun May 27 20:25:05 2007  A5:  361681497428832
Sun May 27 20:25:05 2007  size score = 1.031788e-010, Murphy alpha = -2.650199, combined = 2.496008e-010
Sun May 27 20:25:15 2007  restarting with 4046282 relations
Sun May 27 20:25:15 2007  
Sun May 27 20:25:15 2007  commencing relation filtering
Sun May 27 20:25:15 2007  commencing duplicate removal, pass 1
Sun May 27 20:25:19 2007  error -14 reading relation 419584
Sun May 27 20:25:20 2007  error -14 reading relation 448609
Sun May 27 20:25:20 2007  error -14 reading relation 504209
Sun May 27 20:25:22 2007  error -14 reading relation 627685
Sun May 27 20:25:22 2007  error -14 reading relation 648897
Sun May 27 20:25:22 2007  error -14 reading relation 671884
Sun May 27 20:25:23 2007  error -14 reading relation 723819
Sun May 27 20:25:24 2007  error -14 reading relation 830715
Sun May 27 20:25:26 2007  error -14 reading relation 1020917
Sun May 27 20:25:26 2007  error -14 reading relation 1020968
Sun May 27 20:25:26 2007  error -14 reading relation 1068758
Sun May 27 20:25:27 2007  error -14 reading relation 1111589
Sun May 27 20:25:27 2007  error -14 reading relation 1148791
Sun May 27 20:25:28 2007  error -14 reading relation 1220163
Sun May 27 20:25:29 2007  error -14 reading relation 1291952
Sun May 27 20:25:29 2007  error -14 reading relation 1297280
Sun May 27 20:25:29 2007  error -14 reading relation 1313716
Sun May 27 20:25:30 2007  error -14 reading relation 1403724
Sun May 27 20:25:32 2007  error -14 reading relation 1534919
Sun May 27 20:25:33 2007  error -14 reading relation 1658666
Sun May 27 20:25:33 2007  error -14 reading relation 1675327
Sun May 27 20:25:33 2007  error -14 reading relation 1679435
Sun May 27 20:25:35 2007  error -14 reading relation 1793328
Sun May 27 20:25:35 2007  error -14 reading relation 1845937
Sun May 27 20:25:36 2007  error -14 reading relation 1944811
Sun May 27 20:25:37 2007  error -14 reading relation 2033707
Sun May 27 20:25:37 2007  error -14 reading relation 2042483
Sun May 27 20:25:39 2007  error -14 reading relation 2166831
Sun May 27 20:25:39 2007  error -14 reading relation 2167315
Sun May 27 20:25:40 2007  error -14 reading relation 2243282
Sun May 27 20:25:40 2007  error -14 reading relation 2266643
Sun May 27 20:25:42 2007  error -14 reading relation 2454429
Sun May 27 20:25:42 2007  error -14 reading relation 2461537
Sun May 27 20:25:43 2007  error -14 reading relation 2529520
Sun May 27 20:25:44 2007  error -14 reading relation 2578890
Sun May 27 20:25:44 2007  error -14 reading relation 2654189
Sun May 27 20:25:45 2007  error -14 reading relation 2679930
Sun May 27 20:25:45 2007  error -14 reading relation 2731679
Sun May 27 20:25:46 2007  error -14 reading relation 2766503
Sun May 27 20:25:46 2007  error -14 reading relation 2789851
Sun May 27 20:25:46 2007  error -14 reading relation 2819985
Sun May 27 20:25:48 2007  error -14 reading relation 2928619
Sun May 27 20:25:49 2007  error -14 reading relation 3053936
Sun May 27 20:25:49 2007  error -14 reading relation 3071780
Sun May 27 20:25:49 2007  error -14 reading relation 3090392
Sun May 27 20:25:50 2007  error -14 reading relation 3142467
Sun May 27 20:25:52 2007  error -14 reading relation 3346153
Sun May 27 20:25:54 2007  error -14 reading relation 3461292
Sun May 27 20:25:54 2007  error -14 reading relation 3466881
Sun May 27 20:25:55 2007  error -14 reading relation 3546257
Sun May 27 20:25:57 2007  error -3 reading relation 3723754
Sun May 27 20:25:58 2007  error -14 reading relation 3803670
Sun May 27 20:25:58 2007  error -14 reading relation 3833701
Sun May 27 20:25:59 2007  error -14 reading relation 3949808
Sun May 27 20:26:00 2007  error -14 reading relation 3988410
Sun May 27 20:26:01 2007  found 30395 hash collisions in 4046227 relations
Sun May 27 20:26:01 2007  commencing duplicate removal, pass 2
Sun May 27 20:26:11 2007  found 0 duplicates and 4046227 unique relations
Sun May 27 20:26:11 2007  memory use: 36.9 MB
Sun May 27 20:26:13 2007  ignoring smallest 192370 rational and 192563 algebraic ideals
Sun May 27 20:26:13 2007  filtering rational ideals above 2637001
Sun May 27 20:26:13 2007  filtering algebraic ideals above 2637001
Sun May 27 20:26:13 2007  need 654386 more relations than ideals
Sun May 27 20:26:13 2007  commencing singleton removal, pass 1
Sun May 27 20:27:02 2007  relations with 0 large ideals: 75333
Sun May 27 20:27:02 2007  relations with 1 large ideals: 562834
Sun May 27 20:27:02 2007  relations with 2 large ideals: 1467911
Sun May 27 20:27:02 2007  relations with 3 large ideals: 1487681
Sun May 27 20:27:02 2007  relations with 4 large ideals: 452468
Sun May 27 20:27:02 2007  relations with 5 large ideals: 0
Sun May 27 20:27:02 2007  relations with 6 large ideals: 0
Sun May 27 20:27:02 2007  relations with 7+ large ideals: 0
Sun May 27 20:27:02 2007  4046227 relations and about 4127707 large ideals
Sun May 27 20:27:02 2007  commencing singleton removal, pass 2
Sun May 27 20:27:51 2007  found 1957308 singletons
Sun May 27 20:27:51 2007  current dataset: 2088919 relations and about 1773326 large ideals
Sun May 27 20:27:51 2007  commencing singleton removal, pass 3
Sun May 27 20:28:18 2007  found 449611 singletons
Sun May 27 20:28:18 2007  current dataset: 1639308 relations and about 1283469 large ideals
Sun May 27 20:28:18 2007  commencing singleton removal, pass 4
Sun May 27 20:28:41 2007  found 153521 singletons
Sun May 27 20:28:41 2007  current dataset: 1485787 relations and about 1124104 large ideals
Sun May 27 20:28:41 2007  commencing singleton removal, pass 5
Sun May 27 20:29:02 2007  found 58431 singletons
Sun May 27 20:29:02 2007  current dataset: 1427356 relations and about 1064746 large ideals
Sun May 27 20:29:02 2007  commencing singleton removal, final pass
Sun May 27 20:29:22 2007  memory use: 51.4 MB
Sun May 27 20:29:22 2007  commencing in-memory singleton removal
Sun May 27 20:29:22 2007  begin with 1427356 relations and 1095471 unique ideals
Sun May 27 20:29:24 2007  reduce to 1283849 relations and 950054 ideals in 14 passes
Sun May 27 20:29:24 2007  max relations containing the same ideal: 14
Sun May 27 20:29:24 2007  filtering wants 961773 more relations
Sun May 27 20:29:24 2007  factor base loaded:
Sun May 27 20:29:24 2007  158623 rational ideals (max prime = 2140907)
Sun May 27 20:29:24 2007  158670 algebraic ideals (max prime = 2140877)
Sun May 27 20:29:24 2007  a range: [-6727274, 6727273]
Sun May 27 20:29:24 2007  b range: [638447, 4294967295]
Sun May 27 20:29:24 2007  number of hash buckets: 33
Sun May 27 20:29:24 2007  sieve block size: 65536
Sun May 27 20:29:24 2007  
Sun May 27 20:29:24 2007  maximum RFB prime: 2140907
Sun May 27 20:29:24 2007  RFB entries: 158623
Sun May 27 20:29:24 2007  medium RFB entries: 6542
Sun May 27 20:29:24 2007  resieved RFB entries: 6374
Sun May 27 20:29:24 2007  small RFB prime powers: 28
Sun May 27 20:29:24 2007  projective RFB roots: 0
Sun May 27 20:29:24 2007  RFB trial factoring cutoff: 55 bits
Sun May 27 20:29:24 2007  single large prime RFB range: 21 - 26 bits
Sun May 27 20:29:24 2007  double large prime RFB range: 43 - 50 bits
Sun May 27 20:29:24 2007  
Sun May 27 20:29:24 2007  maximum AFB prime: 2140877
Sun May 27 20:29:24 2007  AFB entries: 158670
Sun May 27 20:29:24 2007  medium AFB entries: 6534
Sun May 27 20:29:24 2007  resieved AFB entries: 6339
Sun May 27 20:29:24 2007  small AFB prime powers: 43
Sun May 27 20:29:24 2007  projective AFB roots: 8
Sun May 27 20:29:24 2007  AFB trial factoring cutoff: 55 bits
Sun May 27 20:29:24 2007  single large prime AFB range: 21 - 26 bits
Sun May 27 20:29:24 2007  double large prime AFB range: 43 - 50 bits
Sun May 27 20:29:24 2007

edit: my run on a c103 which has been started with 1.22alpha does not show such errors, but some of the "bad" relations with the c101 have been found with 1.22alpha.

P.S.: I don't know if it's possible to send you the relations in any way - even if compressed as a .rar file at maximum compression rate the file is approx. 158 MB, and this would take loooooong to upload (even if I had a webspace to upload it).