mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2023-01-02, 00:41   #12
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

260410 Posts
Default

Quote:
Originally Posted by charybdis View Post
Getting errors during compilation with gcc 9.4.0:[/code]
I've not seen that before. But there's no reason payload needs to be a bitfield since it now uses 32 bits of a 64-bit integer. Just make it uint32. And might as well get rid of the bitfield entirely.

Code:
diff --git a/common/filter/filter_priv.h b/common/filter/filter_priv.h
index 2e2722a..8358bd7 100644
--- a/common/filter/filter_priv.h
+++ b/common/filter/filter_priv.h
@@ -39,12 +39,12 @@ typedef struct {
    linked list of relations that use that ideal */

 typedef struct {
-       uint64 payload : 32;    /* offset in list of ideal_relation_t
+       uint32 payload; /* offset in list of ideal_relation_t
                                   structures where the linked list of
                                   ideal_relation_t's for this ideal starts */
-       uint64 clique : 1;      /* nonzero if this ideal can participate in
+       uint8 clique;      /* nonzero if this ideal can participate in
                                   a clique */
-       uint64 connected : 1;   /* nonzero if this ideal has already been
+       uint8 connected;   /* nonzero if this ideal has already been
                                   added to a clique under construction */
 } ideal_map_t;
*Code has not been tested.
frmky is offline   Reply With Quote
Old 2023-01-02, 02:47   #13
charybdis
 
charybdis's Avatar
 
Apr 2020

92910 Posts
Default

Quote:
Originally Posted by frmky View Post
I've not seen that before. But there's no reason payload needs to be a bitfield since it now uses 32 bits of a 64-bit integer. Just make it uint32. And might as well get rid of the bitfield entirely.

...

*Code has not been tested.
Thank you! Filtering runs smoothly on the data from the benchmark thread. It's nice to see the relations being read so much faster at the start
charybdis is offline   Reply With Quote
Old 2023-01-05, 18:14   #14
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

I think this was a side effect of the changes to fix the large dataset bug; the original structure had a 30-bit entry for the first bitfield and large clique removal problems were overflowing 30 bits.
jasonp is online now   Reply With Quote
Old 2023-01-05, 19:14   #15
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

1010001011002 Posts
Default

Exactly. I changed it to use 32 bits for payload but just left it as a bitfield at the time.

BTW I just ran into a problem with duplicate removal on a large data set (> 3.5 billion relations). I'll attempt to track it down later today...

Code:
Msieve v. 1.54 (SVN Unversioned directory)
Wed Jan  4 21:07:40 2023
random seeds: 8843eb30 0eaf6dcd
MPI process 0 of 1
Using 32 OpenMP threads
factoring 4253349343727251941236877330119054101365914162453902893114846114910830524926133972442672109384930997010015571127515364573577614552367729063797097718571593825921640272454441835184315923713781601800465188651975108402186204817922305008709852043792965744682561465375915998120986746272975079603698798568632913 (304 digits)
no P-1/P+1/ECM available, skipping
commencing number field sieve (304-digit input)
R0: -12259964326927110866866776217202473468949912977468817408
R1: 1
A0: 2
A1: 0
A2: 0
A3: -2
A4: 0
A5: 0
A6: 1
skew 1.54, size 3.668e-16, alpha 2.178, combined = 2.345e-16 rroots = 0

commencing relation filtering
setting target matrix density to 130.0
estimated available RAM is 257753.8 MB
commencing duplicate removal, pass 1
skipped 4902752 relations with b > 2^32
skipped 4 relations with composite factors
skipped 22985 malformed relations
found 1242193459 hash collisions in 3517393380 relations
added 1218925 free relations
commencing duplicate removal, pass 2
[kepler-0-1:11718] *** Process received signal ***
[kepler-0-1:11718] Signal: Segmentation fault (11)
[kepler-0-1:11718] Signal code: Address not mapped (1)
[kepler-0-1:11718] Failing at address: 0x7f706418be3c
[kepler-0-1:11718] [ 0] /lib64/libpthread.so.0(+0xf5e0)[0x7f7b769c75e0]
[kepler-0-1:11718] [ 1] ./msieve[0x44dac7]
[kepler-0-1:11718] [ 2] ./msieve[0x462da4]
[kepler-0-1:11718] [ 3] ./msieve[0x428675]
[kepler-0-1:11718] [ 4] ./msieve[0x4162ad]
[kepler-0-1:11718] [ 5] ./msieve[0x4061d0]
[kepler-0-1:11718] [ 6] ./msieve[0x404b7d]
[kepler-0-1:11718] [ 7] ./msieve[0x404730]
[kepler-0-1:11718] [ 8] /lib64/libc.so.6(__libc_start_main+0xf5)[0x7f7b760f3c05]
[kepler-0-1:11718] [ 9] ./msieve[0x4047ca]
[kepler-0-1:11718] *** End of error message ***
frmky is offline   Reply With Quote
Old 2023-01-06, 05:14   #16
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22×3×7×31 Posts
Default

Quote:
Originally Posted by frmky View Post
Code:
found 1242193459 hash collisions in 3517393380 relations
I haven't had a chance to dig into the code yet, but my first suspicion is that the problem is related to 1242193459*sizeof(uint32) > 2^32.
frmky is offline   Reply With Quote
Old 2023-01-06, 14:39   #17
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

DE316 Posts
Default

There are going to be more and more of these failures as problems approach 4 billion relations. Maybe there would be a bigger payoff investing in making msieve postprocessing interoperable with CADO postprocessing :)

