Help me finish this c/8 search

For discussion of specific patterns or specific families of patterns, both newly-discovered and well-known.
Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Help me finish this c/8 search

Post by Sokwe » January 13th, 2020, 7:24 am

Andrew J. Wade's new program is making other spaceship searchers obsolete in many respects, but here's something that might still be reasonable to finish with qfind.

I am trying to complete the (1,0)c/8 width-19 symmetric spaceship search with qfind. I did a preliminary search a while back, but realized it would take too long to complete on a single computer. To finish it I decided to split the current search state into 168 pieces that can be run separately. I'm hoping others can run parts of the search on their computers.

How to help:
  1. Download and extract this zip file:
    c8-w19-search.zip
    (132.72 KiB) Downloaded 23 times
  2. Compile qfind-c8.cpp using OpenMP. For example, I compile with

    Code: Select all

    g++ qfind-c8.cpp -O3 -fopenmp -march=native -o qfind-c8
  3. Claim a piece of the search by editing the table on this wiki page. If you don't have a wiki account, post which pieces you are claiming in this thread. Hopefully I or someone else will add them to the wiki table fairly quickly.
  4. Run the search on the specified piece with a specified number of threads. For example, if you claimed piece 0001 and want to run with 3 threads, then run

    Code: Select all

    ./qfind-c8 piece0001 t3 > output0001
    This will send the output to the file "output0001".
  5. When the search completes it will create a report file, "reportNNNN" where NNNN is the piece number, which gives the longest partial result. Go to the table, click the red link for the report, and create the page with the contents pasted from the report file on your computer.
  6. If the search finds a ship, it will print it and save it to the file "ship0001". Further ships will be saved to "ship0002", "ship0003", etc. Post any ships that get found to this thread.
Please do not edit any of the provided files.

A few things to note:
  • The search uses about 2.4 gigabytes of RAM. If you don't have this much RAM available you simply won't be able to run the search.
  • I haven't actually finished a single search yet. I ran some tests using 7 threads on an 8-core machine, and I think that under these conditions the shortest searches will take about 4 or 5 hours. Some searches may take days or weeks. We might have to split some of them again to get this project done.
  • As a search runs, dump files will be created in the pieces folder called "dumpMMMM-NNNN" where MMMM is the piece number and NNNN is the dump number. If a search gets killed early it can be restarted from the latest dump file. For example, you may need to run

    Code: Select all

    ./qfind-c8 dump0001-0017 t3 > output0001-continued
    Note that you need to respecify the number of threads when continuing a search from a dump file.
  • Sometimes a file called "pushNNNN" will be created where NNNN is the piece number. This will contain partial results that are "potential pushalongs". For the most part they will be uninteresting, so don't worry about them too much. It won't be clear what front end they are a pushalong for, so another search would have to be run to determine that. These probably won't be useful for anything, but I wanted to save them anyway, just in case.
There is certainly no guarantee that a ship exists at this width, but we won't know until we try. If all of the searches complete without finding anything, this should prove that no width-19 symmetric (1,0)c/8 ships exist.

Technical note:
I did not change gind3 to an array of type std::atomic_uintptr_t as suggested in this post, because I'm not sure how to do it correctly. If anyone more knowledgable could explain it, I would appreciate it.
-Matthias Merzenich

User avatar
testitemqlstudop
Posts: 1276
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: Help me finish this c/8 search

Post by testitemqlstudop » January 13th, 2020, 8:32 am

Please compile with the optimizations

Code: Select all

g++ qfind-c8.cpp -O3 -Ofast -flto -march=native -fopenmp -march=native -o qfind-c8

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 13th, 2020, 12:24 pm

testitemqlstudop wrote:
January 13th, 2020, 8:32 am
Please compile with the optimizations

Code: Select all

g++ qfind-c8.cpp -O3 -Ofast -flto -march=native -fopenmp -march=native -o qfind-c8
This worked for me using Cygwin64 on Windows 10, on a laptop with an Intel(R) Core(TM) i5-7440HQ chip.

I got a -bash: qfind-c8: command not found when following the exact instructions in the first post, but it seemed to work fine with the command line modified to

Code: Select all

./qfind-c8 piece0100 t3 > output0100
(I'm trying a 3-thread run for the first piece that I signed up for, #100; will update this post with how long it took to complete. qfind-c8.exe seems to be using 75% of my CPU, with other tasks occasionally spiking total usage up to 99% but it seems very manageable so far. If performance on other tasks suffers I'll try a 2-thread run next.)

