apgsearch v4.0

[mniemiec]

At this stage, before anyone programs anything, it's worth discussing how best to represent objects in a toroidal universe.

Based on the current protocols, it would make sense to retain the xs* and xp* conventions, and rather than having the pattern encoding string just be the lowest of all 8 possible reflections and rotations, have it be the lowest of all 8 possible reflections and rotations of all possible translation of the pattern. There would be no need for xq* (unless you want to somehow distinguish agars that seem to shift giving them a lower mod, but this precedent hasn't existed for xp* or xq*). y* would be impossible. zz* should be unnecessary. ov* might still be possible for rules involving large tori.

One could similarly qualify cylindrical rules, although those could support xq*, y*, and zz*.

[dani]

Here's an easy-to-implement suggestion: Make error messages red instead of purple, so they stick out and warn the user. I was wondering why one of my rules wasn't going through before I read the error message.

[muzik]

I'm still experiencing problems with searching b026s1/1x256, which refuses to work entirely. Can this be looked into?

[calcyman]

I'm still experiencing problems with searching b026s1/1x256, which refuses to work entirely. Can this be looked into?

This might have been due to the change I implemented to ensure objects are separated correctly in B0 and Generations rules, judging by the version numbers of successful hauls:

https://gitlab.com/apgoucher/lifelib/co ... 2e5666b3f1

I could try reverting that in the case of B0 rules, since it doesn't look like B0 rules have been working at all lately.

[Majestas32]

I'm sorry, it's my fault

[calcyman]

Here's an easy-to-implement suggestion: Make error messages red instead of purple, so they stick out and warn the user. I was wondering why one of my rules wasn't going through before I read the error message.

Fixed both this and the B0 problem in cccf17cf (version v4.27-ll1.31).

I'm sorry, it's my fault

What is?

[Majestas32]

4.24 was...

Also wait 4.27? What happened to 4.26? Currently still running a 4.24 fork

[calcyman]

4.26 was to reduce the lifetree memory from 400 megabytes to 100 (i.e. to garbage-collect more often) so that it plays better with low-RAM machines. High memory is only useful for running complex patterns in hashlife, which is seldom involved in apgsearch. I think I also merged the latest lifelib to ensure that the refactoring I made (to incorporate streamlife as an alternative algorithm) didn't break anything or cause any slowdown.

Things should also be slightly faster, since Tom Rokicki and I found and corrected a typo which caused lifetree performance to be suboptimal.

[muzik]

If you set the rulestring to something like "b3s23#", the program goes into an infinite loop. Seems like an easy fix.

[77topaz]

If you set the rulestring to something like "b3s23#", the program goes into an infinite loop. Seems like an easy fix.

Also if you type "B3s23", "B3/S23", or other variant formats like that.

[dani]

Hmm, the error message for 'payosha256 authentication succeeded' is also red. I think it would be better to have that to be a different colour, so as to make errors that occur that do not result in a successful search jump out

[77topaz]

Hmm, the error message for 'payosha256 authentication succeeded' is also red. I think it would be better to have that to be a different colour, so as to make errors that occur that do not result in a successful search jump out

Yeah, Danny's point was to make the "there was an error" message a different colour from the "payosha256 authentication succeeded" message. Changing the colour of both those messages doesn't help.

[calcyman]

There are going to be a couple of major updates in the moderately near future:

Firstly, I'm currently implementing support for custom rule genera in lifelib. A rule genus is a Python module for generating code for a rulespace such as LtL, Generations, or BSFKL. This update will allow new rulespaces to be added more easily, and eventually pave the way for functionality to run Golly-compatible rule tables or trees. Moreover, the maintainability of lifelib is increasing as a result of this refactoring effort.

Secondly, I notice that v3.28 is about 30% faster than v4.x for b3s23. I believe this is because v3.28 removes gliders in the incubation stage, rather than the censusing stage. With a little effort, this can similarly be implemented in v4.x, with the effect of making it at least as fast as v3.28.

[Majestas32]

APGLUXE 4.3 CONFIRMED

[Apple Bottom]

Secondly, I notice that v3.28 is about 30% faster than v4.x for b3s23. I believe this is because v3.28 removes gliders in the incubation stage, rather than the censusing stage. With a little effort, this can similarly be implemented in v4.x, with the effect of making it at least as fast as v3.28.

Excellent! Then I can finally upgrade my 3.28 searchers to 4.x

And support for pluggable rules? Wonderful, that's great news as well.

[cordership3]

And in the meantime, v4.3||1.5 is already working, with support for LtL Generations rules.
https://catagolue.appspot.com/census/g6 ... 5s34t58/C1

[calcyman]

And in the meantime, v4.3||1.5 is already working, with support for LtL Generations rules.
https://catagolue.appspot.com/census/g6 ... 5s34t58/C1

...and v4.32-ll1.5 supports Isotropic Generations as well:

https://catagolue.appspot.com/census/g3 ... 4ir5y7c/C1

The code change to incorporate this was ridiculously small:

https://gitlab.com/apgoucher/lifelib/co ... b9e70b3682

Lifelib genera aren't quite as user-friendly as Golly ruletables, but more flexible and computationally efficient.

[cordership3]

Can anybody troubleshoot what exactly happened here (with the exception of the obvious memory error)?

Code: Select all

<snip status lines>

b3s23/C2_4: 268017 soups completed (431.317 soups/second current, 461.626 overall).
Rare oscillator detected: xp8_gk2gb3z11
b3s23/C2_4: 273017 soups completed (500.000 soups/second current, 462.275 overall).
b3s23/C2_4: 277672 soups completed (465.500 soups/second current, 462.329 overall).
b3s23/C2_4: 282716 soups completed (504.400 soups/second current, 463.018 overall).
b3s23/C2_4: 287908 soups completed (519.200 soups/second current, 463.923 overall).
b3s23/C2_4: 292875 soups completed (496.700 soups/second current, 464.443 overall).
Memory error!!!

...hundreds of memory errors later...

Memory error!!!
(program stops)

[Majestas32]

There is a memory error.

[Apple Bottom]

Can anybody troubleshoot what exactly happened here (with the exception of the obvious memory error)?[/code]

Looks like this is thrown in several places in lifelib, specifically in hashtrees/kivtable.h, when calls to posix_memalign(3) fail.

Looking at the man page for that in turn, there's two possible error conditions --- the "alignment" argument is not a power of two (or a multiple of sizeof(void*)), or there wasn't enough memory to fulfill the request. Since I reckon we can likely rule out the former, I'd bet it's the latter. TL;DR: not enough free memory (or perhaps too much memory fragmentation). This may be due to a lack of memory on your system, or due to a bug in apgsearch that leads it to request more memory than is reasonable.

(Keep in mind of course that on Cygwin, posix_memalign is sneakily mapped to a call to std::malloc instead. But the point still stands, chances are you're simply out of memory, and a request made could not be fulfilled.)

What you may want to include in such bug reports, BTW, is the exact version of the program used, tools used to build it, OS and version (Linux? Cygwin? ...), and the rule, symmetry and seed and exact invocation you used so that others can try to reproduce, diagnose, understand, and maybe even fix the underlying issue (assuming there is one, of course).

[calcyman]

For b3s23, v4.4-ll1.52 is now about 5% faster than v3.28, producing in excess of 3400 soups/sec on a single core of an AVX2-compatible machine (Intel(R) Core(TM) i5-4590 CPU @ 3.30GHz). I'll need to do some testing to confirm whether it's reliable, although it seems to be.

I think I can squeeze some extra b3s23 performance by using a more specialised iterator. Tom Rokicki (in private communication) mentioned a GoL circuit with 19 binary operations (amortized), so implementing this would shave some extra instructions from the innermost loop. When AVX-512 goes mainstream, I have some ideas for making a compatible iterator based on that as well.

EDIT: I've verified a v4.4-ll1.52 haul with a v3.28 instance.

[calcyman]

I think I can squeeze some extra b3s23 performance by using a more specialised iterator. Tom Rokicki (in private communication) mentioned a GoL circuit with 19 binary operations (amortized), so implementing this would shave some extra instructions from the innermost loop.

Implemented: v4.41-ll1.53 is now 6% faster than v4.4-ll1.52, producing about 3600 soups/sec on a single core of my AVX2 machine. (I've tested that it works for all 3 instruction sets, but only performed the timing comparison for AVX2.) More generally, lifelib runs patterns in b3s23 about 10% faster than before; performance for all other rules is unchanged.

You can compare it with the old version by commenting out the 'b3s23life' line in lifelib/genuslist.py (the short file which lists the various algorithms for running different cellular automata).

[77topaz]

When I try to use --update to update my version of apgsearch, I get this error message:

Code: Select all

Checking for updates from repository...
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100  5381  100  5381    0     0   4360      0  0:00:01  0:00:01 --:--:--  4364
...your copy of apgluxe does not match the repository.
New version: "v4.41-" LIFELIB_VERSION
Old version: "v4.24-" LIFELIB_VERSION
fatal: Not a git repository (or any of the parent directories): .git

How can I fix this?

[calcyman]

When I try to use --update to update my version of apgsearch, I get this error message:

Code: Select all

Checking for updates from repository...
  % Total    % Received % Xferd  Average Speed   Time    Time     Time  Current
                                 Dload  Upload   Total   Spent    Left  Speed
100  5381  100  5381    0     0   4360      0  0:00:01  0:00:01 --:--:--  4364
...your copy of apgluxe does not match the repository.
New version: "v4.41-" LIFELIB_VERSION
Old version: "v4.24-" LIFELIB_VERSION
fatal: Not a git repository (or any of the parent directories): .git

How can I fix this?

That's strange; if you cloned the project with git (rather than downloading it as a ZIP, or whatever), then you shouldn't see this error message.

The easiest thing to do is probably to download it afresh:

Code: Select all

git clone https://gitlab.com/apgoucher/apgmera.git
cd apgmera
bash recompile.sh

[77topaz]

The first two commands work for me, but "bash recompile.sh" gives an error:

Code: Select all

Skipping updates; use --update to update apgluxe automatically.
Downloading lifelib...
Submodule 'lifelib' (https://gitlab.com/apgoucher/lifelib.git) registered for path 'lifelib'
Cloning into '/Applications/apgluxe/apgmera/lifelib'...
Submodule path 'lifelib': checked out '6a20d348837d19a4794c49619183dca13c0a072e'
Rule unspecified; assuming b3s23.
Symmetry unspecified; assuming C1.
Configuring rule b3s23; symmetry C1
Traceback (most recent call last):
  File "lifelib/rule3asm.py", line 155, in <module>
    main()
  File "lifelib/rule3asm.py", line 90, in main
    import genera
  File "/Applications/apgluxe/apgmera/lifelib/genera/__init__.py", line 4, in <module>
    from genuslist import genus_list
ModuleNotFoundError: No module named 'genuslist'

I wonder if this is another Python 3.x versus Python 2.x error, which gave me problems with apgsearch before.