How could I further optimize my implementation of Conway's Game of Life? And how would you critique my current strategies? I'm taking a C++ optimization class, the deadline has passed and my assignment has already been submitted. We were supposed to compile with these options: g++ me.cpp -std=c++11 -O3 -march=native -o me.
I'm trying to minimize real time after executing it like this: time ./me 0 1000 0. My program's first argument is the random seed, the second is the number of iterations, and the last is 1 or 0 meaning print or don't print. I don't want to print while timing. The random seed and number of iterations could be any value.
How it works
I iterate through living cells instead of all spaces on the board. I manually unrolled iterating through all 9 tiles encompassing each living cell. Living neighbors, including the central living cell, become incremented positively. Dead neighbors of a living cell become decremented.
That means after the encode function a value of -3 on a dead tile means there are 3 living neighbors, therefore that tile should become alive. 1 is not possible because living cells are incremented at least once. Positive 2 means no living neighbors, 3 means 1 living neighbor, 4 means 2 living neighbors, 5 means 3 living neighbors, etc.
According to the rules there are 3 circumstances where a cell can be alive, but my living_cipher array includes a 4th living state. That's because within the decode method a code value of 1 means I've already decided the cell is alive and now I should ignore that tile. Because 1 should be ignored, the counter_cipher has a zero at that entry. This method transforms codes ranging from -8 to 10, to either a 1 or a 0 meaning living or dead. Rise and repeat for the desired number of iterations.
I used macros as an optimization because constant variables were slower. I did not try an inline function.
#include <iostream>
using namespace std;
#define HEIGHT ((1 << 10) + 2)
#define WIDTH ((1 << 11) + 2)
#define MAX_Y (HEIGHT - 1)
#define MAX_X (WIDTH - 1)
#define NEXT_ROW (WIDTH - 2)
#define AREA (HEIGHT * WIDTH)
constexpr signed char offset_living_cipher[19] = {
0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0
};
constexpr signed char offset_counter_cipher[19] = {
0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0
};
class Matthew_Conway{
private:
bool print;
signed char * board;
signed char ** cells, ** next_cells;
unsigned long total_cells;
void make_cells(){
unsigned long next_total_cells = 0;
cells = new signed char * [AREA];
next_cells = new signed char * [AREA];
for (unsigned long row = 1; row <= HEIGHT - 2; ++row){
for(unsigned long column = 1; column <= WIDTH - 2; ++column){
unsigned long index = row * WIDTH + column;
signed char cell = rand() % 2 == 0;
board[index] = cell;
cells[next_total_cells] = board + index;
next_total_cells += cell;
}
}
total_cells = next_total_cells;
}
public:
unsigned long iterations;
Matthew_Conway(char ** argv){
unsigned random_seed = (unsigned) atoi(argv[1]);
srand(random_seed);
iterations = (unsigned long) atoi(argv[2]);
print = (bool) atoi(argv[3]);
board = (signed char*) calloc(AREA, sizeof(signed char));
make_cells();
}
void print_board(){
if (!print)
return;
for (unsigned long row = 1; row <= HEIGHT - 2; ++row){
for (unsigned long column = 1; column <= WIDTH - 2; ++column){
signed char value = board[row * WIDTH + column];
cout << (int) value;
}
cout << endl;
}
}
void encode() {
#define INCREMENT *board_address += 2 * (*board_address > 0) - 1;
unsigned long next_total_cells = 0;
for (unsigned long cell_i = 0; cell_i < total_cells; ++cell_i) {
signed char * cell = cells[next_total_cells] = cells[cell_i];
unsigned long index = cell - board;
unsigned long y = index / WIDTH;
unsigned long x = index % WIDTH;
if (x == 0 || x == MAX_X || y == 0 || y == MAX_Y){
continue;
}
++next_total_cells;
signed char * board_address = cell - WIDTH - 1; // Upper Left
INCREMENT;
++board_address; // Upper Middle
INCREMENT;
++board_address; // Upper Right
INCREMENT;
board_address += NEXT_ROW; // Middle Left
INCREMENT;
++board_address; // Center
++*board_address;
++board_address; // Middle Right
INCREMENT;
board_address += NEXT_ROW; // Lower Left
INCREMENT;
++board_address; // Lower Middle
INCREMENT;
++board_address; // Lower Right
INCREMENT;
}
total_cells = next_total_cells;
}
void decode() {
#define LIVING_CIPHER (offset_living_cipher + 8)
#define COUNTER_CIPHER (offset_counter_cipher + 8)
#define DECIPHER { \
code = *board_address; \
*board_address = LIVING_CIPHER[code]; \
next_cells[next_total_cells] = board_address; \
next_total_cells += COUNTER_CIPHER[code]; \
}
signed char code;
unsigned long next_total_cells = 0;
for (unsigned long cell_i = 0; cell_i < total_cells; ++cell_i) {
signed char * cell = cells[cell_i];
signed char * board_address = cell - WIDTH - 1; // Upper Left
DECIPHER;
++board_address; // Upper Middle
DECIPHER;
++board_address; // Upper Right
DECIPHER;
board_address += NEXT_ROW; // Middle Left
DECIPHER;
++board_address; // Center
DECIPHER;
++board_address; // Middle Right
DECIPHER;
board_address += NEXT_ROW; // Lower Left
DECIPHER;
++board_address; // Lower Middle
DECIPHER;
++board_address; // Lower Right
DECIPHER;
}
total_cells = next_total_cells;
swap(cells, next_cells);
}
};
int main(int argc, char ** argv){
if (argc != 4){
cout << "usage game-of-life <seed> <generations> <0:don't print, 1:print>" << endl;
return 1;
}
Matthew_Conway conway(argv);
conway.print_board();
for (unsigned long i = 0; i < conway.iterations; ++i){
conway.encode();
conway.decode();
}
conway.print_board();
return 0;
}