John Goodman
Posts: 16
Joined: December 13th, 2019, 10:00 am

Re: Help me finish this c/8 search

Post by John Goodman » January 13th, 2020, 1:46 pm

Would be happy to do some pieces if someone can figure out how to build this on macOS Mojave (Apple's Clang does not support fopenmp, and I got other errors after using homebrew to install either llvm or gcc).

EDIT: Got it to compile by using homebrew to install libomp and then using clang++

But then when I ran it (used piece0043) I got:

qfind-c8(24278,0x700041b4000) malloc: *** error for object 0x7fb9e54000a0: pointer being freed was not allocated
qfind-c8(24278,0x700041b4000) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6

hkoenig
Posts: 110
Joined: June 20th, 2009, 11:40 am

Re: Help me finish this c/8 search

Post by hkoenig » January 13th, 2020, 2:07 pm

You'd need to create an XCode CommandLine project with the sourcecode, then replace the Open_MP calls with GCD calls. Several years ago I hacked up apgnano that way, and it was only changed in about two places.

For the hell of it, I just built that project and ran it, and it appears to have worked and submitted the runs properly (found a Pentadecatlon and a yl144_1_16_afb5f3db909e60548f086e22ee3353ac).

Here's the project. Look for #ifdef MACOSX in main.cpp, which is defined in the project file "Apple Clang" >> "Other C Flags" >> "-DMACOSX=1"
Attachments
apgnanoMac.zip
(168.52 KiB) Downloaded 1 time
Last edited by hkoenig on January 13th, 2020, 2:22 pm, edited 1 time in total.

User avatar
rowett
Moderator
Posts: 1919
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Help me finish this c/8 search

Post by rowett » January 13th, 2020, 2:13 pm

I got a crash on 64bit Ubuntu Linux running piece0167:

Code: Select all

% ./qfind-c8 piece0167 t4 > output0167
*** Error in `./qfind-c8': double free or corruption (!prev): 0x00007f38e8000bb0 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f398bcc27e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7f398bccb37a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f398bccf53c]
./qfind-c8[0x4054eb]
./qfind-c8[0x4073e3]
/usr/lib/x86_64-linux-gnu/libgomp.so.1(+0x1a436)[0x7f398b64b436]
/lib/x86_64-linux-gnu/libpthread.so.0(+0x76ba)[0x7f398acf66ba]
/lib/x86_64-linux-gnu/libc.so.6(clone+0x6d)[0x7f398bd5241d]
======= Memory map: ========
00400000-00409000 r-xp 00000000 08:01 2111384                            /home/chris/c8-w19-search/qfind-c8
00608000-00609000 r--p 00008000 08:01 2111384                            /home/chris/c8-w19-search/qfind-c8
00609000-0060a000 rw-p 00009000 08:01 2111384                            /home/chris/c8-w19-search/qfind-c8
0060a000-0060d000 rw-p 00000000 00:00 0 
01ce2000-01d24000 rw-p 00000000 00:00 0                                  [heap]
7f38e79fd000-7f38e8000000 rw-p 00000000 00:00 0 
7f38e8000000-7f38e8021000 rw-p 00000000 00:00 0 
7f38e8021000-7f38ec000000 ---p 00000000 00:00 0 
7f38ec000000-7f38ec021000 rw-p 00000000 00:00 0 
7f38ec021000-7f38f0000000 ---p 00000000 00:00 0 
7f38f0000000-7f38f0021000 rw-p 00000000 00:00 0 
7f38f0021000-7f38f4000000 ---p 00000000 00:00 0 
7f38f4156000-7f38f696a000 rw-p 00000000 00:00 0 
7f38f696a000-7f38f696b000 ---p 00000000 00:00 0 
7f38f696b000-7f38f716b000 rw-p 00000000 00:00 0 
7f38f716b000-7f38f716c000 ---p 00000000 00:00 0 
7f38f716c000-7f38f796c000 rw-p 00000000 00:00 0 
7f38f796c000-7f38f796d000 ---p 00000000 00:00 0 
7f38f796d000-7f398acef000 rw-p 00000000 00:00 0 
7f398acef000-7f398ad07000 r-xp 00000000 08:01 935503                     /lib/x86_64-linux-gnu/libpthread-2.23.so
7f398ad07000-7f398af06000 ---p 00018000 08:01 935503                     /lib/x86_64-linux-gnu/libpthread-2.23.so
7f398af06000-7f398af07000 r--p 00017000 08:01 935503                     /lib/x86_64-linux-gnu/libpthread-2.23.so
7f398af07000-7f398af08000 rw-p 00018000 08:01 935503                     /lib/x86_64-linux-gnu/libpthread-2.23.so
7f398af08000-7f398af0c000 rw-p 00000000 00:00 0 
7f398af0c000-7f398af0f000 r-xp 00000000 08:01 928718                     /lib/x86_64-linux-gnu/libdl-2.23.so
7f398af0f000-7f398b10e000 ---p 00003000 08:01 928718                     /lib/x86_64-linux-gnu/libdl-2.23.so
7f398b10e000-7f398b10f000 r--p 00002000 08:01 928718                     /lib/x86_64-linux-gnu/libdl-2.23.so
7f398b10f000-7f398b110000 rw-p 00003000 08:01 928718                     /lib/x86_64-linux-gnu/libdl-2.23.so
7f398b110000-7f398b127000 r-xp 00000000 08:01 917781                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7f398b127000-7f398b326000 ---p 00017000 08:01 917781                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7f398b326000-7f398b327000 r--p 00016000 08:01 917781                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7f398b327000-7f398b328000 rw-p 00017000 08:01 917781                     /lib/x86_64-linux-gnu/libgcc_s.so.1
7f398b328000-7f398b430000 r-xp 00000000 08:01 935523                     /lib/x86_64-linux-gnu/libm-2.23.so
7f398b430000-7f398b62f000 ---p 00108000 08:01 935523                     /lib/x86_64-linux-gnu/libm-2.23.so
7f398b62f000-7f398b630000 r--p 00107000 08:01 935523                     /lib/x86_64-linux-gnu/libm-2.23.so
7f398b630000-7f398b631000 rw-p 00108000 08:01 935523                     /lib/x86_64-linux-gnu/libm-2.23.so
7f398b631000-7f398b667000 r-xp 00000000 08:01 1835400                    /usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0
7f398b667000-7f398b866000 ---p 00036000 08:01 1835400                    /usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0
7f398b866000-7f398b867000 r--p 00035000 08:01 1835400                    /usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0
7f398b867000-7f398b868000 rw-p 00036000 08:01 1835400                    /usr/lib/x86_64-linux-gnu/libgomp.so.1.0.0
7f398b868000-7f398ba3b000 r-xp 00000000 08:01 1836368                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7f398ba3b000-7f398bc3a000 ---p 001d3000 08:01 1836368                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7f398bc3a000-7f398bc45000 r--p 001d2000 08:01 1836368                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7f398bc45000-7f398bc48000 rw-p 001dd000 08:01 1836368                    /usr/lib/x86_64-linux-gnu/libstdc++.so.6.0.28
7f398bc48000-7f398bc4b000 rw-p 00000000 00:00 0 
7f398bc4b000-7f398be0b000 r-xp 00000000 08:01 935520                     /lib/x86_64-linux-gnu/libc-2.23.so
7f398be0b000-7f398c00b000 ---p 001c0000 08:01 935520                     /lib/x86_64-linux-gnu/libc-2.23.so
7f398c00b000-7f398c00f000 r--p 001c0000 08:01 935520                     /lib/x86_64-linux-gnu/libc-2.23.so
7f398c00f000-7f398c011000 rw-p 001c4000 08:01 935520                     /lib/x86_64-linux-gnu/libc-2.23.so
7f398c011000-7f398c015000 rw-p 00000000 00:00 0 
7f398c015000-7f398c03b000 r-xp 00000000 08:01 931829                     /lib/x86_64-linux-gnu/ld-2.23.so
7f398c11a000-7f398c223000 rw-p 00000000 00:00 0 
7f398c239000-7f398c23a000 rw-p 00000000 00:00 0 
7f398c23a000-7f398c23b000 r--p 00025000 08:01 931829                     /lib/x86_64-linux-gnu/ld-2.23.so
7f398c23b000-7f398c23c000 rw-p 00026000 08:01 931829                     /lib/x86_64-linux-gnu/ld-2.23.so
7f398c23c000-7f398c23d000 rw-p 00000000 00:00 0 
7ffdc8bf7000-7ffdc8c18000 rw-p 00000000 00:00 0                          [stack]
7ffdc8d5c000-7ffdc8d5e000 r--p 00000000 00:00 0                          [vvar]
7ffdc8d5e000-7ffdc8d60000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]
Aborted (core dumped)
Before the crash it had created 8 dump files so I continued from the latest one:

Code: Select all

% ./qfind-c8 dump0167-0008 t4 > output0167-continue
That then crashed with the same error as above after it got to dump0167-0011.

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 13th, 2020, 3:58 pm

John Goodman wrote:
January 13th, 2020, 1:46 pm
when I ran it (used piece0043) I got:

qfind-c8(24278,0x700041b4000) malloc: *** error for object 0x7fb9e54000a0: pointer being freed was not allocated
rowett wrote:
January 13th, 2020, 2:13 pm
I got a crash on 64bit Ubuntu Linux running piece0167:

Code: Select all

...
*** Error in `./qfind-c8': double free or corruption (!prev): 0x00007f38e8000bb0 ***\
...
Before the crash it had created 8 dump files so I continued from the latest one:

Code: Select all

% ./qfind-c8 dump0167-0008 t4 > output0167-continue
That then crashed with the same error as above after it got to dump0167-0011.
I'm going to guess that this is the same error. It looks like it has to do with lines 950, 951, 955, and 956. Admittedly, this is part of the code I simply copied from gfind.

It appears that the program allocates memory for arrays srows and ssrows at lines 845 and 846, and then creates static pointers drows and ddrows and sets them equal to srows and ssrows respectively. This "saves" the pointer locations, because srows and ssrows get changed at lines 902 and 903. However, it tries to free drows and ddrows (and later olddrows and oldddrows) instead of srows or ssrows. I'll have to fix this, probably by copying code from Paul Tooke's modification to gfind. I can't do it right now, unfortunately.
-Matthias Merzenich

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 13th, 2020, 5:59 pm

I've made an update to the code in the zip file in the first post that I hope will fix this bug. For those of you who were experiencing the crash, please test this new version with piece0167. This piece is smaller than the others, so it should run fairly quickly. If you get to dump0167-0010 without a crash, then I think that means it is working correctly. Please post to say whether that fixed the problem.

For those using the old version, please update to the new version. You can copy your dump files to the new pieces folder and continue the search from your latest dump.

If you run piece0167 to completion you should get the following in your report:

Code: Select all

#C Search 0167 complete.
#C 0 spaceships found.
#C Longest partial:
x = 19, y = 36, rule = B3/S23
4bo9bo$ob3obo5bob3obo$bob2o2bo3bo2b2obo$bo5bo3bo5bo$6b7o$3bobob
obobobobo$2b4o2bobo2b4o$b2o13b2o$b2o13b2o$2ob4o5b4ob2o$o5b2o3b2o
5bo$bo2bob2o3b2obo2bo$2bobo3bobo3bobo$4b5ob5o$2b3o2bo3bo2b3o$2b3o
9b3o$2bo2b2o5b2o2bo$3b4o5b4o$3bo2bo5bo2bo$4b3o5b3o$4bo2bo3bo2bo$
6b2o3b2o$8bobo$5bo3bo3bo$5bo2bobo2bo$3b2obo5bob2o$3b2o2bo3bo2b2o
$3b2o9b2o$7b2ob2o$3b3o3bo3b3o$4bo9bo3$8b3o$9bo$9bo!

testitemqlstudop wrote:
January 13th, 2020, 8:32 am
Please compile with the optimizations

Code: Select all

g++ qfind-c8.cpp -O3 -Ofast -flto -march=native -fopenmp -march=native -o qfind-c8
Are there any potential issues with compiling using the flags -Ofast and -flto? I'm hardly an expert in this area.
-Matthias Merzenich

John Goodman
Posts: 16
Joined: December 13th, 2019, 10:00 am

Re: Help me finish this c/8 search

Post by John Goodman » January 13th, 2020, 6:18 pm

Seems to have fixed things -- I'm up to dump0167-0018 without a crash.

EDIT: Spoke too soon.

At dump0167-0032, another crash:
qfind-c8(24862,0x7000033c5000) malloc: Incorrect checksum for freed object 0x7fec06400140: probably modified after being freed.
Corrupt value: 0x0
qfind-c8(24862,0x7000033c5000) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 13th, 2020, 6:24 pm

John Goodman wrote:
January 13th, 2020, 6:18 pm
Seems to have fixed things -- I'm up to dump0167-0018 without a crash.

EDIT: Spoke too soon.

At dump0167-0032, another crash:
qfind-c8(24862,0x7000033c5000) malloc: Incorrect checksum for freed object 0x7fec06400140: probably modified after being freed.
Corrupt value: 0x0
qfind-c8(24862,0x7000033c5000) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6
Thanks for the feedback. I'll take another look.
-Matthias Merzenich

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 13th, 2020, 6:27 pm

Sokwe wrote:
January 13th, 2020, 5:59 pm
For those using the old version, please update to the new version. You can copy your dump files to the new pieces folder and continue the search from your latest dump.
Seems to be working. I had a momentary scare when I ran

Code: Select all

./qfind-c8 dump100-0028 t3 > output0100-continued
and the search completed instantly with no error messages. But apparently that's what happens when it can't find the input file due to a typo. The correct invocation was

Code: Select all

./qfind-c8 dump0100-0028 t3 > output0100-continued
and it seems to have picked up where it left off.

... I guess there's probably another upgrade in my future now. But I'm not seeing any crashes so far, in any case, so maybe I'll just let this version run to completion.

John Goodman
Posts: 16
Joined: December 13th, 2019, 10:00 am

Re: Help me finish this c/8 search

Post by John Goodman » January 13th, 2020, 6:28 pm

Restarted it at dump0167-0032 and (after five more dumps) it successfully generated the report (which matched yours).

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 13th, 2020, 6:46 pm

@John Goodman
Try it with this code for qfind-c8.cpp:

Edit: deleted; see zip file for current version.

I don't think this will fix it, but I have to go, so I don't have anything else I can try at the moment. Test it again with piece0167.
-Matthias Merzenich

John Goodman
Posts: 16
Joined: December 13th, 2019, 10:00 am

Re: Help me finish this c/8 search

Post by John Goodman » January 13th, 2020, 7:30 pm

piece0167 completed successfully with that version.

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 13th, 2020, 11:46 pm

What should we do with "push" components when they show up? I didn't get any of those in piece #100, but one has showed up already for piece #101, and a couple other "potential pushalongs" have gotten posted to Discord.

They do seem fairly useless, as the first post suggested.

Mine (push0101):

Code: Select all

x = 15, y = 6, rule = B3/S23
2ob2obobob2ob2o$bob2obobob2obo$2b3obobob3o$3bo2bobo2bo$6bobo$4b
2o3b2o!
Freywa's (presumably push0002):

Code: Select all

x = 5, y = 5, rule = B3/S23
bobo$2ob2o$b3o2$b3o!
matthew's (I think that's what this is, it wasn't labeled but it was right after Freywa's) (push0137):

