Тези дни отново ме загриза съвестта, че не работя по някакъв сайд-проект – мой собствен или open source и за това днес реших да почета и понапиша Game of Life.
Оказа се доста прост алгоритъм с доста интересна история, която и сами може да си прочетете 🙂
Демо може да видите тук: http://dailyffs.com/life/
Сорсът е тук: https://gist.github.com/1102964
Коментарът към сорса от страна на @skanev е тук: https://twitter.com/skanev/status/95213748092026880
Това, което искам да кажа в тази статия е, че колкото и да са бързи съвремените Javascript engine-и и колкото и разни светила и икони на браузър вендорите да се хвалят, че производителността скача многократно от версия до версия, това не значи че не може да забързате всичко още малко много. Цената на “забързването” е “угрозняване” и оптимизиране на кода. В моя конкретен случай – на една функция, която се вика 60000 пъти на преизчисление.
Въпросната фунцкия:
function getLiveNeighbours(id, data) {
var x = id % canvas.width;
var y = parseInt(id / canvas.width);
var cnt = 0;
for (var i = -1; i < 2; i++) {
for (var j = -1; j < 2; j++) {
if ((i != 0 || j != 0) &&
!(x+i < 0 || x+i >= canvas.width || y+j < 0 || y+j >= canvas.height) &&
data.data[4*((y+j)*canvas.width+(x+i))] != THE_BLACK) {
cnt++;
}
}
}
return cnt;
}
Простата оптимизация на кода включва:
- Премахване на извикването на функцията (тялото на функцията се ползва директно) – спестява 60000 извиквания и времето за изпълнение на една итерация пада от 500ms на 270ms
- Заменяне на двата вложени цикъла проверяващи за броя на съседни клетки – от 270ms на 150ms
- Опростяване на пресмятанията (премахване на умножения) – от 150ms на 60ms
- Създаване на локални референции към често използваните данни (вместо постоянни извиквания от типа “obj.data” при изчисленията се създава и използва локална променлива) – от 60ms на 50ms
// (4)
var width = canvas.width*4;
var d = data.data;
var nd = newdata.data;
var cw = canvas.width;
var ch = canvas.height;
var base = 0;
for (var i = 0; i < d.length/4; i++) {
var x = i % cw;
var y = parseInt(i / cw);
var cnt = 0;
// (1), (2), (3)
if (x > 0 && d[base-4] != THE_BLACK) cnt++;
if (x < cw-1 && d[base+4] != THE_BLACK) cnt++;
if (x > 0 && y > 0 && d[base-4-width] != THE_BLACK) cnt++;
if (y > 0 && d[base-width] != THE_BLACK) cnt++;
if (x < cw-1 && y > 0 && d[base+4-width] != THE_BLACK) cnt++;
if (x > 0 && y < ch-1 && d[base-4+width] != THE_BLACK) cnt++;
if (y < ch-1 && d[base+width] != THE_BLACK) cnt++;
if (x < cw-1 && y < ch-1 && d[base+4+width] != THE_BLACK) cnt++;
...
В крайна сметка производителността скочи 10 пъти, макар логиката на кода да изглежда по-зле от преди. Не, че преди изглеждаше много красива, но все пак 😀
Разбира се има и още един доста по-умен начин за техническа оптимизация – Web Workers. Те са панацеята на всички проблеми, началото и края, давид и голиат, содом и гомор, ин и ян… за тях може да почетете тази статия – Mandelbrot + Web Workers
Забележка:
- става дума за проста техническа оптимизация на кода, а не за подобрения на алгоритъма!
- вероятно оптимизациите в javascript engine-ите не се фокусират върху случаи на извикване на функция 60 хиляди пъти… а би трябвало.
Follow me…
