Pull to refresh

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

Reading time 5 min
Views 6.5K
Обновляя недавно дизайн своего хомяка, подумал – а не сделать ли мне какую-нибудь необычную страницу с 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, 3 бита уйдут на сумму (максимум 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
Что примечательно, при отключении аппаратного ускорения в Firefox, скорость с отрисовкой падает в ~1.5 раза. Но в целом, радует, что FireFox подтянулся до планки производительности, установленной Chrome.

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

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

Есть идеи по дальнейшей оптимизации и о жизни в целом — в комменты!
Tags:
Hubs:
+61
Comments 52
Comments Comments 52

Articles