apgsearch v4.0

For general discussion about Conway's Game of Life.
User avatar
77topaz
Posts: 1366
Joined: January 12th, 2018, 9:19 pm

Re: apgsearch v4.0

Post by 77topaz » February 10th, 2019, 4:06 pm

testitemqlstudop wrote:On Linux (Lubuntu 18.10), when I run apgluxe (latest) either with "-p 0" or "-p 4", both don't respond to pressing "q".
Why would you even run "-p 0" in the first place? That's effectively telling it to parallelise over 0 cores, which seems like a pretty useless thing to do.

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 10th, 2019, 4:15 pm

"-p 0" actually tells it to disable parallelisation. (i.e. single-threaded run)

User avatar
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 10th, 2019, 4:19 pm

testitemqlstudop wrote:"-p 0" actually tells it to disable parallelisation. (i.e. single-threaded run)
-p 0 is the default, and on my Linux machine 'q' still works when parallelisation is disabled.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
77topaz
Posts: 1366
Joined: January 12th, 2018, 9:19 pm

Re: apgsearch v4.0

Post by 77topaz » February 10th, 2019, 5:02 pm

Oh, I see. But what would "-p 1" be, then? Wouldn't that be equivalent to not parallelising?

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 10th, 2019, 5:28 pm

Umm... I think "-p 1" activates parallelism (i.e. runs "threadSearch" and "partialSearch" instead of "runSearch" in searching.h), but only uses one instance of the function "partialSearch". (So pretty much useless.)

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

Re: apgsearch v4.0

Post by wildmyron » February 12th, 2019, 5:45 am

From the Scripts Request thread:
calcyman wrote:Another thing you can do nowadays, that seems to be under-utilised: if you write a program (in any language) which prints RLEs of glider syntheses, you can pipe it into apgsearch (compiled with a symmetry containing 'stdin' as a substring) and it will search those as 'soups' instead of 16x16 pseudorandom soups.
I used this feature of apgsearch to postprocess some results from a low period search I ran with ikpx (c/2 orthogonal). It works very nicely, but I presume that it didn't upload to catagolue because there were less than 10000 "soups". I presume if I had used the -c option of ikpx to pipe all partials to apgsearch then there would have been sufficient soups. The local log file was however sufficient for what I was interested in.

Considering your comments above, I thought I'd give this another go, so as a test I'm running a c/4d search in ikpx with the option "-c 'apgluxe-stdin_xq4_diag --symmetry stdin_xq4_diag -k <key> -n 10000'". This is just a trial out of curiousity, so I'm not expecting any particularly interesting results - but I am expecting a lot of gliders!
calcyman wrote:Everything else is unchanged, so it still uploads to Catagolue (and /hashsoup gives you back the original RLEs as intended). Here's an example:

https://catagolue.appspot.com/object/ov_q6/b3s23

I think there's a limit of 2000 characters per RLE, so you can't search huge soups in this manner, but it certainly gives you much more freedom than the regular symmetries (and accepts multistate RLEs). These RLEs are considered to begin with a line starting 'x' (as RLEs do, because they have a header line "x = ..., y = ...") and end with the next exclamation mark.
Do we have to be careful about the inclusion of RLEs in the haul leading to rather large haul sizes? I guess your Minstrel search submitting to Catagolue shows this is readily manageable, however in a search with many different objects I guess this might be an issue.

I've also considered some other search script possibilities which could utilise this feature of apgsearch. In some cases the number of RLE snippets to submit might not be large enough. Would it be reasonable to pad them out with sufficient empty patterns in order to make up the minimum haul size?

Edit: Whoops, I forgot to disable the testing flag so that's not being uploaded. I'll try again. Note to anyone else wanting to try this: when using stdin symmetry, add '-t 0' to the command line if you want to upload results to Catagolue
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
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 12th, 2019, 12:20 pm

wildmyron wrote:Considering your comments above, I thought I'd give this another go, so as a test I'm running a c/4d search in ikpx with the option "-c 'apgluxe-stdin_xq4_diag --symmetry stdin_xq4_diag -k <key> -n 10000'". This is just a trial out of curiousity, so I'm not expecting any particularly interesting results - but I am expecting a lot of gliders!
Thanks! It seems to be working, although separation isn't great when there's a nonstandard spaceship present. Ergo https://catagolue.appspot.com/object/xq ... z42e/b3s23

