Пишем и оптимизируем Жизнь Конуэя на JS
Обновляя недавно дизайн своего хомяка, подумал – а не сделать ли мне какую-нибудь необычную страницу с 404-й ошибкой? Поскольку в детстве я был впечатлен Жизнью Конуэя (как возможно и многие из читателей), решил её на JS и реализовать.Казалось бы, что сложного в Жизни : если у занятой клетки 2 или 3 соседа – она остается, если у пустой ровно 3 – рождается? В этой статье я расскажу о своей оптимизации алгоритма и отрисовки на canvas-е, некоторых не очевидных моментах целочисленной/бинарной арифметики в JavaScript.
Забегая вперед, конечный результат можно увидеть тут, исходники видны там же (да еще и по лицензии CC BY).
Идем простым путем
for(y=1;y<maxy-1;y++)//We do not process 1px border
for(x=1;x<maxx-1;x++)
{
sum =
data[readpage][y-1][x-1] + data[readpage][y-1][x ] + data[readpage][y-1][x+1] +
data[readpage][y ][x-1] + data[readpage][y ][x+1] +
data[readpage][y+1][x-1] + data[readpage][y+1][x ] + data[readpage][y+1][x+1];
if(sum==3 || (sum==2 && data[readpage][y][x]))
data[writepage][y][x] = 1;
else
data[writepage][y][x] = 0;
setColor(data[writepage][y][x]);
drawCell(x,y);
}
Оптимизация отрисовки
Будем рисовать пиксель только в том случае, если он изменился - 67 FPS.Т.к. переключение текущего цвета в контексте на каждую клетку - слишком тяжелая операция, будем рисовать в 2 прохода, сначала все рожденные клетки, потом все умершие : 80 кадров в секунду. Поскольку отображается у меня не все рассчитываемое поле (чтобы не было видно "глюков" от столкновения с концем света), не пытаюсь рисовать невидимые клетки на экране - 125 FPS.
Отрисовка в off-screen canvas на практике не дала никакого ускорения, наоборот было небольшое падение из-за копирования в видимую canvas.
Остается только запускать отрисовку кадра не из setTimeout а requestAnimationFrame - чтобы не рисовать анимацию, когда пользователь на неё не смотрит (например если страница в какой-то фоновой вкладке браузера)
Видимо придется переходить к оптимизации алгоритма...
Существующие методы оптимизации
Первенство по скорости на около-бесконечных полях держит hashlife - грубо говоря поле разбивается на quad-tree, и одинаковые блоки не рассчитываются, а берется сразу результат из кеша. Проблема тут в том, что "раскочегаривается" такой алгоритм медленно, памяти жрет кучу, и для нашего поля (256*192) - это как электронным микроскопом гвозди забивать.Другая группа алгоритмов работает на исключении из расчетов блоков поля где пусто (или нет изменений). Но в моём случае поле почти всегда плотно заполнено активностью, так что прирост скорости будет, но не фантастический.
Еще один подход - хранить очередь изменяющихся клеток, и обновлять в массиве сразу сумму. Т.е. вместо того чтобы делать X*Y*8 операций, мы делаем только (кол-во изменившихся клеток на предыдущем шаге)*8. Тут конечно есть существенные накладные расходы на работу с очередью, но даже для плотного поля ускорение в 3-5 раз получить легко (для больших слабозаполненных полей - это достаточно хороший алгоритм).
Но я пойду своим путем
Основная идея - поскольку в JS массивы состоят из объектов, доступ к ним относительно медленный. Ну и вычисление нового состояния клетки через условие - это всегда плохо для процессора из-за непредсказанных ветвлений. Потому, буду минимизировать количество обращений к массиву и переписывать код без ветвлений.Буду хранить поле в битовом виде (по 32 значения на элемент массива). 32-х битные числа в JS хранятся и интерпретируются именно как Signed(!) Integer, но если мы хоть на еденичку вылазим за 32-бита - можем получить вещественное число. Другая интересная особенность - в JS есть 2 команды сдвига вправо, >> и >>>. >>> отличается тем, что рассматривает число как unsigned (и на пустое место "вдвигает" нули, а не знаковый бит). Именно такой сдвиг нам и нужно будет использовать при работе с числами, где у нас используются все 32 бита.
Теперь когда мы идем по строчке слева на право - мы можем получить сразу значение 3-х последовательных ячеек : value&7. Чтобы посчитать сумму этих ячеек - сделаем lookup table на 8 возможных комбинаций, и чтобы не обращяться к медленному массиву даже один раз - запихнем его в одно число:
// Bitcounting trick:
// IN CNT CNTBIN
// 000 0 00
// 001 1 01
// 010 1 01
// 011 2 10
// 100 1 01
// 101 2 10
// 110 2 10
// 111 3 11
// Magiсk lookup number = 0b00000000000000001110100110010100
// Least significant ^
// in octal 0164624Теперь мы можем посчитать сумму сразу 3-х клеток без дополнительных обращений к массиву:
sum = (0164624 >> ((value& 7)<<1)) & 3;Аналогичным образом мы можем посчитать сумму на верхней и нижней линии. Чтобы исключить саму клетку вокруг которой мы считаем сумму - в средней линии мы делаем &5 вместо &7. Таким образом мы получили 3 суммы с 3-х строк без обращений к массиву.
Далее нам нужно получить новое состояние клетки - снова сделаем lookup table, 4 бита уйдут на сумму (максимум 8), 1 бит - на старое состояние:
/*state_lookup =
[
//Old cell state
//0 1
0 , 0 // 0 SUM
, 0 , 0 // 1
, 0 , 1 // 2
, 1 , 1 // 3
, 0 , 0 // 4
, 0 , 0 // 5
, 0 , 0 // 6
, 0 , 0 // 7
, 0 , 0 // 8
];*/
state_lookup = 0340; //0b0000000011100000;
Теперь получить новое состояние клетки без ветвлений мы можем так:
(0340 >>> ((sum<<1) | (v2&1)))&1
Осталось только подумать, как можно расчитать все 32 клетки - ведь для этого нам нужно иметь доступ дополнительно к одной клетке слева и справа. Придется разбивать работу на 2 части, по 16 клеток, и загружать дополнительно как минимум по 1-й клетке слева и справа (вот тут-то нам и понадобится бесзнаковый сдвиг справо, чтобы не получить лишние еденицы в старших разрядах при сдвиге отрицательных чисел). После расчета обоих 16-клеточных половинок, готовое 32-х битное число записывается в массив, и нужно отрисовывать изменившиеся клетки.
Родившиеся клетки мы можем получить как:
need_draw = (new_state ^ data[readpage][y ][x]) & new_state;
need_draw = (new_state ^ data[readpage][y ][x]) & ~new_state;
Если need_draw==0, то рисовать ничего не нужно, иначе - пробегаем по 32-м битам и рисуем необходимые изменения.
Конечный код - видно во View Source, не буду тут загромождать.
Могу еще заметить, что счастливые писатели нативных приложений могут иметь lookup table из 512 однобитовых значений - получать новое состояние из 9-бит старого окружения напрямую. lookup table занял бы 64 байта, и аккурат влез бы в строчку L1 кеша... Эх, мечты, мечты...
Результаты
Конечная скорость меня полностью устраивает, даже на старых компьютерах есть определенных запас по производительности (код анимации пытается рисовать не более 30 кадров в секунду).| Браузер | FPS c отрисовкой | FPS без отрисовки |
| Firefox 12 | 473 | 1545 |
| IE 9 | 209 | 451 |
| Chrome 19 | 274 | 1210 |
Протестировать себя можно тут: с отрисовкой, без отрисовки.
Результат в законченном виде видно тут.
21 Мая 2012
@BarsMonster