LifeAPI - New GOL API (in C++)

[simsim314]

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.

[Freywa]

Well I'm on GitHub too. Will you add me to the fray?

[simsim314]

Will you add me to the fray?

I didn't understand your request...

[simsim314]

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.

[simeks]

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:

Code: Select all

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.

[Kazyan]

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:

Code: Select all

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.

[simeks]

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:

Code: Select all

#define __forceinline inline __attribute__((always_inline))

[Kazyan]

That nearly fixes it. Only two errors persist:

Code: Select all

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); 
                               ^

[simsim314]

@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.

[Scorbie]

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?

[simsim314]

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?

[Scorbie]

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/bl ... #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.

Code: Select all

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?

[Scorbie]

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

Code: Select all

#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:

Code: Select all

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

Gen 1:

Code: Select all

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

Gen 2:

Code: Select all

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.

[Gamedziner]

Gen 1:

Code: Select all

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.

[Scorbie]

Gen 1:

Code: Select all

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/bl ... 1176-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

[rokicki]

How does this compare with the algorithm test suite in

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

[Scorbie]

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.

[wildmyron]

I recently modified popseq.c to output the RLE of all the 4G collisions it generates. After extending the collision space and experiencing OOM crashes I discovered that LifeAPI's GetRLE() leaks a LifeString for every call. I patched up the issue by adding a TempString in the same way that there are several Temp LifeState objects which can be reused without being allocated.

Code: Select all

diff --git a/LifeAPI.h b/../popseq/LifeAPI.h.new
index 2f8ad60..2d5538f 100644
--- a/LifeAPI.h
+++ b/../popseq/LifeAPI.h.new
@@ -109,6 +109,8 @@ LifeString* NewString(const char* val)
        return result;
 }

+static LifeString* TempString = NewString();
+
 typedef struct
 {
        int x;
@@ -1299,7 +1301,7 @@ LifeState* NewState(const char* rle)

 const char* GetRLE(LifeState *state)
 {
-    LifeString* result = NewString();
+    Clear(TempString);

     int eol_count = 0;

@@ -1316,20 +1318,19 @@ const char* GetRLE(LifeState *state)
             if(val == 1 && eol_count > 0)
             {
                 if(eol_count > 1)
-                                Append(result, eol_count);
+                Append(TempString, eol_count);

-                                                       Append(result, "$");
+                Append(TempString, "$");

                 eol_count = 0;
             }
-
             // Flush current run if val changes
             if (val == 1 - last_val)
             {
                 if(run_count > 1)
-                                Append(result, run_count);
+                    Append(TempString, run_count);

-                                                       Append(result, last_val ? "o" : "b");
+                Append(TempString, last_val ? "o" : "b");

                 run_count = 0;
             }
@@ -1342,9 +1343,9 @@ const char* GetRLE(LifeState *state)
         if (last_val == 1)
         {
             if(run_count > 1)
-                        Append(result, run_count);
+               Append(TempString, run_count);

-                    Append(result, "o");
+            Append(TempString, "o");

             run_count = 0;
         }
@@ -1352,7 +1353,7 @@ const char* GetRLE(LifeState *state)
         eol_count++;
     }

-       return result->value;
+    return TempString->value;
 }

 void PrintRLE(LifeState *state)

This suits my purpose because GetRLE() is overused in this application, but in general it may be preferable to fix up the leaks. Also I noticed that there's some funny things going on with NewString(). The LifeString type and associated methods for reference:

Code: Select all

typedef struct 
{
	char* value;
	int size;
	int allocated;
	
} LifeString;

void FreeString(LifeString* string)
{
	free(string->value);
	free(string);
}

LifeString* NewString()
{
	LifeString* result = (LifeString*)(malloc(sizeof(LifeString)));
	
	result->value = (char*)(malloc(2 * sizeof(char)));
	result->value[0] = '\0';
	result->size = 1;
	result->allocated = 1;
	
	return result;
}

void Clear(LifeString* s)
{
	s->value[0] = '\0';
	s->size = 1;

}

void Realloc(LifeString* string)
{
	int empty = NO;
	
	if(string->value[0] == '\0')
		empty = YES;
	
	if(empty == NO)
	{
		string->value = (char*)(realloc(string->value, string->allocated * 2 * sizeof(char)));
	}
	else
	{
		string->value = (char*)(malloc(string->allocated * 2 * sizeof(char)));
		string->value[0] = '\0';
	}
	
	string->allocated *= 2;
}

