ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

LifeAPI - New GOL API (in C++)

For scripts to aid with computation or simulation in cellular automata.

Re: LifeAPI - New GOL API (in C++)

Postby simsim314 » December 29th, 2014, 3:16 am

I was thinking about new golly algorithm based on LifeAPI iterator.

It seems to me that a bit iterator, could be faster than hash table at least for large patterns. One should divide the space into 62x62 squares and use overlapping 64x64 squares to iterate (this approach allows having the min-max optimization very straightforward).

It's also seems to be simple to make stable (or p2) speedup. Also some sort of pattern recognition could work to recognize gliders / *WSSs.

There is also a possibility of having hash for 64x64. Say we create a hash function: from 64x64 space into int64 value. So it will insure most of the times we find the same hash code for 64x64 we will also have the same state.
User avatar
simsim314
 
Posts: 1637
Joined: February 10th, 2014, 1:27 pm

Re: LifeAPI - New GOL API (in C++)

Postby Freywa » April 26th, 2015, 1:43 am

Well I'm on GitHub too. Will you add me to the fray?
Princess of Science, Parcly Taxel
User avatar
Freywa
 
Posts: 390
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

Re: LifeAPI - New GOL API (in C++)

Postby simsim314 » April 26th, 2015, 4:34 am

Freywa wrote:Will you add me to the fray?


I didn't understand your request...
User avatar
simsim314
 
Posts: 1637
Joined: February 10th, 2014, 1:27 pm

Re: LifeAPI - New GOL API (in C++)

Postby simsim314 » August 8th, 2016, 4:41 pm

Some good news for all LifeAPI users (including app users like CatForce and Glue++).

LifeAPI became between 4 to 8 times faster!

After some discussions with simeks in this thread (thx a lot btw), I've managed to make LifeAPI iterate faster, as well as to accelerate with SSE/AVX flags enabled in gcc compiler.

I've committed this version into LifeAPI github repository.

Just add -msse/-mavx/-mavx2 flags to compile. I've explained more in Compilation section of the readme.

@simeks - for some reason LifeAPI is consistently slower than GolGrid. Your test sample with LifeAPI has done 36 BCO/s while GolGrid was ~50. With 8 threads GolGrid reached 200 BCO/s while LifeAPI only ~130. I'm starting to think it has something to do with C++ vs C. Check out PerformanceTest.cpp I've added.
User avatar
simsim314
 
Posts: 1637
Joined: February 10th, 2014, 1:27 pm

Re: LifeAPI - New GOL API (in C++)

Postby simeks » August 9th, 2016, 9:59 am

simsim314 wrote:for some reason LifeAPI is consistently slower than GolGrid. [...] I'm starting to think it has something to do with C++ vs C.

I think the only way to really know what's going on is to look at the generated assembler code... I looked at how GCC compiles IterateState in LifeAPI, and the inner evolve loop compiles perfectly reasonably. Instead I think it's a number of other considerations that makes the difference:

- I use the "restrict" keyword to tell the compiler that the source and destination memory used in a vectorized loop don't overlap. Without that, GCC needs to generate extra code to verify this dynamically.

- A vectorized loop processes four 64-bit words at at time. If the first and last word to be processed isn't aligned to a four-word boundary, GCC needs to generate "peeling code" to process the first and last few words. This can be avoided by aligning the first row up, and the last row down to the correct boundary. After that you have to make sure that you've actually convinced GCC that everything is aligned properly... This is reason for this code in GoLGrid:

s32 required_row_on = higher_of_s32 (in_gg->pop_y_on - 1, 0);
s32 required_row_off = lower_of_s32 (in_gg->pop_y_off + 1, in_gg->grid_rect.height);
s32 make_row_on = align_down_s32 (required_row_on, PREFERRED_VECTOR_BYTE_SIZE / sizeof (u64));
s32 make_row_off = align_up_s32 (required_row_off, PREFERRED_VECTOR_BYTE_SIZE / sizeof (u64));
s32 make_row_cnt = make_row_off - make_row_on;

- GoLGrid_evolve reads from one source grid and writes to one destination grid, and uses no other temporary memory. Typically, after each evolve, you would swap the pointers to the source and destination grids, to avoid having to copy the grid before the next evolve.

