Problems with efficiency with the Game of Life

Question

To help prepare myself for my final exam, I wrote a simple Game of Life. I want to expand it to have each sub-population represented by a character, but before I do that, I want to make it more efficient; because right now it's running at about 1 fps, which is way too slow (I'd like at least 3 fps). What I want from a review, mainly is:

1. Any minor fixes that don't require a refactor.

2. Any larger fixes that I might need to move things around to implement.

3. Any other notable things regarding safety/style.

I appreciate any and all feedback that might help prepare me for my exam.

To represent a 2D point - StaticPoint.h

#ifndef STATICPOINT_H
#define STATICPOINT_H
#include <iostream>
class StaticPoint {
protected:
 double x = 0;
 double y = 0;
public:
 StaticPoint();
 StaticPoint(double, double);
 StaticPoint(const StaticPoint&);
 double getX() const;
 double getY() const;
 double distanceTo(const StaticPoint&) const;
 inline bool operator==(const StaticPoint&) const;
 inline bool operator!=(const StaticPoint&) const;
 inline bool operator<(const StaticPoint&) const;
 inline bool operator>(const StaticPoint&) const;
};
std::ostream& operator<<(std::ostream&, const StaticPoint&);
bool StaticPoint::operator==(const StaticPoint& oP) const {
 return x == oP.x && y == oP.y;
}
bool StaticPoint::operator!=(const StaticPoint& oP) const {
 return !(*this == oP);
}
bool StaticPoint::operator<(const StaticPoint& oP) const {
 return x < oP.x || (x == oP.x && y < oP.y);
}
bool StaticPoint::operator>(const StaticPoint& oP) const {
 return *this != oP && !(*this < oP);
}
#endif

StaticPoint.cpp

#include "StaticPoint.h"
StaticPoint::StaticPoint() {
}
StaticPoint::StaticPoint(double nX, double nY) {
 x = nX;
 y = nY;
}
StaticPoint::StaticPoint(const StaticPoint& oP) {
 x = oP.x;
 y = oP.y;
}
double StaticPoint::getX() const {
 return x;
}
double StaticPoint::getY() const {
 return y;
}
double StaticPoint::distanceTo(const StaticPoint& p) const {
 return sqrt( pow(x - p.x, 2) + pow(y - p.y, 2) );
}
std::ostream& operator<<(std::ostream& os, const StaticPoint& p) {
 os << "(" << p.getX() << ", " << p.getY() << ")";
 return os;
}

Represents the cells - Population.h

#ifndef POPULATION_H
#define POPULATION_H
#include <set>
#include <vector>
#include "StaticPoint.h"
class Population {
 std::set<StaticPoint> cells;
public:
 Population();
 static const StaticPoint badCell;
 void addCellToPop(const StaticPoint&);
 void removeCellFromPop(const StaticPoint&);
 void killPopulation();
 StaticPoint getCellAt(double, double) const;
 StaticPoint getCellAt(const StaticPoint&) const;
 bool pointIsOccupied(const StaticPoint&) const;
 int countNeighborsWithin(const StaticPoint&, int depth = 1) const;
 void decideLifeOf(const StaticPoint&);
};
bool cellIsValid(const StaticPoint& c);
std::vector<StaticPoint> getPointsAround(const StaticPoint&, int depth = 1);
#endif

Population.cpp

#include "Population.h"
Population::Population() {
}
const StaticPoint Population::badCell = StaticPoint(std::numeric_limits<double>::lowest(), std::numeric_limits<double>::lowest());
void Population::addCellToPop(const StaticPoint& c) {
 cells.insert(c);
}
void Population::removeCellFromPop(const StaticPoint& c) {
 cells.erase(c);
}
void Population::killPopulation() {
 cells.clear();
}
StaticPoint Population::getCellAt(const StaticPoint& p) const {
 auto cellIt = cells.find(p);
 //Find returns a iterator to the end if it's not found
 if (cellIt == cells.end()) {
 return badCell;
 }
 return *cellIt;
}
StaticPoint Population::getCellAt(double tX, double tY) const {
 return getCellAt(StaticPoint(tX,tY));
}
bool Population::pointIsOccupied(const StaticPoint& c) const {
 return cells.count(c) != 0;
}
int Population::countNeighborsWithin(const StaticPoint& p, int depth) const {
 int count = 0;
 for (const StaticPoint& n : getPointsAround(p, depth)) {
 if (pointIsOccupied(n)) {
 count += 1;
 }
 }
 return count;
}
void Population::decideLifeOf(const StaticPoint& centrePoint) {
 int ns = countNeighborsWithin(centrePoint, 1);
 if (ns < 2 || ns > 3) removeCellFromPop(centrePoint);
 else if (ns == 3) addCellToPop(centrePoint);
}
bool cellIsValid(const StaticPoint& c) {
 return c != Population::badCell;
}
std::vector<StaticPoint> getPointsAround(const StaticPoint& centrePoint, int depth) {
 std::vector<StaticPoint> surrounding;
 //Pre-reserve the number of cells
 surrounding.reserve( pow(depth * 2 + 1, 2) - 1 );
 for (int cY = centrePoint.getY() - depth; cY <= centrePoint.getY() + depth; cY++) {
 for (int cX = centrePoint.getX() - depth; cX <= centrePoint.getX() + depth; cX++) {
 StaticPoint p(cX, cY);
 if (p != centrePoint) {
 surrounding.push_back(p);
 }
 }
 }
 return surrounding;
}