void Realloc(LifeString* string, int size)
{
	while(string->allocated <= string->size + size + 1)
		Realloc(string);
}

void Append(LifeString* string, const char* val)
{
	Realloc(string, strlen(val));
	strcat(string->value, val);
	string->size = strlen(string->value);
}

void Append(LifeString* string, int val)
{
	char str[10];
	sprintf(str, "%d", val);
	Append(string, str);
}

LifeString* NewString(const char* val)
{
	LifeString* result = NewString();
	Append(result, val);
	return result;
}

I believe that "result->allocated = 1;" in NewString() is a bug, because the char array that's allocated has length 2. Then when any string is appended to this new LifeString the first thing that happens is that Realloc(LifeString* string) is called, which detects that the string is empty, and it allocates a new char* (without freeing the old one) which still has length 2, but now allocated is set to 2. This cycle continues a few times until the "char* value" has the right length, but each time a new array is malloc'ed without reusing or freeing the old one. [Actually, I just noticed that chris_c mentioned this here: https://github.com/simsim314/LifeAPI/pull/2 , but that seems to have been lost amongst the rest of the discussion there.]

There seem to be a few other memory leaks which are probably only hit a few times in any sensible program so they're probably not a big issue. E.g. LoadResults(const char* filePath) doesn't free rle - which points to a char* array allocated in ReadFile(const char *filePath).

Lastly, to simsim314: I understand you have a preference to not use anything within the std:: namespace, but does that alse extend to not using operator new and new[]? These don't require anything from std::. Not really an issue, just curious why you continued to use malloc in place of new.

[simsim314]

Not really an issue, just curious why you continued to use malloc in place of new.

The intention was to use C and not C++. But in C you can't overload a function - this is the only feature I use from C++ (and is the only reason I've switched to C++). I don't like the LifeString object, and the memory leaks are horrible. It's probably preferable to switch to full C++ and use new and <string>.

I don't maintain LifeAPI and recommend switching to lifelib (hopefully LifeAPI will become a more user friendly interface to lifelib). anyway for now if you pull request and fix I'll incorporate it into the main branch. As of fixing it - not sure about the best way to deal with this memory leak (simply erasing the life string will destroy the result string).

[testitemqlstudop]

I recently modified popseq.c to output the RLE of all the 4G collisions it generates. After extending the collision space and experiencing OOM crashes I discovered that LifeAPI's GetRLE() leaks a LifeString for every call. I patched up the issue by adding a TempString in the same way that there are several Temp LifeState objects which can be reused without being allocated.

Does your modified version still check for the population sequence?

(I want to see your code!)

[wildmyron]

I recently modified popseq.c to output the RLE of all the 4G collisions it generates. <snip>

Does your modified version still check for the population sequence?

(I want to see your code!)

No, I only use the hacked popseq.c to generate RLE for the 4G collisions. There's really not much to what I did, it's not very clever about how it searches the 4G collision space.

See the Hacking apgsearch thread for details and code: viewtopic.php?p=76299#p76299

[Scorbie]

Okay, finished the initial draft of the cpp port.
https://github.com/Scorbie/LifeAPI/tree/cpp
This is still a draft, so expect things to break... (N.B. Haven't checked the last test, it takes a long time to run.)
UnitTest.cpp/TestSimkin{01,02,03} functions describe how to use this API.

[simsim314]

Okay, finished the initial draft of the cpp port.

Nice!

I wonder if we could migrate lifelib iterator but keep the interface itself. i.e. we would not be limited by 64x64 yet everything else would be back compatible, specifically all the function supports. lifelib is providing all the functionality as well - but I think LifeAPI strength is its simplicity and many structures and functions prepared for simplistic usage.

[GUYTU6J]

Is there a summary of modern search utilities using LifeAPI, and how to adapt LifeAPI to non-totalistic rules? (Or converting to lifelib for that matter, if not making the program harder to configure)

[Book]

Is there a summary of modern search utilities using LifeAPI, and how to adapt LifeAPI to non-totalistic rules? (Or converting to lifelib for that matter, if not making the program harder to configure)

Would be good to have LifeAPI info added to the wiki.