To Byte or not to Byte

Добрый вечер, Хабр. Немного отвлекусь от расчетов больших и страшных девайсов для выхода за пределы гравиколодца. Есть идея запустить небольшой скрипт, рисующий красивые визуалы (которые потом можно пустить или на пиксел-арт, или на текстуры к чему-нибудь хайтековому).

Сами клеточные автоматы - огромное поле, которое можно рассматривать с самых разных аспектов.

Можно варьировать правила, можно пытаться уйти от брутфорсного перебора вариантов к более изящному запоминанию типичных сценариев и подбором возможных вариантов развития по хэшу клеточного рисунка (Golly, например). Но моя цель - достаточно редкие правила как MirekGro и Bombers, и желания/сил возиться с адаптацией существующих hashlife-алгоритмов к этим двум своеобразным правилам нет.

А еще хочется испытать одномерные "хаотические" правила вроде Rule30 для целей, с визуалами пока вовсе не связанными. Так что пусть будет bruteforce-моделирование с пересчетом сумм вокруг каждой клеточки - просто, быстро в написании и достаточно ресурсоемко.

Как хранить состояние клетки. POJO vs bitwise record

Cостояний у КА может быть больше, чем только "жив/мертв". В MirekGro клетка может пребывать в 4-х состояниях, в Bombers - в 25-и состояниях. Для отслеживания перехода "сейчас/потом" можно или хранением состояние как plain old javascript object вида { now, next }, или же в виде бинарной записи на unsigned Int16, старший байт которого - это состояние "потом", а младший - "сейчас". Посмотрим, какой вариант лучше в производительности.

Модельная ситуация - перевести состояние "потом" в состояние "сейчас", а затем назначить новое состояние "потом". Для большей надежности повторим этот процесс несколько раз. Тестовый вариант - массив из 100000 элементов, который мы будем тасовать 500 раз.

(Не)научные эксперименты проводим в node 12.18.4 на камне i5-8600KF, которому дано 32Гб RAM.

Тест с бинарной записью прошел в среднем за 25,092мс. Тест с объектом - за 43,574мс. Бинарная запись обеспечивал выигрыш в ~1,74 раз. Рост не на порядок, но и почти двукратное ускорение вычисление - это приятно. Так что модель КА будет работать на двухбайтовом числе.

Расплетение массива в вектор vs квадратной матрицы

Еще один момент - как лучше хранить модельные данные, стоит ли держать их в матрице или лучше расплести матрицу в один (но очень длинный вектор)? А заодно - как различается производительности двухмерных массивов в зависимости от того, обычные ли это массивы JS или же новомодные (или уже нет) TypedArrays?

Пройдемся по каждому элементу массива и раз за разом присвоим ему несколько значений. Первый эксперимент - сравнение прогонов по матрице 1000 x 1000, "расплетенной" в вектор из 1000000 элементов. Для обычных Array пять прогонов подряд (миллион элементов, 100 перетасовок) показывают, что одномерная развертка оказалась быстрее в ~ 3,75 раз (245,8мс против 922,8мс)

Теперь запустим аналогичный эксперимент с Uint8Array. Тот же миллион элементов, те же 100 тасовок. Пять прогонов показали, что для Uint8Array разность в производительности между матрицей и вектором - в пределах погрешности измерения performance.now().

Можно предположить, что такая разница (точнее - ее полное отсутствие) связано с тем, что для обычного Array постоянно происходит перерасчет границ массива (т.к. каждый его элемент может иметь произвольный размер), что приводит к просадке производительности при работе с многомерным массивом. Для TypedArray такой проблемы быть не должно из-за фиксированного размера каждого элемента. Кстати, Uint8Array также оказался немного быстрее (где-то на 10%), чем обычный Array.

Выводы

1. Даже в JS можно спуститься на уровень работы с отдельными байтами и получит от этого ощутимый прирост производительности. Ну или багов. И удовольствия

2. Двухмерные массивы на обычном Array - это весьма прожорливые конструкции (а ведь я даже не пытался экспериментировать с разреженными массивами или диагональными матрицами, где ситуация может стать совсем забавной)

3. TypedArrays обладают преимуществом в производительности, и с ними нет необходимости "расплетать" 2d-матрицу в вектор

4. Голоса в голове просят повторить эксперимент уже не для IntArray, а для Float. Потому что это уже может пригодиться в Rocket Science. Для той же баллистики, например