Obliczanie stanu gry w życie w javascript
Stworzyłem implementację Life w javascript, aby być tak szybko, jak to możliwe, z renderowaniem jestem zadowolony (patrz zdjęcie poniżej), ale następne obliczenia stanu są naprawdę wolne i nie mam pomysłów, jak przyspieszyć jeszcze bardziej.
Aktualny stan realizacji
Wykonanie
Zrzut ekranu gry
Osiągnąłem to, używając regl do renderowania i przenoszenia obliczeń widocznych komórek do oddzielnego wątku (stworzyłem dedykowanego do tego pracownika internetowego). Myślę, że to nie wymaga żadnej optymalizacji, może sposobu, w jaki obliczam widoczne komórki.
Sposób, w jaki obliczam widoczne komórki
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})
}
Reprezentujący „wszechświat”
Miałem kilka pomysłów, jak przedstawić wszechświat Life, ale trzymam się ostatniej opcji, ponieważ okazała się najlepsza. (Zauważ, że ta implementacja nie ogranicza przestrzeni, więc jest to nieskończona siatka)
1.1 Używanie tablicy 2D jako cellState = grid [x] [y];
Ponieważ mamy do czynienia z nieskończoną siatką, nie można jej użyć
1.2 Używanie tablicy 2D jako siatki [[x, y], [x1, y2], ...]
Przechowywanie tylko współrzędnych żywej komórki. To ma problem z możliwymi duplikatami. Przeprowadziłem też kilka testów na jsbench.me i okazało się, że jest to wolniejsze niż druga droga (następna).
2. Korzystanie z przedmiotu
Ustawianie właściwości obiektu w celu stworzenia iluzji szyku 2D. To trochę zadziałało, ale miał problem z narzutem utworzonym przez konwersję int na string i odwrotnie, ponieważ indeksowanie obiektów używa ciągów jako kluczy
//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. Korzystanie z map i zestawów (bieżące)
W ten sposób mogę używać liczb całkowitych jako indeksów i nie muszę mieć do czynienia z możliwością zduplikowania komórki
//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);
Następne obliczenia stanu
Dlatego piszę to pytanie. Nie wiem, jak dalej poprawić tutaj wydajność.
Kod do obliczenia następnego stanu
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 });
}
Kiedy pracownik odzyskuje początkową siatkę, tworzy dwie nowe siatki: sketchta siatka będzie zawierała potencjalne nowe komórki (pisząc to zauważyłem, że nie dodam (x; y) do tej siatki tylko sąsiednich i nadal działa, Przyjrzę się temu głębiej, gdy skończę pisać) 1 , newGridktóry będzie zawierał wynik końcowy. W ten sposób zapętlam tylko komórki, które mogą zmienić stan.
1 Okazuje się, że był to szczęśliwy błąd po wielu refaktoryzacjach, działa, ponieważ sąsiedzi dodają go do listy, ale jeśli nie ma sąsiadów, umrze
Obecna wydajność
+------------------------+-----------+--------+------+
| Population | 6,986,628 | 64,691 | 3 |
+------------------------+-----------+--------+------+
| Iteration time (ms/i) | 23925 | 212 | 0.16 |
+------------------------+-----------+--------+------+
| FPS (all cell visible) | 900+ | 70 | 60 |
+------------------------+-----------+--------+------+
Zanim zapytasz, nie wiem, dlaczego fps jest większe, jeśli renderuje się więcej komórek, ale jeśli wiesz, zapisz to w komentarzu
Próby optymalizacji
Podziel pracę na pracowników CPUcores-2
To było bezużyteczne, obliczenie jednej iteracji zajęło kilka minut na populacji ~ 700 tys. Myślę, że ponieważ obiekt jest kopiowany do każdego pracownika, więc narzut był znacznie większy niż przy korzystaniu tylko z jednego pracownika.
Odpowiedzi
Wydajność pętli
Korzystanie for...ofpętle zrobić dla wielkiego czytelności, ale mogą być kosztowne, jeśli chodzi o wydajność, ponieważ używają interators wewnętrznie 1 . Jak wyjaśnia ten post, odwrócone forpętle mogą zapewnić najlepszą wydajność. W tym nowszym artykule porównano również forpętle z pętlami for...infunkcjonalnego stylu programowania forEach.
Słowa kluczowe ES6
Podczas pisania nowoczesnego JavaScript nie ma pożytku z var. Dzisiejsze najlepsze praktyki wymagają domyślnego const- nawet dla tablic, w których elementy są wpychane tylko metodą wypychania - i wtedy i tylko wtedy, gdy ponowne przypisanie zostanie uznane za konieczne, a następnie użyj let- np. W tych forpętlach.
Porównania równości
Dobrym nawykiem i zalecenie wielu przewodnikach typu jest użycie surowych operatorów równości (tj ===, !==). Problem z luźnymi porównaniami polega na tym, że ma tak wiele dziwnych zasad, których należałoby zapamiętać, aby mieć pewność, że zostanie prawidłowo użyty.