I’ve created a Life implementation in javascript with the goal to be as fast as possible, with the rendering I’m satisfied (see picture bellow), hovever the next state calculation is really slow and I’m out of ideas how to speed it up even more.

## Rendering

**Screenshot of the game**

*I can get 700FPS+ when rendering a total population of 6,986,628*

I achieved this by using regl for rendering and moving the calculation of the visible cells to a separate thread (spawned a web worker dedicated for this). I think this doesn’t need any optimization, maybe the way I calculate the visible cells.

**The way I calculate visible cells**

```
onmessage = function (e) {
var visibleCells = ();
for (const x of e.data.grid.keys()) {
if (x < -(e.data.offsets.X+1)) continue; //Continue until reaches the visible part
if (x > -e.data.offsets.X+e.data.width) break; //Stop after leaving visible part
for (const y of e.data.grid.get(x).keys()) {
if (y < e.data.offsets.Y-1) continue;
if (y > e.data.offsets.Y+e.data.height) break;
visibleCells.push((x, y));
}
}
this.postMessage({result: visibleCells})
}
```

## Representing the “universe”

I had some ideas on how to represent the Life universe but I stick with the last option as it turned out to be the best performing. (Note that this implementation does not restrict the space so it is an infinite grid)

### 1.1 Using 2D array as cellState = grid(x)(y);

Since we are dealing with an infinite grid this can’t be used

### 1.2 Using 2D array as grid((x,y),(x1,x2),…)

Storing only the living cell’s coordinate. This has the problem of possible duplicates. Also I ran some tests on jsbench.me and turned out that this is slower than the 2nd way (the next one).

### 2. Using an object

Setting an object’s properties to create the illusion of a 2D array. This somewhat worked, but had the problem of the overhead created by converting int to string and via versa, because object indexing uses strings as keys

```
//Defining grid
var grid = {};
//Creating a cell at (x;y)
if (grid(x) == undefined) grid(x) = {};
grid(x)(y) = null;
//Killing a cell at (x;y)
delete grid(x)(y);
if (Object.keys(grid(x)).length == 0) delete grid(x);
```

### 3. Using Maps and Sets (current)

This way I can use integers as indexes and don’t have to deal with the possibility of a duplicate cell

```
//Defining grid
var grid = new Map();
//Creating a cell at (x;y)
if (!grid.has(x)) grid.set(x, new Set());
grid.get(x).add(y);
//Killing a cell at (x;y)
grid.get(x).delete(y);
if (grid.get(x).size == 0) grid.delete(x);
```

This is why I’m writing this question. I don’t know how to further improve performance here.**The code for calculating the next state**

```
onmessage = function (e) {
var newGrid = new Map();
var sketch = new Map();
var start = performance.now();
for (var x of e.data.grid.keys()) {
var col1 = x - 1, col3 = x + 1;
if (!sketch.has(col1)) sketch.set(col1, new Set());
if (!sketch.has(x)) sketch.set(x, new Set());
if (!sketch.has(col3)) sketch.set(col3, new Set());
for (var y of e.data.grid.get(x).keys()) {
var row1 = y - 1, row3 = y + 1;
sketch.get(col1).add(row1);
sketch.get(col1).add(y);
sketch.get(col1).add(row3);
sketch.get(x).add(row1);
sketch.get(x).add(row3);
sketch.get(col3).add(row1);
sketch.get(col3).add(y);
sketch.get(col3).add(row3);
}
}
for (var x of sketch.keys()) {
for (var y of sketch.get(x).keys()) {
//Count neighbours
var c = 0;
var col1 = x - 1, col3 = x + 1;
var row1 = y - 1, row3 = y + 1;
if (e.data.grid.has(col1)) {
//1st col
var col = e.data.grid.get(col1);
c += col.has(row1)
c += col.has(y)
c += col.has(row3)
}
if (e.data.grid.has(x)) {
//2nd col
var col = e.data.grid.get(x);
c += col.has(row1)
c += col.has(row3)
}
if (e.data.grid.has(col3)) {
//3rd col
var col = e.data.grid.get(col3);
c += col.has(row1)
c += col.has(y)
c += col.has(row3)
}
if (c == 3) { //If a cell has 3 neighbours it will live
if (!newGrid.has(x)) newGrid.set(x, new Set());
newGrid.get(x).add(y);
continue;
}
//but if it has 2 neigbours it can only survive not born, so check if cell was alive
if (c == 2 && (e.data.grid.has(x) && e.data.grid.get(x).has(y))) {
if (!newGrid.has(x)) newGrid.set(x, new Set());
newGrid.get(x).add(y);
}
}
}
postMessage({ result: newGrid, timeDelta: performance.now() - start });
}
```

When the worker recives the initial grid it creates two new grids: `sketch`

this grid will contain potentional new cells (as of writing this I just noticed that I don’t add (x;y) to this grid just the neighbouring ones and it still works, I will look into this deeper after I finish writing), and `newGrid`

which will contain the final result. This way I only loop throug the cells that maybe change state.

## Current performance

```
+------------------------+-----------+--------+------+
| Population | 6,986,628 | 64,691 | 3 |
+------------------------+-----------+--------+------+
| Iteration time (ms/i) | 23925 | 212 | 0.16 |
+------------------------+-----------+--------+------+
| FPS (all cell visible) | 900+ | 70 | 60 |
+------------------------+-----------+--------+------+
```

*Before you ask I don’t know why the fps greater if more cells are rendered, but if you know please write it down in a comment*

## Attemts to optimize

### Split work to CPUcores-2 workers

This was unusable, one iteration took minutes to compute on a ~700K population. I think because the object is copied to each worker so the overhead was much larger than using only one worker.