Cálculo do estado do Game of Life em javascript

Question

Criei uma implementação do Life em javascript com o objetivo de ser o mais rápido possível, com a renderização estou satisfeito (veja a imagem abaixo), porém o próximo cálculo de estado é muito lento e estou sem ideias de como acelerar ainda mais.

Estado atual da implementação

Renderização

Captura de tela do jogo

, posso obter 700FPS + ao renderizar uma população total de 6.986.628
. Consegui isso usando regl para renderizar e mover o cálculo das células visíveis para um thread separado (gerou um web worker dedicado para isso). Acho que não precisa de nenhuma otimização, talvez da forma como calculo as células visíveis.

A maneira como calculo as células visíveis

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})
}

Representando o "universo"

Eu tinha algumas idéias sobre como representar o universo Life, mas mantenho a última opção, pois acabou sendo a de melhor desempenho. (Observe que esta implementação não restringe o espaço, por isso é uma grade infinita)

1.1 Usando array 2D como cellState = grid [x] [y];

Como estamos lidando com uma grade infinita, isso não pode ser usado

1.2 Usando matriz 2D como grade [[x, y], [x1, y2], ...]

Armazenando apenas as coordenadas da célula viva. Isso tem o problema de possíveis duplicatas. Também fiz alguns testes no jsbench.me e descobri que este é mais lento do que a 2ª forma (a próxima).

2. Usando um objeto

Definir as propriedades de um objeto para criar a ilusão de uma matriz 2D. Isso funcionou um pouco, mas tinha o problema da sobrecarga criada pela conversão de int em string e via versa, porque a indexação de objetos usa strings como chaves

//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. Usando mapas e conjuntos (atual)

Desta forma posso usar inteiros como índices e não tenho que lidar com a possibilidade de uma célula duplicada

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

O próximo cálculo de estado

É por isso que estou escrevendo esta pergunta. Não sei como melhorar ainda mais o desempenho aqui.
O código para calcular o próximo estado

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

Quando o trabalhador recebe a grade inicial, ele cria duas novas grades: sketchesta grade irá conter novas células potenciais (enquanto escrevo isso, acabei de notar que não adiciono (x; y) a esta grade apenas as vizinhas e ainda funciona, Vou analisar isso mais profundamente depois de terminar de escrever) ¹ , e newGridque conterá o resultado final. Desta forma, eu só faço loop através das células que podem mudar de estado.

¹ Acontece que foi um erro de sorte após muitas refatorações, funciona porque seus vizinhos irão adicioná-lo à lista, mas se não tiver vizinhos ele irá morrer

Desempenho Atual

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

Antes que você pergunte, não sei por que o fps é maior se mais células forem renderizadas, mas se você souber, escreva em um comentário

Tenta otimizar

Divida o trabalho para CPUcores-2 trabalhadores

Isso era inutilizável, uma iteração levou minutos para calcular em uma população de aproximadamente 700K. Acho que porque o objeto é copiado para cada trabalhador, a sobrecarga era muito maior do que usar apenas um trabalhador.

Answer 1

Desempenho de Loop

O uso de for...ofloops oferece grande legibilidade, mas pode ser caro quando se trata de desempenho porque eles usam interatores internamente ¹ . Como este post explica revertida forloops podem proporcionar melhor desempenho. Este artigo mais recente também compara os forloops com for...inos forEachloops de estilo de programação funcional .

Palavras-chave ES6

Ao escrever JavaScript moderno, há pouco uso para var. As melhores práticas hoje requerem padronização para const- mesmo para matrizes onde os itens são apenas enviados por push através do método push - e se, e somente se, a reatribuição for considerada necessária, use let- por exemplo, nesses forloops.

Comparações de igualdade

Um bom hábito e recomendação de muitos guias de estilo é usar operadores de igualdade estrita (isto é ===, !==). O problema com as comparações soltas é que ele tem tantas regras estranhas que seria preciso memorizar para ter certeza de seu uso adequado.