In this case the hashtable code that is used should have a linked list of hashtable offsets and not byte offsets for resolving collisions, but nobody should rely on my memory from 2007.
jasonp is online now   Reply With Quote
Old 2023-01-07, 01:03   #18
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22×3×7×31 Posts
Default

Yes, it looks like hashtable.c needs a bit of a rewrite. But fundamentally this crash is just a symptom. The real (and easier to patch) problem is that the pass 1 hashtable is too small, which leads to far too many collisions. I'm testing changes now.

As Jason's comment in the source suggests, a better fix would be to replace it with a Bloom filter. And I would argue for sizing the filter a bit larger, discarding the second pass, and just throwing away relations that collide. It wouldn't be difficult to adjust the filter to get negligible collisions.

CADO polyselect and filtering + msieve GPU BL and sqrt would definitely be the best of both worlds. The very different architecture for keeping track of relations suggests this might be difficult to implement, but I do think it would be worth the effort.
frmky is offline   Reply With Quote
Old 2023-01-07, 04:03   #19
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

A different idea was explored in another corner of the svn repo, using Berekeley DB. This is straightforward for the duplicate removal, using BDB to implement an out-of-core sort on relation coordinates. Similar techniques apply to the first pass of the singleton removal but gaining a speedup over using a hashtable is much harder.
jasonp is online now   Reply With Quote
Old 2023-01-07, 17:56   #20
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22×3×7×31 Posts
Default

Quote:
Originally Posted by frmky View Post
Yes, it looks like hashtable.c needs a bit of a rewrite. But fundamentally this crash is just a symptom. The real (and easier to patch) problem is that the pass 1 hashtable is too small, which leads to far too many collisions. I'm testing changes now.
Increasing the pass 1 hashtable in duplicate removal circumvented the crash in pass 2, but it just reappeared in singleton removal initial pass. So, in the short term, hashtable.c does need to be fixed. For now, though, I've just done duplicate removal and a couple rounds of singleton removal to reduce the dataset before starting msieve.

I'll look into the msieve-db code soon, but I'm afraid I also have little time these days for tool development.
frmky is offline   Reply With Quote
Old 2023-01-22, 04:44   #21
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22·3·7·31 Posts
Default

Quote:
Originally Posted by frmky View Post
BTW I just ran into a problem with duplicate removal on a large data set (> 3.5 billion relations). I'll attempt to track it down later today...
I finally had time to look at this yesterday. Simple overflow in the hashtable match array reallocation size. Easy fix, and it only affects runs with more than 3,276,800,000 relations.
https://github.com/gchilders/msieve_...833d28370a2948
frmky is offline   Reply With Quote
Old 2023-01-27, 03:44   #22
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Quote:
Originally Posted by frmky View Post
I finally had time to look at this yesterday. Simple overflow in the hashtable match array reallocation size. Easy fix, and it only affects runs with more than 3,276,800,000 relations.
https://github.com/gchilders/msieve_...833d28370a2948
Thanks! Does this mean the duplicate removal is limited to 3.2 billion unique relations?
jasonp is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
msieve with GMP 6.2.0 ryanp Msieve 2 2020-06-16 20:36
GMP-ECM with --enable-openmp flag set in configure = bad results? GP2 GMP-ECM 3 2016-10-16 10:21
Msieve on a Mac (Help) pxp Msieve 1 2013-02-28 14:56
OpenMP R. Gerbicz Programming 13 2011-09-22 01:11
msieve help em99010pepe Msieve 23 2009-09-27 16:13

All times are UTC. The time now is 13:58.


Wed Feb 8 13:58:05 UTC 2023 up 174 days, 11:26, 1 user, load averages: 0.62, 0.80, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