Code: Select all

x = 13, y = 6, rule = B3/S23
o11bo$2b2o5b2o$bo9bo$bo2bo3bo2bo$2bo2bobo2bo$4bo3bo!
dani's (push0138) (warning: contains snakes):

Code: Select all

x = 19, y = 5, rule = B3/S23
5b2obobob2o$5bob2ob2obo2$2ob3o7b3ob2o$2ob3o7b3ob2o!
I'd like to see which front end can push that last one.

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 14th, 2020, 1:03 am

John Goodman wrote:
January 13th, 2020, 7:30 pm
piece0167 completed successfully with that version.
To clarify, did you restart piece0167 from the beginning using the new version? I'll be honest, I didn't expect that to work. However, I don't think the small change I made could make things worse, so I put it in the zip file.

I recommend that everyone update to the latest version which is in the zip file. However, if you haven't had a problem yet, I can't imagine you will start having one now. None of the bugs seem to affect the main search, nor would they have suppressed the output of a spaceship (it would crash first).
dvgrn wrote:
January 13th, 2020, 11:46 pm
What should we do with "push" components when they show up?
Probably nothing. The "frontends" file contains the full search tree that I split into pieces. As the search runs, it checks each added row to see that it didn't already occur as part of one of these front ends. If it has occured, that row is discarded, but not before the piece is printed to the push file. In most cases these are useless. Most probably aren't even proper "pushalongs". They could match with any of the first six rows (in all phases) of one of the front ends. All of this is simply to prevent significant overlap between two different piece searches. As I said, I'm printing them "just in case", but I have no good way of analyzing them.
dvgrn wrote:
January 13th, 2020, 6:27 pm
I had a momentary scare...
Surely nothing compared to the full-minute scare I had just now. I thought I had made a typo that would invalidate all results so far. Fortunately, the "typo" was actually the correct thing to do, and I had just forgotten why I had to do things that way.

