Пишем и оптимизируем Жизнь Конуэя на 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, 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, лучше я узнаю о них от вас…

    Есть идеи по дальнейшей оптимизации и о жизни в целом — в комменты!
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 52
      +2
      Изначально долго раскочегаривается под Chrome — 1 fps
        +3
        Это так и задумано, начинает оно медленно, потом — все быстрее и быстрее.

        setTimeout(function() {requestAnimFrame(frameEventHandler);}, 3000.0/(frame+1)+20);
        
          +2
          Понятно, что так и задумано, но если не смотреть код есть ощущение, что оно просто подтормаживает вначале.
        –7
        Страница не найдена
          +9
          Так и должно быть, это же страница 404-й ошибки.
            +2
            Да ладно?
            +4
            Бот что-ли?
            +3
            О-о-о, у-у-у. а-а-а! Давно пора. Я более года назад делал реализацию, получалось 4-5 мс на ход в Fx 3.6 (200 в секунду), если без графики (при поле 180х150), с графикой меньше. Но с тех пор так и не брался за доработки и оптимизации, тема исчерпала себя.
            (Javascript и canvas в игре «Жизнь» Джона Конвея)
              0
              Да, глядя на те результаты, прогресс производительности JS в Firefox-е впечатляет :-)
                +1
                Тут ещё от процессора зависит (у меня был e2180), а графика — от видеокарты.
                Вот страница, готовая для тестов (с графикой): spmbt.kodingen.com/lifeConway.htm.

                Сейчас проверил на Хроме18 то же поле, на тексте — 4.5 секунды на 100 ходов (тогда в Хроме 8 было столько же. Firefox 12 — 10 секунд (а было 15). Зато канвас-режим (с 4 пикселями квадратики) у него сильно улучшился — было 12, стало 5.5 с. Проверялось на АМД-ноутбуке 1.8ГГц с дискретной штатной видеокартой. Это — тесты с отрисовкой графики, а графика отъедала раза в 2-3 большее время после всех оптимизаций, чем цикл на массивах без графики.

                В общем, согласен, что массивы по определению должны считаться неэффективно, и есть лучшие методы, но оптимизировать энтузиазма не было. Ядро цикла вычислений можно с удобством увидеть на codepaste.ru/5091/, там прокомментировано.
              +1
              Отличная идея! Может кто-нибудь даст ссылок на подобные(анимация, околоайтишная тематика) 404-странички?
              +3
              Сначала было 404, но потом началася война какая-то клеточная!

              Такое впечатление, что вначале программа дико тормозит, поэтому вызывает желание посмотреть загрузку процессора. Может стоит быстрее увеличивать скорость?

              А вообще, очень красивая реализация.
                0
                Да, пожалуй я соглашусь. Сейчас должно быть существенно шустрей.
                  +1
                  А если сделать fading, то будет еще круче смотреться.
                    0
                    В каком смысле?
                      +2
                      Я думаю, имелся ввиду плавный переход цвета, но это сильно ударит по fps.
                +5
                Автор: есть такая, довольно отличная идея. Посмотрел на законченный вариант «404» — там быстро всё рассыпается. Зато, известно, что вариант игры по правилам «DayNight» склонен держать границы гораздо лучше. Чтобы убедиться в этом, поиграйтесь с моим демо: spmbt.kodingen.com/lifeConway.htm. Для просмотра режима «DayNight» выполните такую инструкцию:
                1) открыть или перезагрузить страницу;
                2) выбрать радиокнопку «DayNight»;
                3) поставить «размер» 4;
                4) чекбокс «на canvas»;
                4.1) чекбокс «rect» (будет быстрее);
                5) нажать «Init Random»;
                6) нажать кнопку с крестиком (запустится 100 ходов получившегося рандомного поля)

                При таких настройках у меня 100 ходов пролетают за 7 секунд в Хроме (время отражается на странице), алгоритм выбора правил по матрице, несколько медленнее, чем чистый. В результате получается нечто подобное на 100-м ходу, каждый раз, естественно, разное:


                Видно, что границы стабилизируются и далее плавают интересно и медленно (можно наблюдать, нажимая дальше на кнопку «Х»). Можно сделать клетки 2 на 2, написать цифры «404» с не очень ровными краями как инит-поле — будет, думаю, интересно.

                Ещё для этой версии игры зашит интересный сценарий по нажатию «Init r» вместо «Init Random».
                  +1
                  Согласен, 404 в неком виде осталось бы. Но пропала бы вся ностальгия
                    +1
                    Хорошо, делаете 2 поля, поле с цифрами — по законам DayNight, и ещё космический корабль из демо «Init r» можно в них запустить, а сверху — ружьё по законам Конвея :) на отдельном поле и некоторыми шумами.
                    0
                    Это уже на плазму похоже)
                      0
                      Как здорово! В виде заставки в Windows / отдельного десктопного приложения можно надеяться увидеть?!
                      0
                      Когдато от нечего делать писал «супермегаоптимальную™ жизнь» на 286 компе, для медитативного наблюдения приходилось вставлять задержки. Позже когда я увидел «супермегаоптимальную™ жизнь» под линух, и сравнил со своей, моя оказалась быстрее, но мой интерес к этому давно угас а исходники канули в лету :)
                        +1
                        «Жизнь» в свое время по моему почти каждый кто увлекался программированием делал.
                        Я вон тоже, когда еще только начинал интересоваться программированием, делал реализацию «жизни» на паскале, тоже под 286 компом :)

                        А недавно вообще сделал извращенную реализацию «жизни» на Java в L2, на неписях, служащих клетками мира игры :)

                        видео того как это выглядит
                        исходники этого безобразия на pastebin
                            0
                            Вы не поняли :) тут именно была идея в оптимальности :) К примеру, я там такие алгоритмические улучшения придумал, что обращение к одной клетке, если мне не изменяет память, происходило раз в три хода. Вобщем это была не та «жизнь» которую «каждый пишет», ту «жизнь» я написал еще в школе на спеке :)
                          +1
                          Uint16Array для хранения (быстрая структура) +
                          Web Worker для вычислений (другой поток и у воркера более низкое разрешение таймера) +
                          Рисовать на скрытом канвасе. Можно еще попробовать putImageData.
                            +1
                            Рисовать на скрытом канвасе. Можно еще попробовать putImageData.

                            Оба пункта — антиоптимизации. Остальное имеет смысл, но не везде есть.
                              0
                              Что можешь сказать про оптимизацию очистки канваса? jsperf.com/canvasclear
                                0
                                Считаю, что надо стараться отказаться от идеи функции clearAll и очищать только участки, которые реально поменялись)
                                На практике изменение dom-параметра привязано к ситуации и вызывает reflow, что на тестовой вёрстке незаметно, а в боевом интерфейсе вызовет непонятные тормоза.

                                clear rect:


                                change width:
                              0
                              Держитесь за стулья, с Uint32Array — в хроме просадка по скорости в 4 раза.
                                0
                                В высшей мере странно, должно быть проблема JIT-компилятора.

                                jsperf.com/typed-array-comparison/5 показывает ожидаемые +20-+30% и в хроме и в FF у Uint32Array против Array.
                                  0
                                  если у вас в uint32 массиве хранятся числа вылазящие по значению за max_int, то V8 это не нравится на настоящий момент — деоптимизирует (http://code.google.com/p/v8/source/browse/trunk/src/ia32/lithium-codegen-ia32.cc#2524 ) и потом отключает оптимизацию тех функций, в которых вы так массив используете.

                                  related issue: code.google.com/p/v8/issues/detail?id=2097

                              0
                              Круто! Перед сном заменил 404-ю страницу на новую с этим скриптом и пока разбирал, да пытался подогнать возникла мысль об острой нехватке этого в виде расширения для вордпресса)
                                0
                                отличный все таки повод заменить дефолтную 404-ю для вашей cms/темы.
                                0
                                А все заметили наверху глайдерную пушку, которое через какое-то количество ходов рушит в клочья один из обломков? И еще несколько глайдеров случайно образуются в процессе, если я не ошибаюсь, и улетают в бесконечность.
                                  0
                                  *которую
                                    0
                                    404 — рандомные, так что там каждый раз по разному
                                    0
                                    Потрясно.

                                    Реализовывал игру «жизнь» на Ассемблере в 1998 году.
                                      0
                                      Можете объяснить смысл двух циклов в исходном коде?

                                      for(bit=0;bit<16;bit++)
                                      {
                                      sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+
                                      ((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
                                      ((0164624 >>> (((v3>>>bit)&7)<<1))&3);

                                      new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<bit;
                                      }


                                      и

                                      for(bit=0;bit<16;bit++)
                                      {
                                      sum = ((0164624 >>> (((v1>>>bit)&7)<<1))&3)+
                                      ((0164624 >>> (((v2>>>bit)&5)<<1))&3)+//&5 because we skip middle cell when calculating number of surrounding cells;
                                      ((0164624 >>> (((v3>>>bit)&7)<<1))&3);

                                      new_state |= ((0340 >>> ((sum<<1) | ((v2>>>(bit+1))&1)))&1)<<(bit+16);
                                      }
                                        0
                                        Первый считает первые 16 бит результата, второй — вторые. Сделать в один цикл не выйдет, т.к. нужно 34 бита исходных данных (по одной клетке слева и справа), чтобы рассчитать новое состояние первой и последней клетки в текущем int32.

                                        Видно что второй цикл пишет биты по позиции (bit+16). v1,v2 и v3 сдвигаются на 16 таким образом, чтобы в них было загружено по одному лишнему биту в начале и конце текущих 16 бит.

                                          0
                                          Не вполне понял зачем нужны два «лишних» бита и как состоится без знаковый сдвиг с приведенным вами в топике примером. Если не сложно, можете чуть разъяснить логику?
                                            0
                                            Нам нужно считать кол-во живых клеток «вокруг» — слева, справа, сверху и снизу.

                                            Т.е. для первого бита из группы из 32-х бит — чтобы посчитать клетки слева — нужно иметь доступ к последнему биту предыдущей группы, а для последнего — к первому биту следующей группы.

                                            Бесзнаковый сдвиг в коде в статье нигде не нужен, он нужен когда мы сдвигаем v1,v2 и v3 на 16 бит вправо для дозагрузки дополнительных данных (добавлю это в статье). Знаковый сдвиг вдвигал бы единицы для отрицательный чисел, и поскольку объединение старых и новых данных делается через or, все биты в v1,v2 и v3 постепенно стали бы 1.
                                        +1
                                        Ждем реализацию в minecraft
                                        +2
                                        У меня все «рыбки» сдохли :(
                                          0
                                          Красиво, что планерное ружьё оказалось уничтожено взрывными волнами =)
                                            0
                                            Может поможет переписать на Silverlight, например.
                                              +1
                                              Угу, чтобы 95% посетителей матерились :-)

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое