Пишем и оптимизируем Жизнь Конуэя на 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);
  }
Оно конечно работает, но проблема одна - на i7-3820@4.3Ghz и Firefox 12 - этот код успевает посчитать и нарисовать всего 8.5 FPS (кадра в секунду). Быстрый тест показывает, что тормозит именно отрисовка.

Оптимизация отрисовки

Будем рисовать пиксель только в том случае, если он изменился - 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 124731545
IE 9209451
Chrome 192741210
Что примечательно, при отключении аппаратного ускорения в Firefox, скорость с отрисовкой падает в ~1.5 раза. Но в целом, радует, что FireFox подтянулся до планки производительности, установленной Chrome.

Протестировать себя можно тут: с отрисовкой, без отрисовки.

Результат в законченном виде видно тут.
21 Мая 2012

RSS@BarsMonster3@14.by