Edit: I just had the program crash on piece0020, but I restarted the search twice and even tried continuing from the last dump before the crash, but I can't seem to get it to crash again. I still think all the crashes so far have been due to the pattern outputs. I don't think the actual search is being affected in any way. I'm not worried about missing ships. If the program crashes at the same moment it tries to print a ship (causing the ship not to be printed) then you will have to continue the search from the last dump, so it will just find the ship again.
-Matthias Merzenich

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 14th, 2020, 2:11 am

Some of these finish faster than my earlier minimum time estimate of 4 hours with 7 threads. piece0001 finished in 1.5 hours. If you are running these overnight, you may want to write a script that starts the next search after the previous one finishes. I don't have any example scripts; it's just a thought I had. Is anybody already doing something like this?
-Matthias Merzenich

User avatar
Hdjensofjfnen
Posts: 1436
Joined: March 15th, 2016, 6:41 pm
Location: r cis θ

Re: Help me finish this c/8 search

Post by Hdjensofjfnen » January 14th, 2020, 5:36 am

Going with 90 and 91 for now. My computer functionally speaking only has 3 threads available because it can't handle more without its CPU maxing out.
"A man said to the universe:
'Sir, I exist!'
'However,' replied the universe,
'The fact has not created in me
A sense of obligation.'" -Stephen Crane