This actually gives me a good test-case to improve the separation in GoL and other rules.
Do we have to be careful about the inclusion of RLEs in the haul leading to rather large haul sizes? I guess your Minstrel search submitting to Catagolue shows this is readily manageable, however in a search with many different objects I guess this might be an issue.
The stdin symmetries only submit at most 1 sample soup per object, instead of 10.
Would it be reasonable to pad them out with sufficient empty patterns in order to make up the minimum haul size?
Absolutely, yes -- or maybe individual dying cells such as "x = 1, y = 1\no!\n" because I'm not sure whether empty patterns work in apgsearch.
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
danny
Posts: 969
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA
Contact:

Re: apgsearch v4.0

Post by danny » February 12th, 2019, 5:44 pm

calcyman wrote:Thanks! It seems to be working, although separation isn't great when there's a nonstandard spaceship present.
It seems to be a bit freakier than that. see- https://catagolue.appspot.com/census/b3 ... 4_diag/xq4
she/her // danielle

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D.

User avatar
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 12th, 2019, 9:13 pm

danny wrote:
calcyman wrote:Thanks! It seems to be working, although separation isn't great when there's a nonstandard spaceship present.
It seems to be a bit freakier than that. see- https://catagolue.appspot.com/census/b3 ... 4_diag/xq4
Isn't that simply a case of poor spaceship separation?
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: apgsearch v4.0

Post by wildmyron » February 13th, 2019, 3:33 am

calcyman wrote:
danny wrote:
calcyman wrote:Thanks! It seems to be working, although separation isn't great when there's a nonstandard spaceship present.
It seems to be a bit freakier than that. see- https://catagolue.appspot.com/census/b3 ... 4_diag/xq4
Isn't that simply a case of poor spaceship separation?
I believe that dani is referring to the clusters of 2, 3, and 4 gliders; e.g. http://catagolue.appspot.com/object/xq4_562gzx231/b3s23 and http://catagolue.appspot.com/object/xq4 ... z213/b3s23
I looked through the ten most common two glider flotilla and none of them have any sample soups outside of the stdin symmetry. It seems very unlikely to me that not one of them has ever emerged from a soup before, which I suspect means that escaping glider detection is not picking these gliders up - presumably because there's a larger ship leading the way in front and so these gliders aren't escaping on the boundary of the soup.
calcyman wrote:The stdin symmetries only submit at most 1 sample soup per object, instead of 10.
That seems to make it manageable. Also the limit you mentioned on RLE length only seems to apply to inclusion as a sample soup - apgluxe appears to be perfectly happy to run larger RLE soups. This means it is possible to run the following command in a directory containing pattern files (such as a subdirectory of the jslife-moving collection)

Code: Select all