Layer over a population to hold the world's dimensions and any relevant methods - World.h

#ifndef WORLD_H
#define WORLD_H
#include <set>
#include <sstream>
#include <limits>
#include <vector>
#include "StaticPoint.h"
#include "Population.h"
class World {
 Population pop;
 StaticPoint worldDims;
public:
 World(double, double);
 std::string compileOutput(int spacedAt = 2, std::string disp = "#") const;
 //Advances the generation
 void simGeneration();
 void randomizeCells(double chanceOfLife = 0.3, int newSeed = -1);
};
#endif

World.cpp

#include "World.h"
#include <iomanip>
#include <set>
#include <cstdlib>
#include "StaticPoint.h"
World::World(double xMax, double yMax) {
 worldDims = StaticPoint(xMax, yMax);
}
std::string World::compileOutput(int spacedAt, std::string disp) const {
 std::stringstream output;
 for (double cX = 0; cX < worldDims.getX(); cX++, output << '\n') {
 for (double cY = 0; cY < worldDims.getY(); cY++) {
 StaticPoint c = pop.getCellAt(cX, cY);
 output << (cellIsValid(c) ? disp : "") << std::setw(spacedAt);
 }
 }
 return output.str();
}
void World::simGeneration() {
 //We can't modify the population in place;
 // the entire generation needs to be updated at once
 Population newPop = pop;
 for (int y = 0; y < worldDims.getY(); y++) {
 for (int x = 0; x < worldDims.getX(); x++) {
 newPop.decideLifeOf(StaticPoint(x, y));
 }
 }
 //Copy the new Population over the old
 pop = newPop;
}
void World::randomizeCells(double chanceOfLife, int newSeed) {
 if (newSeed > 0) srand(newSeed);
 pop.killPopulation();
 for (int y = 0; y < worldDims.getY(); y++) {
 for (int x = 0; x < worldDims.getX(); x++) {
 if ((rand() % int(1.0 / chanceOfLife)) == 0) {
 pop.addCellToPop(StaticPoint(x, y));
 }
 }
 }
}

The main routine Main.cpp

#include <iostream>
#include <sstream>
#include "StaticPoint.h"
#include "World.h"
#include "Timer.h"
#include <cstdlib>
#include <vector>
bool getRandBool() {
 return bool(rand() % 2);
}
int main(int argc, char* argv[]) {
 using namespace std;
 const long maxX = 50, maxY = 50;
 World w(maxX, maxY);
 w.randomizeCells(0.5, 10);
 w.simGeneration();
 for (int rounds = 0; rounds < 150; rounds++) {
 cout << rounds << "\n" << w.compileOutput() << "\n\n";
 w.simGeneration();
 } 
}

At this point, it's the bare minimum. I'd like to speed it up before I begin expanding on it though.

---

After JS1's suggestions, for my standard test case (30x30 world, 40% spawn chance, seed of 10, and 150 rounds), the time required dropped from 35.502 seconds, to 17.742 seconds (with non-redirected output). That's a definite improvement.d

