Комментарии 25
И неизвестно, что будет эффективнее: предельно оптимизировать анализ одной клетки с просмотром всего поля или оптимизировать формирование и обработку списка клеток, которые могут изменить своё состояние на следующем шаге.
Да, одну клетку будем обрабатывать дольше. Но кол-во обрабатываемых клеток на типичном поле будет меньше даже не в разы, а на порядки.
Да, скорость будет плавающей и в худшем случае будет медленнее. Но эти худшие случаи будут встречаться практически только в начальных комбинациях, а дальше всё быстро сведётся к достаточно низкой средней плотности меняющихся на одном шаге клеток.
Ограничение поля для расчета это отдельная оптимизация, меня интересовало сколько может выдать, грубо говоря, брутфорс
В таком случае хороший прирост производительности можно получить из texture swizzle pattern для улучшения кэш когерентности соседних ячеек.
повторюсь, мне кажется, что узкое место- гигабайтная lookup-таблица, к ней постоянно идет обращение, и она не влезает в кэш, поэтому идут частые промахи кеша и тормоза на случайное чтение из ОЗУ, а не на обработке битовых операций в ядрах CPU.
Да, но когда фигуры начинают повторяться, то у этой таблицы будет не так много горячих областей
аргумент. значит, надо бенч пускать не просто "абыкак", а на поле, заполненным каким-то псевдослучайным шумом (условно, 10% живых клеток, например) и на поле, заполненном пачкой разнонаправленных глайдеров и других "живых тварей". и сравнивать производительности в этих случаях. :-). и мы плавно приходим выводу, что "а че мы вообще меряем-то?".
обработка клеток требует последовательного чтения данных из памяти- на каждом шаге клетка считывается из памяти один раз и записывается один раз. массив хелпер можно рассматривать как промежуточный слой, и на первом шаге "cell" считаем основным, а "helper"- вспомогательным, а на втором шаге- меняем их местами, тогда нам не нужно будет на каждом прогоне перемещать данные из хелпера в целл. А вот обращения к lookup-таблице происходят рандомно при обработке каждой пачки клеток. Из этого я делаю вывод, что производительность представленного кода упирается не в битовые операции не в математику вообще, а в долгий доступ к памяти при обработке lookup-таблицы. Ускорение можно получить, если размер lookup-таблицы будет меньше 32МБ- тогда она будет влезать целиком в кэш авторского процессора, обращение к ней будет быстрым, и скорость обработки будет близка к теоретическому пределу шины памяти- порядка 50ГБ/с, что при 8клеток на байт и двух операциях памяти (чтение и запись) за ход должны давать порядка 200В клеток в секунду.
высокая скорость обработки, полученная автором, КМК, объясняется тем, что основное количество клеток поля пустые (забиты нулем), и вычисленный по ним адрес в лукап-таблице- тоже нулевой, поэтому обращение идет чаще всего к одному и тому же участку lookup-таблицы. Он постоянно лежит в кэше процессора (возможно даже- не вылезает из L1) и быстро отвечает, а когда попадаются живые клетки- то приходится прыгать по всему гигабайту этой таблицы и вываливаться за пределы кэша- в L2, L3 или вообще в ОЗУ, что очень медленно.
Вообще, на такой простой математике (целочисленная без делений, sin/exp/ln и длинных цепочек операций) производительность многопотока должна упираться именно в пропускную способность памяти.
Нет, я просто не привел код случайного заполнения, там не было нулей
это надо подробно разбираться- че там на каком шаге есть, какие места таблицы горячие, какие холодные, как часто бывают промахи кеша и в каких условиях. ЕМНИП, если сделать случайное заполнение 50% единиц, то они должны быстро вымереть, и оставить полупустынный ландшафт с анклавами бурно живущих популяций, стреляющих глайдерами. поэтому жизнь на начальных этапах будет сильно не такая, как на поздних, и бенчмарки должны поплыть. но это надо подробно и внимательно изучать вопрос.
Добавил последнюю главку по чередованию шагов.
ну вот, избавление от одного копирования дало Вам 30% прироста. Я посмотрел повнимательнее, и полагаю, что простое изменение порядка обхода клеток даст Вам дополнительно сравнимый эффект. Вы гоняете цикл сначала по x, а потом- по y. А массивы проиндексированы [y,x]. то есть, вместо считывания во внутреннем цикле байтов один за одним ([y,x-1], [y,x], [y,x+1]), вы во внутреннем цикле считываете байты из разных кусков памяти ([y-1,x], [y,x], [y+1,x]), предполагаю, что банальное изменение порядка обхода (сначала по y, а внутри- по x) даст сравнимый прирост. потому что в таком случае у Вас за один запрос к памяти будет в кэш помещаться сразу 64 нужных Вам в ближайшее время байта данных, что снизит во внутреннем цикле количество обращений к ОЗУ сразу в несколько раз, с соответствующим сокращением времени работы.
Вы видимо пропустили, порядок x,y vs y,x я тестировал - пункт 5
нет., я заметил, но не думаю, что Вы там что-то действительно тестировали. Там Вы изменили порядок доступа к памяти на плохом алгоритме, и получили ускорение (с 0.3B до 0.9B)- не понятно с чего, но это совершенно не те скорости обработки данных, на которых время доступа к памяти должно как-то чего-то решать- на такой скорости у Вас ПСП использована менее, чем на 1%, на что она там влияет? это был шаманизм какой-то. На такой скорости может у Вас вообще все данные успевают за время простоя из кэша вытесниться фоновыми процессами?. А вот сейчас у Вас есть хороший алгоритм, на два порядка более быстрый, и утилизирующий ПСП довольно плотно (процентов на 20), на нем скорость доступа к памяти и латентность этого доступа уже реально влияет, и теперь имеет смысл играться с порядком индексов при обходе массивов.
Спасибо, очень интересно!
В step9 происходит 3 чтения из массива на каждом шаге, но зато есть 6 чтений-переписываний переменных "кэша". А поскольку чтение из массива по индексу это O(1), то, видимо, шило поменяли на мыло.
Всё это время над задачей трудился ваш AMD Ryzen 5 3600X 6-Core Processor 3.79 GHz. А как можно было бы запустить этот ваш код на видеокарте?
Ну, и можно вспомнить про ультимативный https://en.wikipedia.org/wiki/Hashlife , опирающий на свойство игры после первых нескольких сотен шагов локально-упрощаться почти всюду до комбинаций осцилляторов и неподвижных конфигураций.
Чёрт побери, обожаю такие вещи!
С одной стороны вроде язык высокого уровня, но можно вполне себе управлять обработкой на низком уровне (=> нет искусственных запретов спускаться на нижние уровни абстракции).
Задачка как я понимаю автора зацепила, целый цикл статей получился :-)
Для продолжения темы оптимизации - тут уже выше спрашивают как это всё можно замутить на GPU, ведь с такими размерностями этот подход прям напрашивается.
Очень интересно как Julia работает в такой среде, буду ждать продолжения!
Я тоже пробовал различные варианты оптимизации Жизни:
Хранение и обработка блоков 4 на 4.
Таблица поиска занимает всего 64 кб и содержит значение 4 центральных клеток.
Для получения промежуточного блока из соседних нужно 5 битовых операций.
Разделение на четные и нечетные шаги.
При этом на нечетном шаге все поле сдвинуто по диагонали.
Флаги изменений.
На поле меняется не очень много ячеек, и проверка флагов выгоднее чем честное вычисление нового состояния.
Рекурсивное хранение флагов изменений.
Можно пропустить большие участки стабилизировавшегося поля.
Последний результат: желудь на поле 512 на 512, 1200 шагов расчитываются за 1,5 мс.
Вариант на SIMD без этих оптимизаций в 10 раз медленнее.
А если через FFT сделать? По сути расчет кол-ва "живых" соседей есть свёртка игрового поля с простым ядром.
Кстати, уже есть на хабре https://habr.com/ru/post/180135/
Интересно, что можно выжать из Python в рамках этой же задачи.
Надо будет попробовать заюзать Cython + Pandas и посмотреть во что выльется по скорости.
nb = cell_left_upper + cell_upper + cell_right_upper + cell_left + cell_right + cell_left_lower + cell_lower + cell_right_upper
При проверке производительности различных оптимизаций нужно ещё проверять их корректность. В какой-то момент правая верхняя ячейка стала учитываться 2 раза.
Максимальная оптимизация игры «Жизнь» на Julia