cat *.rle | apgluxe --symmetry stdin -i 1
and get a nice list of apgcodes for all objects in the collection. (This doesn't work for all files in the collection such as a set of puffers or wickstretchers where some crash into the output of others, but aside from that it works really well.)

I added the "-i 1" option to the command because without some option other than the symmetry option apgluxe just prints "apgluxe v4.95-ll2.1.15: Symmetry stdin is correctly configured." and then exits. "-k <key>" or "-n 10000" work equally well.
calcyman wrote:
Would it be reasonable to pad them out with sufficient empty patterns in order to make up the minimum haul size?
Absolutely, yes -- or maybe individual dying cells such as "x = 1, y = 1\no!\n" because I'm not sure whether empty patterns work in apgsearch.
Thanks, from a quick test "x = 1, y = 1\nb!\n" appears to work equally well.
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
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 13th, 2019, 9:12 am

wildmyron wrote: I believe that dani is referring to the clusters of 2, 3, and 4 gliders; e.g. http://catagolue.appspot.com/object/xq4_562gzx231/b3s23 and http://catagolue.appspot.com/object/xq4 ... z213/b3s23
I looked through the ten most common two glider flotilla and none of them have any sample soups outside of the stdin symmetry. It seems very unlikely to me that not one of them has ever emerged from a soup before, which I suspect means that escaping glider detection is not picking these gliders up - presumably because there's a larger ship leading the way in front and so these gliders aren't escaping on the boundary of the soup.
The reason is that there's a function called sss() which separates standard spaceships -- so any cluster of gliders or *WSSes will be correctly separated into its constituents. But when there's a nonstandard spaceship in there, sss() doesn't work, so it falls back on the generic (not particularly good) spaceship separation code.

Having seen that mess, I made a modification recently to better handle these gliders. In particular, apgsearch now applies spaceship separation recursively in order to give sss() a second shot at splitting any pure-glider clusters that have been isolated.
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: apgsearch v4.0

Post by wildmyron » February 13th, 2019, 10:08 am

Ok. That sounds like it will help a bit - with the glider clusters in any case. I had a reasonable understanding of how object separation worked in apgsearch 1.0, but tbh I haven't looked at the corresponding C code at all.

I'll update the instance tomorrow when I have access to the machine again.
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
testitemqlstudop
Posts: 1234
Joined: July 21st, 2016, 11:45 am
Location: in catagolue
Contact:

Re: apgsearch v4.0

Post by testitemqlstudop » February 13th, 2019, 5:51 pm

Did you see my apgmera merge request

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

Re: apgsearch v4.0

Post by wildmyron » February 14th, 2019, 1:51 am

calcyman wrote:The reason is that there's a function called sss() which separates standard spaceships -- so any cluster of gliders or *WSSes will be correctly separated into its constituents. But when there's a nonstandard spaceship in there, sss() doesn't work, so it falls back on the generic (not particularly good) spaceship separation code.

Having seen that mess, I made a modification recently to better handle these gliders. In particular, apgsearch now applies spaceship separation recursively in order to give sss() a second shot at splitting any pure-glider clusters that have been isolated.
I restarted the ikpx search with an updated apgluxe. Unfortunately, it's going to be difficult to discern what I was hoping to find out from this search: how many of the small c/4 diagonal ships from the jslife-moving collection can be found with an ikpx search in a reasonable time (and can it find any new ones)? I've reduced the soup count per haul as several hauls were above the 1MB limit.

There's a similar trick that might be worth applying which will slightly improve the situation. Consider the following two RLE patterns which represent two different phases of the same cluster of c/4 ship plus gliders:

Code: Select all

x = 49, y = 37, rule = B3/S23
2o$obo$o3$b2o2bo$2o4bo$2b2obo2b3o$4b2o2b2obob2o$11bobobo$13bo$14bobo$
16bo$17bo$18bo11bo$18b3o8b2o$23bo5bobo$19bo2b2obo$19bob2obob2o$18b2obo
9bo$18bo2bo5bob4o$19bo9bo2bo2bo$23b3o8bobo$23bo$24bo10b2ob2o$35b2o3bo$
37b2o$40b2o2$36b2o$36bobo4b2o$36bo6bobo$43bo2$47b2o$46b2o$48bo!

Code: Select all

x = 50, y = 37, rule = B3/S23
b2o$2o$2bo3$b3o$bo2b4o2bo$2b3ob4obo$4b3o2bo2bob2o$11bo2bo$13b2obo$16bo
$16b3o$18bo$18b2o10b2o$19b2o9bobo$19bobob3o4bo$21b2o3b2o$20bobo2b3o$
19b2obo4b3o2b2o$19bo9b2o2bo$25bo3b2o2b2obo$24b2o10bo$24bobo10b2o$36b3o
bo$36bo$37b2ob3o3$37b2o$36b2o6b2o$38bo4b2o$45bo2$47b3o$47bo$48bo!
I ran "apgluxe --symmetry stdin -t 1" twice, once for each of the above "soups". For the first pattern the census contains a single object, but for the second pattern it separates two of the gliders.

If during the decomposition phase the object could be tested starting from each phase of its period, then in combination with the recursive separation there'd be a further improvement to separation, though lots of very closely spaced ships would still remain unseparated.

As an aside, in lifelib/classifier.h the first thing the pseudoBangBang function does is evolve the pattern in a history rule for period+2 generations. Why the +2? Are there objects which are incorrectly separated if they are evolved for only period generations?
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
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 14th, 2019, 4:23 am

testitemqlstudop wrote:Did you see my apgmera merge request
Yes -- great work! (Ideally, make sure you don't include Vim temporary files in there -- if you run 'git status' you can see what new files have appeared, and only 'git add' the file called searcher.h, not the temporary file .searcher.h.swp.)
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 14th, 2019, 4:28 pm

What happened? I'm seeing a 1200 soups/second slowdown at worst:

Code: Select all

./apgluxe -s l_kEwHfF3ArtPb -p 0 -v 0

Greetings, this is apgluxe v4.96-ll2.1.16, configured for b3s23/C1.

Lifelib version: ll2.1.16
Compiler version: 8.2.0
Python version: '2.7.15+ (default, Oct  2 2018, 22:12:08)  [GCC 8.2.0]'

Using seed l_kEwHfF3ArtPb
Instruction set AVX2 detected
Running 10000000 soups per haul:
b3s23/C1: 66222 soups completed (6622.200 soups/second current, 6622.200 overall).
Linear-growth pattern detected: yl144_1_16_afb5f3db909e60548f086e22ee3353ac
b3s23/C1: 137223 soups completed (7099.891 soups/second current, 6861.038 overall).
Linear-growth pattern detected: yl144_1_16_afb5f3db909e60548f086e22ee3353ac
b3s23/C1: 211427 soups completed (7420.304 soups/second current, 7047.456 overall).

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

Re: apgsearch v4.0

Post by Hdjensofjfnen » February 14th, 2019, 8:35 pm

testitemqlstudop wrote:What happened? I'm seeing a 1200 soups/second slowdown at worst:

Code: Select all

./apgluxe -s l_kEwHfF3ArtPb -p 0 -v 0

Greetings, this is apgluxe v4.96-ll2.1.16, configured for b3s23/C1.

Lifelib version: ll2.1.16
Compiler version: 8.2.0
Python version: '2.7.15+ (default, Oct  2 2018, 22:12:08)  [GCC 8.2.0]'

Using seed l_kEwHfF3ArtPb
Instruction set AVX2 detected
Running 10000000 soups per haul:
b3s23/C1: 66222 soups completed (6622.200 soups/second current, 6622.200 overall).
Linear-growth pattern detected: yl144_1_16_afb5f3db909e60548f086e22ee3353ac
b3s23/C1: 137223 soups completed (7099.891 soups/second current, 6861.038 overall).
Linear-growth pattern detected: yl144_1_16_afb5f3db909e60548f086e22ee3353ac
b3s23/C1: 211427 soups completed (7420.304 soups/second current, 7047.456 overall).
I don't know. Are you using a dated version of apgsearch?
EDIT: By the way, it might not be the best idea to openly post your payosha256.
"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
77topaz
Posts: 1366
Joined: January 12th, 2018, 9:19 pm

Re: apgsearch v4.0

Post by 77topaz » February 14th, 2019, 9:24 pm

Hdjensofjfnen wrote:I don't know. Are you using a dated version of apgsearch?
EDIT: By the way, it might not be the best idea to openly post your payosha256.
:face_palm:

You can see exactly what version of apgsearch he's using in the quote he posted, v4.96-ll2.1.16, the newest version. And since he's been contributing to the updating of apgsearch, it's a bit silly to think he would be using an old version.

Also, his payosha key isn't even in that message. Not that, if it was, you'd be able to do anything other than submit soups in his name.

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 14th, 2019, 9:44 pm

Technically you can overwite someone's payosha256 with your name and they won't know.

User avatar
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 14th, 2019, 10:59 pm

testitemqlstudop wrote:What happened? I'm seeing a 1200 soups/second slowdown at worst:
  • Try rerunning it and see if you get the same behaviour. (If not, it might be another process on your machine, or CPU throttling, or suchlike.)
  • Try recompiling with and without the --profile and see whether the behaviour persists. (If not, it could be an unhelpful optimisation generated in the profiling stage.)
If the problem persists, let me know which commit is faster.
What do you do with ill crystallographers? Take them to the mono-clinic!

ZoG
Posts: 1
Joined: February 16th, 2019, 12:20 am

Re: apgsearch v4.0

Post by ZoG » February 16th, 2019, 12:28 am

When I try to run apgluxe, it says

Code: Select all

Illegal instruction (core dumped)
I'm running 4.96. Is there something I'm doing wrong or any way to fix this? Thanks!
(also might be important to note that I'm using Cygwin)

User avatar
Apple Bottom
Posts: 1027
Joined: July 27th, 2015, 2:06 pm
Contact:

Re: apgsearch v4.0

Post by Apple Bottom » February 16th, 2019, 3:54 am

ZoG wrote:When I try to run apgluxe, it says

Code: Select all

Illegal instruction (core dumped)
I'm running 4.96. Is there something I'm doing wrong or any way to fix this? Thanks!
(also might be important to note that I'm using Cygwin)
What sort of machine are you on? apgluxe only runs on x86_64 machines supporting at least (IIRC) SSE2.
If you speak, your speech must be better than your silence would have been. — Arabian proverb

Catagolue: Apple Bottom • Life Wiki: Apple Bottom • Twitter: @_AppleBottom_

Proud member of the Pattern Raiders!

User avatar
calcyman
Posts: 2104
Joined: June 1st, 2009, 4:32 pm

Re: apgsearch v4.0

Post by calcyman » February 17th, 2019, 8:06 pm

In addition to some more minor general speed improvements, apgluxe v4.97 reports the number of tile updates whenever parallelism is disabled. When running:

./apgluxe -n 1000000 -t 1 -v 0 -s test

I get a total of 1 715 262 603 tiles processed for both SSE and AVX2 (these numbers are expected to agree exactly, so this is reassuring), and 1 388 197 897 tiles processed for AVX-512. A tile-update consists of 2 successive generations of a 28x28 (or 28x44 in the case of AVX-512) block of cells.

This means that a large class of future apgsearch optimisations -- such as tweaking stabilisation detection -- can be measured much more precisely than solely relying on wall clock time (the latter being dependent on background processor activity, etc.).
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
77topaz
Posts: 1366
Joined: January 12th, 2018, 9:19 pm

Re: apgsearch v4.0

Post by 77topaz » February 17th, 2019, 9:02 pm

calcyman wrote:./apgluxe -n 1000000 -t 1 -v 0 -s test

I get a total of 1 715 262 603 tiles processed for both SSE and AVX2 (these numbers are expected to agree exactly, so this is reassuring), and 1 388 197 897 tiles processed for AVX-512. A tile-update consists of 2 successive generations of a 28x28 (or 28x44 in the case of AVX-512) block of cells.
I also get exactly 1715262603 tiles processed on an AVX1 machine.

User avatar
77topaz
Posts: 1366
Joined: January 12th, 2018, 9:19 pm

Re: apgsearch v4.0

Post by 77topaz » February 18th, 2019, 4:31 am

I'm not sure whether I should post this here or in the "Catagolue Oddities" thread, but I just noticed what appears to be a bug in apgsearch: in the census for b2n3aijkr4j5cek6ci7c8s2-ci3-acky4einrtz5anr6c7, there are currently three 10000-soup hauls. In two of these, l_zNWe48giKjUY and l_hc7gsQdKS3h5, xq2_1b1 is the third or fourth-most common object, with 1440 and 1455 occurrences, respectively. In the third haul, l_q49qHzuxdkcK, there are somehow zero occurrences of xq2_1b1 (even though a flotilla of two of them, xq2_1b101b1, does appear once). Not surprisingly, l_q49qHzuxdkcK also has significantly fewer objects than the other two hauls.

There's statistically no way this can be correct - the only possible explanation is that while running the l_q49qHzuxdkcK haul, apgsearch somehow decided to discard the list of xq2_1b1 occurrences entirely. The cause of this bug should be investigated as soon as possible, so similar discardings don't affect other, larger censuses.

There's also another weird inconsistency between the hauls, which may also be related: in the hauls l_q49qHzuxdkcK and l_zNWe48giKjUY, there are 712 and 777 occurrences of xs5_174. But in l_hc7gsQdKS3h5, there are 2072 occurrences of that object, and again a corresponding leap in the overall number of objects in the haul. Though, there exists a puffer that outputs xs5_174 in l_hc7gsQdKS3h5 but not the other hauls (yl16_1_5_77367f7f351318623f69d6ca3a09ec0c), so that may have something to do with it. One instance of a p16 puffer contributing 1300-odd extra still lifes still seems a bit peculiar to me, though, so there may be more bugs involved.

Post Reply