- Most of the time the destination grid isn't cleared before being used. The evolve function verifies that all previous content of the destination will be written to, and only clears part of it if that's actually needed. This happens less than 1% of the time, if the previous content of the destination is the same pattern at (gen - 2) when generating (gen).

- Saving and restoring the ymm-registers to the stack takes some time if every use of IterateState is a function call. By making sure that everything is inlined into the loop that iterates successive generations, that can be avoided.

By the way, I thought LifeAPI was supposed to implement a torus, but when I try with a LWSS it doesn't seem to get past the edges... Otherwise, I thought some of the speed difference could be because of the overhead of copying bits at the edges.
simeks
 
Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: LifeAPI - New GOL API (in C++)

Postby Kazyan » August 14th, 2016, 11:35 pm

Wow, quadruple speed at minimum. That's going to be very helpful for large search spaces in CatForce! Excellent!

However, CatForce isn't compiling with the new LifeAPI.h; g++ is throwing errors specifically about the new iterator, because some things in there weren't declared. It seems like this will persist across other programs based on LifeAPI, if the parts of the iterator remain undeclared:

In file included from CatForce.c:3:0:
LifeAPI.h: At global scope:
LifeAPI.h:1166:8: error: ‘__forceinline’ does not name a type
static __forceinline int align_down_int(int arg, int alignment)
        ^
LifeAPI.h:1171:8: error: ‘__forceinline’ does not name a type
static __forceinline int align_up_int(int arg, int alignment)
        ^
LifeAPI.h:1176:8: error: ‘__forceinline’ does not name a type
static __forceinline const void *align_down_const_pointer(const void *p, uint64_t alignment)
        ^
LifeAPI.h:1181:8: error: ‘__forceinline’ does not name a type
static __forceinline void *align_down_pointer(void *p, uint64_t alignment)
        ^
LifeAPI.h:1187:8: error: ‘__forceinline’ does not name a type
static __forceinline void Add(uint64_t* bit2, uint64_t* bit1, uint64_t*bit0, uint64_t* next_cell)
        ^
LifeAPI.h:1195:8: error: ‘__forceinline’ does not name a type
static __forceinline void Add_Init(uint64_t* bit2, uint64_t* bit1, uint64_t*bit0, uint64_t* next_cell)
        ^
LifeAPI.h:1203:8: error: ‘__forceinline’ does not name a type
static __forceinline void Add1(uint64_t* bit1, uint64_t*bit0, uint64_t* next_cell)
        ^
LifeAPI.h:1209:8: error: ‘__forceinline’ does not name a type
static __forceinline void Add1_Init(uint64_t* bit1, uint64_t*bit0, uint64_t* next_cell)
        ^
LifeAPI.h:1215:8: error: ‘__forceinline’ does not name a type
static __forceinline uint64_t GoLGrid_int_evolve_word(uint64_t upper_word, uint64_t mid_word, uint64_t lower_word)
        ^
LifeAPI.h:1249:8: error: ‘__forceinline’ does not name a type
static __forceinline void GoLGrid_int_evolve_column(const uint64_t *__restrict in_entry, uint64_t *__restrict out_entry, int row_cnt)
        ^
LifeAPI.h: In function ‘void IterateState(LifeState*)’:
LifeAPI.h:1269:97: error: ‘align_down_int’ was not declared in this scope
  int make_row_on = align_down_int(required_row_on, PREFERRED_VECTOR_BYTE_SIZE / sizeof(uint64_t));
                                                                                                 ^
LifeAPI.h:1270:97: error: ‘align_up_int’ was not declared in this scope
  int make_row_off = align_up_int(required_row_off, PREFERRED_VECTOR_BYTE_SIZE / sizeof(uint64_t));
                                                                                                 ^
LifeAPI.h:1277:129: error: ‘align_down_const_pointer’ was not declared in this scope
  const uint64_t *in_entry = (const uint64_t *)align_down_const_pointer(state + (uint64_t)make_row_on, PREFERRED_VECTOR_BYTE_SIZE);
                                                                                                                                 ^
LifeAPI.h:1278:116: error: ‘align_down_pointer’ was not declared in this scope
  uint64_t *out_entry = (uint64_t *)align_down_pointer(tempState + (uint64_t)make_row_on, PREFERRED_VECTOR_BYTE_SIZE);
                                                                                                                    ^
