Пишем и оптимизируем Жизнь Конуэя на JS

Обновляя недавно дизайн своего хомяка, подумал – а не сделать ли мне какую-нибудь необычную страницу с 404-й ошибкой? Поскольку в детстве я был впечатлен Жизнью Конуэя ^[1] (как возможно и многие из читателей), решил её на JS и реализовать.

Казалось бы, что сложного в Жизни: если у занятой клетки 2 или 3 соседа – она остается, если у пустой ровно 3 – рождается? В этой статье я и расскажу о своей оптимизации алгоритма и отрисовки в canvas-е, и некоторых не очевидных моментах целочисленной/бинарной арифметики в JavaScript.

Забегая вперед, конечный результат можно увидеть тут ^[2], исходники видны там же (да еще и по лицензии 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 ^[3] — грубо говоря поле разбивается на 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, не буду тут загромождать.

Результаты

Конечная скорость меня полностью устраивает, даже на старых компьютерах есть определенных запас по производительности (код анимации пытается рисовать не более 30 кадров в секунду).

Что примечательно, при отключении аппаратного ускорения в Firefox, скорость с отрисовкой падает в ~1.5 раза. Но в целом, радует, что FireFox подтянулся до планки производительности, установленной Chrome.

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

Результат в законченном виде видно тут ^[2]. Кстати, если увидите ненароком у меня на сайте какие косяки — смело напишите об этом на 3@14.by, лучше я узнаю о них от вас…

Есть идеи по дальнейшей оптимизации и о жизни в целом — в комменты!

Автор: BarsMonster