apgsearch v4.0

For general discussion about Conway's Game of Life.
User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: apgsearch v4.0

Post by Macbi » February 22nd, 2019, 1:43 pm

Moosey wrote:Having just gotten apgluxe, what command would I run to search b3-ck4e5k6is2-in35i6c8? (I use #anon)
When I try it just searches life.

Code: Select all

./apgsearch --rule b3-ck4e5k6is2-in35i6c8

User avatar
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: apgsearch v4.0

Post by Moosey » February 22nd, 2019, 4:26 pm

This has already been observed, but:

Code: Select all

Soup l_AJQCF42zWA9r22377175 lasts an estimated 31740 generations; rerunning...
Soup l_AJQCF42zWA9r22377175 actually lasts 303 generations.
(unrelated)
Soup l_AJQCF42zWA9r7066009 lasts an estimated 31740 generations; rerunning...
Soup l_AJQCF42zWA9r7066009 actually lasts 335 generations.
Why's it like 31740 so much?
not active here but active on discord

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

Re: apgsearch v4.0

Post by 77topaz » February 22nd, 2019, 4:34 pm

Moosey wrote:This has already been observed, but:

Code: Select all

Soup l_AJQCF42zWA9r22377175 lasts an estimated 31740 generations; rerunning...
Soup l_AJQCF42zWA9r22377175 actually lasts 303 generations.
(unrelated)
Soup l_AJQCF42zWA9r7066009 lasts an estimated 31740 generations; rerunning...
Soup l_AJQCF42zWA9r7066009 actually lasts 335 generations.
Why's it like 31740 so much?
It's just a coincidence that particular number appeared twice. The overestimation is connected with the period-8/period-12 checking calcyman just mentioned, and tends to occur when there are p8 oscillators in the soup (for the version that checked at p8, anyway; I assume v4.98 would've done that with p12 oscillators). v4.981 might be able to avoid that entirely (I haven't tested it yet).
77topaz wrote:Okay, I have something both confusing and concerning to report: a major speed decrease in at least some rules between v4.972 and v4.98. Specifically, for b35s2467/C1, v4.972 averaged about 55000-60000 soups/sec/core and and about 81.9 tiles/soup. However, with v4.98, the speed nearly halves to 30000 soups/sec/core with around 226 tiles/soup.

However, for another rule, b2cei3aekqr4aijkny5cky6-ai78s02ai3jknq4jtyz5-acjy6-an7e/C1, there is a speed increase from around 1200-1300 soups/sec/core to 1600-1700 soups/sec/core, with the tile rate going from around 3800 tiles/soup to 2100 tiles/soup (there is a lot more variation with this rule compared to b35s2467/C1).

As a third reference point, b2k3acijr4ijqy6i7cs2aek3ijnqr4it5n/C1 goes from ~240000 tiles/soup... to around ~240000 tiles/soup, so that appears to be unaffected.

As a fourth reference point, b3-ekqr4nt5r6is02-c3/C1 goes from 4800-4900 soups/sec/core and ~490 tiles/soup to around 3800-3900 soups/sec/core and ~660 tiles/soup, another major slowdown.

Is a correction of one part in 2^18 really expected to cause such huge changes, or is something else going on here? :?
With v4.981:

b35s2467/C1: 52000-53000 soups/sec with ~83 tiles/soup

b2cei3aekqr4aijkny5cky6-ai78s02ai3jknq4jtyz5-acjy6-an7e/C1: ~1700 soups/sec with ~2100 tiles/soup

b2k3acijr4ijqy6i7cs2aek3ijnqr4it5n/C1: ~225000 tiles/soup

b3-ekqr4nt5r6is02-c3/C1: 4500-4600 soups/sec with ~560 tiles/soup

So v4.981 does seem to have taken the best of v4.972 and v4.98! :D There's still a bit of a slowdown with b3-ekqr4nt5r6is02-c3/C1, but not as bad as it was before.

User avatar
Rhombic
Posts: 1072
Joined: June 1st, 2013, 5:41 pm

Re: apgsearch v4.0

Post by Rhombic » February 23rd, 2019, 7:46 am

What does "tiles" refer to?
SoL : FreeElectronics : DeadlyEnemies : 6a-ite : Rule X3VI
what is “sesame oil”?

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

Re: apgsearch v4.0

Post by Apple Bottom » February 23rd, 2019, 7:54 am

Rhombic wrote:What does "tiles" refer to?
Data structures used by lifelib. See also the article on Life128 and vlife.
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
Moosey
Posts: 4306
Joined: January 27th, 2019, 5:54 pm
Location: here
Contact:

Re: apgsearch v4.0

Post by Moosey » February 23rd, 2019, 11:48 am

what command do I use for the number of soups per haul?
Say I'm using

Code: Select all

./apgluxe -k (key) --rule b3-ck4e5k6is2-in35i6c8 --symmetry C1
not active here but active on discord

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: apgsearch v4.0

Post by Macbi » February 23rd, 2019, 11:53 am

Moosey wrote:what command do I use for the number of soups per haul?
Say I'm using

Code: Select all

./apgluxe -k (key) --rule b3-ck4e5k6is2-in35i6c8 --symmetry C1

Code: Select all

./apgluxe -k (key) --rule b3-ck4e5k6is2-in35i6c8 --symmetry C1 -n 1048576

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

Re: apgsearch v4.0

Post by dvgrn » February 23rd, 2019, 12:21 pm

Moosey wrote:Having just gotten apgluxe, what command would I run to search b3-ck4e5k6is2-in35i6c8? (I use #anon)
When I try it just searches life.
Moosey wrote:what command do I use for the number of soups per haul?
Say I'm using

Code: Select all

./apgluxe -k (key) --rule b3-ck4e5k6is2-in35i6c8 --symmetry C1
@Moosey, standard practice is to check any coding project like this for a README, read through it carefully, and then ask these kinds of questions if the answers aren't where they should be. But in this case it seems like they are.

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

Re: apgsearch v4.0

Post by calcyman » February 23rd, 2019, 4:02 pm

wildmyron wrote:Thanks for fixing this. I would never have guessed it would be a fencepost error but I'm glad you were able to debug so quickly. I can confirm that my updated apgluxe does indeed correctly detect the p544 in both orientations.
It's occurred to me that this bug would only occur when there's a horizontal line of at least 18 live cells. The p544 in this phase (which is the generation in which the bug occurred) has that property:

Code: Select all

x = 41, y = 15, rule = B2cik3aeiq4aeijnr5cejy6-ak7c/S02-ak3ace4cekqrz5ainqy6cn8
20bo$7bo25bo$6bo27bo$5b2o27b2o$4b2ob2o6bo4bo4bo6b2ob2o$3b2o2bobo4bobo
2bobo2bobo4bobo2b2o$4bo3bob2ob5o2bo2b5ob2obo3bo$5ob29ob5o$4bo3bob2ob5o
2bo2b5ob2obo3bo$3b2o2bobo4bobo2bobo2bobo4bobo2b2o$4b2ob2o6bo4bo4bo6b2o
b2o$5b2o27b2o$6bo27bo$7bo25bo$20bo!
Those non-totalistic line-stretchers that were misclassified as oscillators almost certainly arose in this manner -- as soon as there was a tile-aligned horizontal line of 18 live cells, undefined behaviour occurred.
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 23rd, 2019, 6:17 pm

SoupSearcher::methudetect reports that this:

Code: Select all

x = 7, y = 5, rule = B3/S23
3ob3o$2bobobo$2bob3o$2bobobo$2bob3o!
lasts 31 generations instead of 32. Is it because it checks for population periodicity instead of pattern periodicity? It should still say 32, though!
Last edited by testitemqlstudop on February 23rd, 2019, 8:08 pm, edited 1 time in total.

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

Re: apgsearch v4.0

Post by dvgrn » February 23rd, 2019, 7:01 pm

testitemqlstudop wrote:SoupSearcher::methudetect reports that this:

Code: Select all

x = 7, y = 5, rule = B3/S23
3ob3o$2bobobo$2bob3o$2bobobo$2bob3o!
lasts 31 generations instead of 32. Is it because it checks for population periodicity instead of pattern periodicity? If so, why doesn't it say 30...?
I believe that's right. At T=30 the population is only 20, not 24.

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 23rd, 2019, 8:08 pm

dvgrn wrote:
testitemqlstudop wrote:SoupSearcher::methudetect reports that this:

Code: Select all

x = 7, y = 5, rule = B3/S23
3ob3o$2bobobo$2bob3o$2bobobo$2bob3o!
lasts 31 generations instead of 32. Is it because it checks for population periodicity instead of pattern periodicity? If so, why doesn't it say 30...?
I believe that's right. At T=30 the population is only 20, not 24.
ah yes, me not realizing the top empty spots :oops:

tod222
Posts: 21
Joined: August 23rd, 2010, 12:43 am

Re: apgsearch v4.0

Post by tod222 » February 24th, 2019, 1:20 pm

Code: Select all

    // Disable verification by default if running on a HPC;
    // otherwise verify three hauls per uploaded haul:
    if (verifications < 0) {
        verifications = (parallelisation <= 4) ? 5 : 0;
    }
Why have this? Why shouldn't high-performance computers do verifications? With the increase in CPU cores these days many more computers fall into the HPC category as defined above.

It means that most of the time my instances of apgluxe aren't doing verifications.
Catagolue: @th222 • Twitter: @th222

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

Re: apgsearch v4.0

Post by calcyman » February 24th, 2019, 1:38 pm

tod222 wrote:

Code: Select all

    // Disable verification by default if running on a HPC;
    // otherwise verify three hauls per uploaded haul:
    if (verifications < 0) {
        verifications = (parallelisation <= 4) ? 5 : 0;
    }
Why have this? Why shouldn't high-performance computers do verifications? With the increase in CPU cores these days many more computers fall into the HPC category as defined above.

It means that most of the time my instances of apgluxe aren't doing verifications.
Verifications are done sequentially, not in parallel. As such, if you have many cores, they'd be under-utilised if verifications were enabled by default. (You can enable this by setting -v 5 in the command-line arguments.)
What do you do with ill crystallographers? Take them to the mono-clinic!

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

Re: apgsearch v4.0

Post by testitemqlstudop » February 24th, 2019, 1:50 pm

Is SoupSearcher::methudetect or stabilise3 from apgluxe better at detecting when an arbitrary pattern stabilizes? (See my above post)

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: apgsearch v4.0

Post by wildmyron » February 25th, 2019, 5:49 am

Macbi wrote:I'm not sure if this is the same bug, but this p3410 is being stored under two apgcodes.
I suspect you probably worked out the answer to this - assuming it stopped showing up after you switched to v4.98 - but in light of calcyman's comments about how the bug in lifelib was triggered I examined the p3410 and found it does indeed have a phase with a continuous line of > 18 cells:

Code: Select all

x = 19, y = 27, rule = B2-ae3aeiq4jnw5ak6-ae7e8/S02-ak3eq4ceqryz5-aejq6-ei7e8
9bo4$8bobo$9bo$8b3o$8b3o$6bo5bo$9bo$2b2o2bo2bo2bo2b2o$bo2bo2b5o2bo2bo$
5b2ob3ob2o$19o$5b2ob3ob2o$bo2bo2b5o2bo2bo$2b2o2bo2bo2bo2b2o$9bo$6bo5bo
$8b3o$8b3o$9bo$8bobo4$9bo!
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

tod222
Posts: 21
Joined: August 23rd, 2010, 12:43 am

Re: apgsearch v4.0

Post by tod222 » February 26th, 2019, 1:22 am

wildmyron wrote:
dvgrn wrote:
Moosey wrote:stupid question:
How do you end a search prematurely?
If you're using Cygwin or you're on Linux or Mac (anything POSIX, apparently), then type "q" and wait some number of seconds. Your partial haul will be submitted and the search will exit gracefully.
As 77topaz mentioned, there are cases where this won't work - in particular if the -p option for running in parallel was used.
I just finished a patch which adds signal handling so that parallel apgluxe will exit gracefully in response to several signals. I typically run it with nice and in the background and wanted the quick graceful exit capability.

Once I create an account on GitLab I'll make a merge request.
Catagolue: @th222 • Twitter: @th222

tod222
Posts: 21
Joined: August 23rd, 2010, 12:43 am

Re: apgsearch v4.0

Post by tod222 » February 26th, 2019, 1:46 am

calcyman wrote: Verifications are done sequentially, not in parallel. As such, if you have many cores, they'd be under-utilised if verifications were enabled by default. (You can enable this by setting -v 5 in the command-line arguments.)
I've found that verifications are so quick that the idle cores aren't worth worrying about, at least for Conway's Life, which is all I run. I'll be changing to using -v 5 on my runs.

I'm much more concerned with the pre-allocation of the search space, as sometimes one thread ends up being much slower than the others. It's possibly as much as 2-3 core minutes on a 20-minute parallel run, as a single thread running solo for 30-60 seconds isn't uncommon. (I know this from running gkrellm which can display per-core utilization graphs.) After adding signal handling I understand how the parallel mode works and I'm thinking about the changes needed for the main thread to distribute the search space in chunks of ~10,000 so that no worker thread has the chance to get too far behind.
Catagolue: @th222 • Twitter: @th222

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

Re: apgsearch v4.0

Post by 77topaz » March 1st, 2019, 7:07 pm

Would it be possible, for table-based rules with multiple states, to add an option to have initial soups with all states rather than just states 0 and 1? I suppose the current system works for Brew due to the specific transitions of that rule, but for p2life it doesn't show any of the interactions between states 1 and 2, instead just basically searching b3s23/C1* with state 1.

*or rather, b3s23/C1 with no object separation...

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

Re: apgsearch v4.0

Post by 77topaz » March 8th, 2019, 6:37 pm

I can't get --profile to work properly: after running the 100k-soup profiling haul, I get this error:

Code: Select all

g++ -c -Wall -Wextra -pedantic -O3 -pthread -flto -march=native --std=c++11 -funsafe-loop-optimizations -Wunsafe-loop-optimizations -fprofile-use -fprofile-correction main.cpp -o main.o
clang: warning: optimization flag '-funsafe-loop-optimizations' is not supported [-Wignored-optimization-argument]
clang: warning: optimization flag '-fprofile-correction' is not supported [-Wignored-optimization-argument]
warning: unknown warning option '-Wunsafe-loop-optimizations'; did you mean
      '-Wunavailable-declarations'? [-Wunknown-warning-option]
error: Could not read profile default.profdata: No such file or directory
1 warning and 1 error generated.
make: *** [main.o] Error 1
Is there any way I can fix that?

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

Re: apgsearch v4.0

Post by testitemqlstudop » March 8th, 2019, 10:19 pm

I tested with clang myself, you can't use profiling with clang (it has weird profiler outputs.)

If you're on MacOS, then you can use brew.sh to instal gcc.

If you're on *nix/Windows then it should be easy to get gcc/mingw, respectively.

The only reason to use clang is for its loop unrolling and vectorization, which is unnecessary after calcyman's rewrite of the upattern movement code.

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

Re: apgsearch v4.0

Post by 77topaz » March 9th, 2019, 2:16 am

I have gcc - it even appears in the top line of the error I posted. apgsearch just decides to use clang for part of it for some reason. But anyway, via a Discord discussion calcyman rewrote the profiling code so it now also works with clang.

However, I'm not really observing a speedup when using it.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: apgsearch v4.0

Post by wildmyron » March 9th, 2019, 3:09 am

77topaz wrote:I have gcc - it even appears in the top line of the error I posted. apgsearch just decides to use clang for part of it for some reason. But anyway, via a Discord discussion calcyman rewrote the profiling code so it now also works with clang.

However, I'm not really observing a speedup when using it.
I think it's worth clarifying here that you do not have gcc on MacOS by default - Apple use a shim named gcc which links to the clang/llvm toolchain to simplify building projects which assume gcc will be used as the compiler. This evidently leads to a lot of confusion..
https://stackoverflow.com/questions/195 ... s-to-clang
https://www.quora.com/Why-does-the-gcc- ... cute-clang

If you want to actually build apgsearch with gcc (for comparison perhaps) then you can install it using Homebrew or Macports as testitemqlstudop suggests.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

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

Re: apgsearch v4.0

Post by 77topaz » March 9th, 2019, 3:28 am

Thanks for the clarification, but I meant what I said - I know there is actual gcc on my computer, because I downloaded it for something unrelated to apgsearch which required it (a university project, IIRC). It appears in my command line tools folder separately from clang and llvm, and, like I pointed out before, it even appears in the error code I posted (the topmost line says g++ instead of clang). For further reference, here is the output of "g++ --version" (or "gcc --version", which it redirects to):

Code: Select all

Configured with: --prefix=/Library/Developer/CommandLineTools/usr --with-gxx-include-dir=/usr/include/c++/4.2.1
Apple LLVM version 9.0.0 (clang-900.0.39.2)
Target: x86_64-apple-darwin16.7.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin
I'm not sure why apgsearch preferentially decides to still use clang for that part, but calcyman added some code to the latest apgsearch commit that makes it compatible with clang anyway, so I don't get the error anymore.

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

Re: apgsearch v4.0

Post by calcyman » March 9th, 2019, 4:11 am

testitemqlstudop wrote:I tested with clang myself, you can't use profiling with clang (it has weird profiler outputs.)
You can use clang now (commit bc9f3afa) with profiling; I made some makefile changes to locate the tool llvm-profdata and run it in 'merge' mode to create the profile. It emits lots of warnings, though, so I don't know how effective it is.
The only reason to use clang is for its loop unrolling and vectorization, which is unnecessary after calcyman's rewrite of the upattern movement code.
Well, it would still help on SSE/AVX1 (the rewritten code targets AVX2/AVX-512, and falls back to the loop otherwise). And there might be other places where automatic vectorisation helps.
What do you do with ill crystallographers? Take them to the mono-clinic!

Post Reply