LifeAPI.h:1280:61: error: ‘GoLGrid_int_evolve_column’ was not declared in this scope
  GoLGrid_int_evolve_column(in_entry, out_entry, make_row_cnt);
                                                             ^
LifeAPI.h: In function ‘char* ReadFile(const char*)’:
LifeAPI.h:1969:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
    fread(buffer, 1, length, f);
                               ^


This might seem like Tier 1 tech support, but I don't trust myself to fix it personally with borrowed GoLGrid code without breaking the vectorization, or, you know, the program in general.
Tanner Jacobi
User avatar
Kazyan
 
Posts: 779
Joined: February 6th, 2014, 11:02 pm

Re: LifeAPI - New GOL API (in C++)

Postby simeks » August 14th, 2016, 11:59 pm

Kazyan wrote:However, CatForce isn't compiling with the new LifeAPI.h; g++ is throwing errors specifically about the new iterator, because some things in there weren't declared. It seems like this will persist across other programs based on LifeAPI, if the parts of the iterator remain undeclared:

Judging from the error messages all that's needed for it to compile is to add this line at the top of LifeAPI.h:

#define __forceinline inline __attribute__((always_inline))
simeks
 
Posts: 369
Joined: March 11th, 2015, 12:03 pm
Location: Sweden

Re: LifeAPI - New GOL API (in C++)

Postby Kazyan » August 15th, 2016, 2:13 am

That nearly fixes it. Only two errors persist:

In file included from CatForce.c:3:0:
LifeAPI.h: In function ‘LifeState* NewState()’:
LifeAPI.h:412:65: error: ‘_aligned_malloc’ was not declared in this scope
  LifeState* result = (LifeState*)(_aligned_malloc(size, boundary));
                                                                 ^
In file included from CatForce.c:3:0:
LifeAPI.h: In function ‘char* ReadFile(const char*)’:
LifeAPI.h:1971:31: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
    fread(buffer, 1, length, f);
                               ^
Tanner Jacobi
User avatar
Kazyan
 
Posts: 779
Joined: February 6th, 2014, 11:02 pm

Re: LifeAPI - New GOL API (in C++)

Postby simsim314 » August 15th, 2016, 3:27 am

@Kazyan - woops sorry. The latest version was an experiment (that didn't succeeded) to use GolGrid. I left it there because it worked okay at all my stations.

Try to take the latest version now, it should work well. All your problems are due to this small experiment.

I've moved all the experimentation with GolGrid to another branch, hopefully to find the source of the GolGrid performance boost later on.

EDIT Your second message is warning not error.

EDIT2 BTW LifeAPI is now not on torus. Did you find torus option useful? It's very simple fix with some moderate performance cost, but I never find torus to be useful for anything.
User avatar
simsim314
 
Posts: 1637
Joined: February 10th, 2014, 1:27 pm

Re: LifeAPI - New GOL API (in C++)

Postby Scorbie » August 15th, 2016, 9:30 am

simsim314 wrote:EDIT2 BTW LifeAPI is now not on torus. Did you find torus option useful? It's very simple fix with some moderate performance cost, but I never find torus to be useful for anything.
does the new version delete gliders?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: LifeAPI - New GOL API (in C++)

Postby simsim314 » August 15th, 2016, 10:16 am

Scorbie wrote:does the new version delete gliders?


Yep...

EDIT Actually it deletes only from left and right, top and down gliders collided with the "edge". I can at 0 cost make it cylinder instead of torus, and it will remove gliders correctly, cost nothing, and be more consistent. my question does anyone use this option at all? or 64x64 is enough for all known usages?
User avatar
simsim314
 
Posts: 1637
Joined: February 10th, 2014, 1:27 pm

Re: LifeAPI - New GOL API (in C++)

Postby Scorbie » June 21st, 2018, 11:01 am

I am currently trying to write a LuaJIT wrapper to LifeAPI for fast prototyping.
Reading the code, I got curious with this part:
https://github.com/simsim314/LifeAPI/blob/master/LifeAPI.h#L249-L250
Is there a reason they are initialized like this, and not the other way around? This causes the following to have the wrong dimensions.
Recalculate(new_empty_state);


Edit: Also, I made a minimal shared library compiled in gcc, at the cost of the following:
1) Removing function overloading (Okay, can do that in Lua)
2) Converting `uint64_t&` references to `uint64_t* const` pointers here; Does this hurt performance? Or can I just convert this function to receive and return `uint64_t`s without loss of performance?
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: LifeAPI - New GOL API (in C++)