• JS1: Quick question: why are you using doubles in StaticPoint? Aren't your coordinates all integral?
• Carcigenicate: For ease of transfer if I ever decide to hook it up to legitimate graphics. When I did this project in Haskell, I use integral coords, and (for some reason, I can't remember what), just casting the integral values to doubles wasn't sufficient, so I had to go through and edit all the types. That shouldn't make a difference in performance should it?
• JS1: It does make a difference because of all the implicit type conversions taking place. I don't know how much but you could test it yourself by changing your code to not use floating point anywhere.
• Carcigenicate: Most of what I use are doubles. Are you talking about the for loops?

Answer 1

Bugs

As written, your program doesn't actually simulate the game of life. The problem is that when you create the new generation, you are modifying the cells as you go. This means that the changes you are making to the new generation are affecting the population counts for the rest of the cells yet to be determined. You tried to address this with a copy of the population:

Population newPop = pop;

However, the loop that follows only uses the new population:

for (int y = 0; y < worldDims.getY(); y++) {
 for (int x = 0; x < worldDims.getX(); x++) {
 newPop.decideLifeOf(StaticPoint(x, y));
 }
}

In order for this to work properly, you would have needed to pass in the old population as well:

for (int y = 0; y < worldDims.getY(); y++) {
 for (int x = 0; x < worldDims.getX(); x++) {
 newPop.decideLifeOf(pop, StaticPoint(x, y));
 }
}

The baseline speed

Disregarding the bug mentioned above, I built your code and ran it to see how fast it was. On my machine, I was able to run 5000 iterations in 13.74 seconds (redirecting output to /dev/null). So let 13.74 seconds be the baseline speed that we will try to improve upon.

Using ints instead of doubles

I modified your program to replace all doubles with ints, except for the random generation function. Doing this made the time go down to 11.80 seconds (16% faster).

Avoiding unnecessary vector creation

The function getPointsAround() is unnecessary. All it does is create a vector of points, which the caller countNeighborsWithin() iterates through. If you just put the logic of getPointsAround() directly into countNeighborsWithin(), you can count the neighbors without ever creating the intermediary vector. Doing this decreased the time from 11.80 to 9.65 (22% faster).

Using a vector instead of a set

You currently use a set to represent your cells. Using a set, it takes O(log N) time to retrieve whether or not a cell is occupied, where N is the number of items in the set. You can do better by using a vector of booleans. Each element of the vector represents whether one cell is occupied or not. A lookup into a vector takes O(1) time.

When I modified your program to use a vector instead of a set, the time went from 9.65 to 1.6 (6 times faster).

Removing StaticPoint

After changing the set to a vector, the use of StaticPoint became unnecessary. Indexing into the vector used this formula cells[y*width + x]. I removed all uses of StaticPoint and replaced them with x/y coordinates instead. At this point, I also fixed the bug mentioned above by using two vectors:

std::vector<bool> cells;
std::vector<bool> newCells;

At each generation, the newCells vector is created using the values from cells. Then I copy back to the old generation with:

cells = newCells;

The time went from 1.60 to 0.60 (2.6 times faster). In total, the last iteration was 23 times faster than the original.

Minor things

In World.cpp, it was printing the cells with X being the row number and Y being the column number. That seemed backwards, so I swapped the for loops so that Y would be the row and X would be the column.

Also, where you used std::setw(spacedAt) wasn't working for me. It kept cutting off the first character in each line. I'm not sure why that was but I changed that part just so I could test properly.

The new code

World.h

#ifndef WORLD_H
#define WORLD_H
#include <set>
#include <sstream>
#include <limits>
#include <vector>
#include "Population.h"
class World {
 Population pop;
 int worldWidth;
 int worldHeight;
public:
 World(int, int);
 std::string compileOutput(int spacedAt = 2, std::string disp = "#") const;
 //Advances the generation
 void simGeneration();
 void randomizeCells(double chanceOfLife = 0.3, int newSeed = -1);
};
#endif

World.cpp

#include "World.h"
#include <iomanip>
#include <set>
#include <cstdlib>
World::World(int xMax, int yMax) {
 worldWidth = xMax;
 worldHeight = yMax;
}
std::string World::compileOutput(int spacedAt, std::string disp) const {
 std::stringstream output;
 for (int cY = 0; cY < worldHeight; cY++, output << '\n') {
 for (int cX = 0; cX < worldWidth; cX++) {
 bool isOccupied = pop.pointIsOccupied(cX, cY);
 // This seems to cut off the first character of each line.
 // output << (isOccupied ? disp : "") << std::setw(spacedAt);
 // I used this instead, which uses a spacing of only 1.
 if (isOccupied)
 output << disp;
 else
 output << " ";
 }
 }
 return output.str();
}
void World::simGeneration() {
 for (int y = 0; y < worldHeight; y++) {
 for (int x = 0; x < worldWidth; x++) {
 pop.decideLifeOf(x, y);
 }
 }
 pop.switchToNewgen();
}
void World::randomizeCells(double chanceOfLife, int newSeed) {
 if (newSeed > 0) srand(newSeed);
 pop.initPopulation(worldWidth, worldHeight);
 for (int y = 0; y < worldHeight; y++) {
 for (int x = 0; x < worldWidth; x++) {
 if ((rand() % int(1.0 / chanceOfLife)) == 0) {
 pop.setOccupied(x, y, true);
 }
 }
 }
 pop.switchToNewgen();
}

Population.h

#ifndef POPULATION_H
#define POPULATION_H
#include <set>
#include <vector>
class Population {
 std::vector<bool> cells;
 std::vector<bool> newCells;
 int width;
 int height;
public:
 Population();
 void setOccupied(int x, int y, bool occupied);
 void initPopulation(int newWidth, int newHeight);
 bool pointIsOccupied(int x, int y) const;
 int countNeighborsWithin(int x, int y, int depth = 1) const;
 void decideLifeOf(int x, int y);
 void switchToNewgen(void);
};
#endif

Population.cpp

#include "Population.h"
#include <limits>
#include <math.h>
Population::Population() {
}
void Population::initPopulation(int newWidth, int newHeight) {
 width = newWidth;
 height = newHeight;
 cells.resize(width * height);
 newCells.resize(width * height);
}
void Population::setOccupied(int x, int y, bool occupied) {
 newCells[y * width + x] = occupied;
}
bool Population::pointIsOccupied(int x, int y) const {
 return cells[y * width + x];
}
int Population::countNeighborsWithin(int x0, int y0, int depth) const {
 int count = 0;
 int xEnd = x0 + depth;
 int yEnd = y0 + depth;
 for (int y = y0 - depth; y <= yEnd; y++) {
 if (y < 0 || y >= height)
 continue;
 for (int x = x0 - depth; x <= xEnd; x++) {
 if (x < 0 || x >= width)
 continue;
 if (pointIsOccupied(x, y))
 count++;
 }
 }
 // Subtract off the count of the point itself.
 if (pointIsOccupied(x0, y0))
 count--;
 return count;
}
void Population::decideLifeOf(int x, int y) {
 int ns = countNeighborsWithin(x, y, 1);
 if (ns < 2 || ns > 3)
 setOccupied(x, y, false);
 else if (ns == 3)
 setOccupied(x, y, true);
}
void Population::switchToNewgen(void) {
 cells = newCells;
}

• Carcigenicate: Whoops. Good catch with the first bug. And I'm having difficulties understanding your switch from the set of points to a vector of. books. Why is that faster? I thought vector was a linked list, although if its faster than a tree I guess that's not true. So you have 1 slot in the vector per cell in the world? And I'm guessing it's cheaper to have the second generation always existing instead of constantly creating one? Finally, can you explain the math involved in your 2 "occupied" methods in Population? I don't quite get how they work. Thank you for your detailed review.
• Carcigenicate: And in countNeighbors, the first out-of-bounds check should read if (y < 0 || y >= height) instead of width right?
• JS1: @Carcigenicate 1) A vector is like an array, not a linked list. Looking up a cell is a fast array lookup. Doing the same with a set is slower. 2) Since you need to have a temporary vector every iteration it makes more sense to just keep it around rather than creating and destroying it all the time. 3) This expression y * width + x is how to calculate an array index for point (x,y) in an array of size (width * height). It's a standard way of handling a 2 dimensional array using a 1 dimensional array. 4) Yes good catch on that typo for y >= height. I'll fix my answer.
• JS1: @Carcigenicate Yes exactly. If you search around for 2 dimensional arrays, you will find that formula. For example, here.
• JS1: @Carcigenicate I would suggest that instead of a vector of bools, you make it a vector of chars. You can use char value 0 to represent "no life". And if there is life, you can put the character that you want into the vector. Then in your printing loop, you can grab the character from the vector and print it if it is nonzero.

Answer 2

I would encourage you to change StaticPoint to use int for its coordinates instead of double.

However, I have a hunch your program is getting killed by too many creations and deletions of std::vector<StaticPoint> in Population::countNeighborsWithin.

I would update the function to not create std::vector at all by moving the logic of Population::getPointsAround to Population::countNeighborsWithin.

int Population::countNeighborsWithin(const StaticPoint& p, int depth) const 
{
 int count = 0;
 for (int cY = centrePoint.getY() - depth; cY <= centrePoint.getY() + depth; cY++)
 {
 for (int cX = centrePoint.getX() - depth; cX <= centrePoint.getX() + depth; cX++)
 {
 StaticPoint p(cX, cY);
 if ( (p != centrePoint) && pointIsOccupied(p) )
 {
 count += 1;
 }
 }
 }
 return count;
}

• Carcigenicate: It's funny, I had a dream about "inlining" getPointsAround into countNeighborsWithin last night, then I wake up and check SE, and both of you guys suggested that.
• R Sahu: @Carcigenicate, dreaming up solutions :) Not bad.
• Carcigenicate: I only included that function because I was trying to copy how it did it in Haskell, without even thinking if it was necessary or not. I had one of those head slapping moments around 1 this morning; idk where the hell it came from lol.