Code: Select all

x = 7, y = 5, rule = B3/S2-i3-y4i
4b3o$6bo$o3b3o$2o$bo!

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 14th, 2020, 9:02 am

Sokwe wrote:
January 14th, 2020, 2:11 am
Some of these finish faster than my earlier minimum time estimate of 4 hours with 7 threads. piece0001 finished in 1.5 hours. If you are running these overnight, you may want to write a script that starts the next search after the previous one finishes. I don't have any example scripts; it's just a thought I had. Is anybody already doing something like this?
There seems to be quite a variety in completion times. Might my crackpot theory be correct that it's kind of good to get a longer completion time, because it might correlate with a longer partial and/or better odds of finding a complete spaceship? Or are the pieces just not necessarily the same size, so the odds are better only because a given piece happens to represent a larger percentage of the search space?

I can probably cobble together a Python script or some such that reads a list of pieces from a queue, and starts the next piece as soon as it sees the report file from the last piece in the root folder.

User avatar
rowett
Moderator
Posts: 1919
Joined: January 31st, 2013, 2:34 am
Location: UK
Contact:

Re: Help me finish this c/8 search

Post by rowett » January 14th, 2020, 9:38 am

I switched to Cygwin64 on Windows 10 and have had no more crashes. I'm running it on two desktop machines: One has an i5 quad core and the other an i7 quad core hyperthreaded. I'm running four threads on both. The quad core is at 100% cpu and the quad core HT at 57%.

