Conway's Game of Life in C, need help with optimizing

[catmeow72]

I've made an implementation of Conway's Game of Life for the Commander X16, but it is quite slow, even with a small 20x20 board that doesn't make use of the entire usable space.
The source code is at https://complecwaft.com/catmeow/lifex16, and I would like some suggestions as to how to optimize it better, hopefully so that the board can be updated once per second at a larger board size.
Currently, the UI runs at 2FPS when editing, and 0FPS (1 second/frame) when simulating, according to some calculations I added to the program.

[ahenry3068]

I'm going to check out your version when I get a chance.

I read C kinda Ok but slowly, so at some point I may be able to make a suggestion beyond what I make now. But this is off the top of my Head. I wrote a version of LIFE in BASIC viewtopic.php?t=6690 and even without seeing mine has to be slower than the C version. The one little speed up I did get was doing short circuit evaluation for LIFE State. Just one example.
Check for three neighbors 1st. If a cell has three neighbors alive it's current life state doesn't mean anything. Next cycle its alive. Skip any further evaluation. Ditto if >3 neighbors or <2 neighbors its going to be dead. Skip further evaluation. You only have to evaluate life state of cells that have 2 living neighbors.

ONLY PERTINENT TO THE 6502 Platform.
Make sure your using 8 bit math wherever possible... This may be difficult with a large grid. Avoid 32 bit math like its the Plague.

[ahenry3068]

I haven't read your code yet. But.... If your using Ints or bytes for the cells in C make them Bool. I didn't have that option in BASIC. Essentially I was using 16 bits to store 1 bit of information (Alive or Dead)

[catmeow72]

I'm pretty much using the best datatype anyways for the cells (a byte) - If I make the data type 1 bit and pack the bits it seems to slow down due to extra processing required to process individual bits, not affecting other parts of the bytes. 1 byte is the smallest it can be without adding extra processing.

[catmeow72]

I managed to get the simulation running at 1 generation/sec with a 20x20 grid, as long as the GUI doesn't run between generations.

[ahenry3068]

How about short circuiting the evaluations ?

[ahenry3068]

I believe a BOOL in C actually takes up the same 8 bits as a Byte. But the code to evaluate True/False is a bit more efficient if the compiler knows it is a BOOL variable. (I'm not experienced in C... I may be dead wrong)...

[desertfish]

I suspect all of the runtime is spent in main.c 's tick_alive function?

- line 99 sets i and neighbors to 0 but they've just been set to 0 already
- alive() is a function that gets called very often, can you inline it?
- but, I suspect the biggest speed gain is to extend the board with a border of 1 cell around it, that is always dead (don't update it's alive status) . Then you can totally get rid of the tile_exists() call that you're doing for every cell access, because you already know you will never read cells outside of the board

[JayKominek]

I wrote a long post and then the stupid forum decided I needed to log in again, and lost it. Not typing that again, sorry.

I think desertfish has the right idea. You need to eliminate all of the calls to tile_exists, by arranging for the code that accesses the board to never want to access a tile that doesn't exist. Expanding the board is one idea. My longer post suggested manually unrolling and specializing the loops, so that you did the four corners specially, then the top and bottom rows, and the left and right columns, and then the whole middle body.