Postby Scorbie » October 14th, 2018, 10:35 am

Here's a small (but not negligible) bug on LifeAPI;
This code should output the evolution of a glider, but outputs something else instead.
#include "LifeAPI.h"

int main(void) {
   New();
   LifeState* pat = NewState("2o$obo$o!", -30, -9);
   printf("Gen 0:\n");
   PrintRLE(pat);
   Evolve(pat, 1);
   printf("Gen 1:\n");
   PrintRLE(pat);
   Evolve(pat, 1);
   printf("Gen 2:\n");
   PrintRLE(pat);
   return 0;
}


This returns:
Gen 0:
x = 0, y = 0, rule = B3/S23
23$2b2o$2bobo$2bo!

Gen 1:
x = 0, y = 0, rule = B3/S23
23$2b2o$3o$3bo!

Gen 2:
x = 0, y = 0, rule = B3/S23
23$ob2o$2o$b2o!


And the results are consistent on Print and PrintRLE, so I'm suspecting the problem is somewhere in the generation algorithm.
This might be the reason why the UnitTests are failing; I think this is either the cause or the result of glider detection/removal failure.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: LifeAPI - New GOL API (in C++)

Postby Gamedziner » October 14th, 2018, 1:38 pm

Scorbie wrote:Gen 1:
x = 0, y = 0, rule = B3/S23
23$2b2o$3o$3bo!

That looks like the glider was shifted one cell to the right mid-calculation, and the rightmost cell was forced to wrap around before it could be deleted.
Gamedziner
 
Posts: 634
Joined: May 30th, 2016, 8:47 pm
Location: Milky Way Galaxy: Planet Earth

Re: LifeAPI - New GOL API (in C++)

Postby Scorbie » October 14th, 2018, 8:58 pm

Gamedziner wrote:
Scorbie wrote:Gen 1:
x = 0, y = 0, rule = B3/S23
23$2b2o$3o$3bo!

That looks like the glider was shifted one cell to the right mid-calculation, and the rightmost cell was forced to wrap around before it could be deleted.

Okay, found out why this was happening:
https://github.com/simsim314/LifeAPI/blob/master/LifeAPI.h#L1176-L1180
When evolving column 0, The code should get the next gen from (empty column) (column 0) (column 1).
However, in the code, it gets the next gen from (empty column) (column 0) (column 2) (Which is the index "2" in bit0[2] bit1[2] in the linked code.)

This corresponds with the erratic behavior in the example I posted.

Therefore, a fix would be changing bit0[2], bit1[2] to bit0[1], bit1[1], but I'll check if that works.

Edit: It required a few more touches to pass the test. The tweaks are documented in:
https://github.com/Scorbie/LifeAPI/comm ... fc791906c0
Here's my fork of LifeAPI, which works as intended again. https://github.com/Scorbie/LifeAPI
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Re: LifeAPI - New GOL API (in C++)

Postby rokicki » October 16th, 2018, 4:58 pm

How does this compare with the algorithm test suite in

https://github.com/rokicki/lifealg/
rokicki
 
Posts: 48
Joined: August 6th, 2009, 12:26 pm

Re: LifeAPI - New GOL API (in C++)

Postby Scorbie » October 17th, 2018, 12:39 am

rokicki wrote:How does this compare with the algorithm test suite in

https://github.com/rokicki/lifealg/

Wow, that's a nice collection!

1) Comparing by speed
I'm not sure. LifeAPI's algorithm is very similar to bitpar2/3, but runs on a 64 by 64 grid. Also, it checks every generation for escaping gliders, so your milage may vary depending on various optimizations turned on or off.

2) Comparing by functionality
Well LifeAPI's basically tries to emulate golly's API, so I guess this compares to GolGrid or lifelib.
Best wishes to you, Scorbie
User avatar
Scorbie
 
Posts: 1374
Joined: December 7th, 2013, 1:05 am

Previous

Return to Scripts

Who is online

Users browsing this forum: No registered users and 2 guests