wildmyron
Posts: 1329
Joined: August 9th, 2013, 12:45 am

Re: Help me finish this c/8 search

Post by wildmyron » January 14th, 2020, 12:04 pm

I've been looking for a project to use some compute time I have available. @Sokwe: Thanks for your ongoing work on qfind and for getting this project up and going. I've claimed a batch of pieces, but I'll be away for a while soon so it might take a while before I can update the table again.

Here's my script for processing pieces from a queue:

Create a file named "queue.txt" in the c8-w19-search directory. This file should have one piece name per line. E.g.

Code: Select all

piece0030
piece0031
Save this as a Python script in the same directory:

Code: Select all

#!/usr/bin/python3
import os
threads = 't4'
if not os.path.exists('outputs'):
        os.makedirs('outputs')
with open('queue.txt', 'r') as Fin:
    for line in Fin:
        piece = line.strip()
        if len(piece) < 9:
            break
        output = 'outputs/output' + piece[5:]
        print('Searching ' + piece)
        os.system('./qfind-c8 ' + piece + ' ' + threads + ' | tee ' + output)

Adjust "threads" to an appropriate value. If you don't wish to see the output in the console, replace ' | tee ' with ' > '. I've tested with a dummy program but haven't actually had it progress to the next piece in the queue, so hopefully it works correctly. My expectation is that it should be possible to add additional pieces to the end of the queue.txt file before the jobs all finish.
The latest version of the 5S Project contains over 226,000 spaceships. There is also a GitHub mirror of the collection. Tabulated pages up to period 160 (out of date) are available on the LifeWiki.

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 14th, 2020, 1:23 pm

wildmyron wrote:
January 14th, 2020, 12:04 pm
Here's my script for processing pieces from a queue:

Create a file named "queue.txt" in the c8-w19-search directory. This file should have one piece name per line.
Adjust "threads" to an appropriate value. If you don't wish to see the output in the console, replace ' | tee ' with ' > '. I've tested with a dummy program but haven't actually had it progress to the next piece in the queue, so hopefully it works correctly.
I tested it with actual calls to qfind, but with piece numbers that don't actually exist. It seems to work fine for me, under Cygwin on a Windows 10 system.

os.system is one of the older "execute-this" Python commands, unlike subprocess.run() which is Python 3.5+. Your code seems to work in either Python 2.7.x or Python 3.x without any changes needed.
wildmyron wrote:
January 14th, 2020, 12:04 pm
My expectation is that it should be possible to add additional pieces to the end of the queue.txt file before the jobs all finish.
I was surprised that that would work so simply, but it seems to -- I tried it with the same queue of dummy calls to qfind with bogus piece numbers, and was able to add a new piece number onto the end of the queue while the script was running through the earlier items. I thought you'd have to close and re-open the queue.txt file, and re-read past the previously processed lines.

Sokwe
Moderator
Posts: 1589
Joined: July 9th, 2009, 2:44 pm

Re: Help me finish this c/8 search

Post by Sokwe » January 14th, 2020, 11:23 pm

I worked carefully through the output printing code and found a few issues that could be the source of crashes. I have updated the zip file in the first post to fix these problems.

Please update to the latest version.

None of the problems had anything to do with the actual search. All saved dump files should be fine. Hopefully this is the last correction I will have to make.
dvgrn wrote:
January 14th, 2020, 9:02 am
Might my crackpot theory be correct that it's kind of good to get a longer completion time, because it might correlate with a longer partial and/or better odds of finding a complete spaceship?
This is probably correct. Each piece is indeed the same size (except piece 0167), so a slower search indicates more branching, which means more possibilities for spaceships. I don't want to get anyone's hopes too high, as spaceships get rarer with increasing period. However, if a spaceship is found, I expect it to be in one of these slow pieces. We may even need to split some of the slow pieces (or rather, the resulting dump files) to get them finished in a reasonable amount of time.
-Matthias Merzenich

User avatar
dvgrn
Moderator
Posts: 6154
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Help me finish this c/8 search

Post by dvgrn » January 15th, 2020, 1:56 pm

On Discord, wildmyron wrote:The piece(s) would be split from the latest dump which would allow the rest of the search for those pieces to be distributed. Seeing as there's so much of the rest of the search space still left it's probably not necessary yet. OTOH, i have a feelinv that gfind searches like this can progess more efficiently if the search parameters don't require deepening too far, and splitting up the search would help with that. However, I don't have any empirical evidence from my experience with gfind to actually back that up.
Sounds like several people have hit hard-to-search pieces by this time, though presumably a day or a week's worth of patience will eventually get them completed.

For the first few pieces, my system was able to handle doing the search in the background in 6-12 hours with no apparent strain. But now piece #0103 looks like it will take a full day or two.

I'm curious about wildmyron's theory about limited deepening being more efficient (assuming I'm understanding that right). I'm probably going to have fairly good data on difficulty for piece #103, since I've been able to run it nearly continuously, and the timestamps for all the dump files are available.* How exactly would piece #103 be split up into let's say ten sub-pieces? I could toss them into wildmyron's queue script, and after the full piece #103 completes, just see if it takes a significantly shorter time to search the ten sub-pieces.

* It would be nice to have the timestamps included in the output file, though. If another bugfix version comes along, maybe that could be added?

Pavgran
Posts: 14
Joined: June 12th, 2019, 12:14 pm

Re: Help me finish this c/8 search

Post by Pavgran » January 15th, 2020, 2:08 pm

dvgrn wrote:
January 15th, 2020, 1:56 pm
I could toss them into wildmyron's queue script
Python script is overkill for that.
Here is simple bash version:

Code: Select all

THREADS=4

while read piece
do
    echo Processing $piece
    ./qfind-c8 $piece t$THREADS > out_$piece
done <queue.txt

Post Reply