#лытдыбр #common_lisp

Сегодня на утреннем стриме тестил производительность новой фичи в ECS-фреймворке, над которой работал всю неделю, а именно, — составных индексов. Выяснилось, что обработка каждой новой тысячи объектов в игре (например, отрисовка анимированных спрайтов 32x32) занимает 0.25 мс, причём большую часть времени программа проводит внутри сишных функций из liballegro. По-моему, достаточно неплохо 😊

#common_lisp #видео

А вот и монтаж вчерашнего стрима с бенчмарком ECS-фреймворка 😊

#лытдыбр #common_lisp

Решил всё же дропнуть поддержку компилятора Clasp в своём ECS-фреймворке cl-fast-ecs из за его неуловимых внутренних ошибок. Ну то есть во-первых, силушек уже никаких моих вот с пикрелейтеда нету, все макросы в коде позакомментируешь, — работает, добавляешь какой-то совершенно безобидный кусочек кода — валится. И во-вторых, камон, на данный момент времени употреблять слова Clasp и fast в одном предложении — это оксюморон какой-то, он же буквально самый медленный среди вообще всех, даже медленнее ECL, который под капотом в C транслирует.

В общем, коммиты мутятся, процессорные циклы крутятся 😅

#common_lisp #видео

Моя реакция, когда только что написанный код работает с первого раза 😂
https://youtu.be/uUMuEMR-c9s

#лытдыбр #common_lisp

Сегодня на утреннем стриме в третий раз в своей жизни реализовывал алгоритм A*, и опять с первого раза нормально не получилось 😅 Для прямого и ясного, как день, пути через несколько клеточек написанная мной функция возвращает гигантский путь из семи тысяч точек. Буду отлаживать завтра, наверное)

#лытдыбр #common_lisp

Не без помощи товарища на утреннем стриме наконец доделал поиск пути A*-алгоритмом 😊 Путь типа того, что на видео, в отладочном режиме рассчитывается за 3 миллисекунды, так что, видимо, есть место для оптимизаций. Ну и сам путь иногда выглядит не очень естественным для живого существа из пространства с евклидовой метрикой, так что завтра буду пробовать трюки с Amit's A* Pages 😅

#мемасики

Лол, на реддите прекрасное: не у одного меня крыша едет от ковыряния в потрохах Шиндуса 😂

#common_lisp #лытдыбр

Путём длительных экспериментов выяснил, что из всех дистрибутивов GNU-тый CLISP собран с поддержкой тредов, а, следовательно, и с возможностью загрузки bordeaux-threads, только в NixOS и в Gentoo (да и то, если в последней включить юз-флаг threads). Возможно, в Guix тоже, но только после того, как там примут патч от моего подписчика. Но в NixOS настолько древняя версия, что на неё даже Quicklisp не ставится. В общем, в порыве очередной оптимизации CI для своего ECS-фреймворка я всё перелопатил, и теперь в нём CLISP запускается из аж специального докер-образа 😅

#видео #лытдыбр

Посмотрел тут выступление крутейшего Майка Актона, одного из популяризаторов идей data-oriented programming (и ECS в частности). В докладе Майк, как водится, гнёт линию, что не нужно заниматься генерализацией и пытаться решить какие-то эфемерные общие случаи, а нужно решать те задачи, которые конкретно есть в руках в данный момент. Мысль о том, что всё течёт, всё меняется, не бывает на самом деле "future-proof" кода и уже через пять-десять лет код твоей игры (да и сама игра), скорее всего, никому не будет нужен, довольно болезненная, но глубокая 🤔

#лытдыбр

В принципе, начинаю понимать г-на Влада Цепеша, жившего в своё время в краях по соседству, потому что в таком климате единственный способ выжить без кондиционера — это, действительно, дрыхнуть днём в каком-нибудь тёмном подземелье с приятным могильным холодком, и только с заходом солнца выползать из него поделать дела 🫠

#лытдыбр #common_lisp

Вообще я думал, что неплохо соображаю в классических структурах данных, но если начинаешь заниматься низкоуровневой оптимизацией с расчёсыванием кэша CPU вдоль шёрстки и вот этим вот всем, становится жарковато. В последние дней десять занимался тем, что добавлял в свой ECS-фреймворк индекс, прямо как в реляционных БД — вспомогательную структуру данных, которая позволяет быстро сделать обратный запрос, т.е. ответить на вопрос "какие сущности имеют вот это конкретное значение такого-то слота такого-то компонента?". Так вот, следите за руками:

• Хэш-таблица с цепочками в виде лисповских односвязных списков замечательно подходит, но любой поиск по такому индексу — это ужас с точки зрения кэша процессора, да и при вставке требует лишних аллокаций.
• Хэш-таблица с открытой адресацией прекрасно уложится в кэш, так как является по сути единственным плоским массивом, но малину портит тот факт, что сущности с одинаковыми значениями слота в неё вставляются чёрти как, а для кэша хорошо бы было, чтобы они шли в аккуратном возрастающем порядке; а организовать какой-нибудь бинарный поиск места для вставки не выйдет потому, что несколько probing sequences (как это по-русски, последовательности попыток?) могут пересекаться.
• Сбалансированное бинарное дерево тоже подошло бы, если бы не случай одинаковых значений слота — за логарифмическое время, мне кажется, никак не получить все сущности с одинаковыми значениями, придётся обходить вообще всё дерево за O(n), и зачем тогда вообще такой индекс нужен.
• На B+-дерево что-то боюсь замахнуться 😅

Судя по тишине в моём вопросе на SO никто индексами в ECS особо не заморачивался.
В общем, если формализовать задачу, нужна структура данных, в которую можно сравнительно быстро, хотя бы за логарифм, вставлять повторяющиеся ключи произвольного типа (значения слота компонента) со связанными с ними целочисленными значениями (сущностями) и быстро, в идеале за константное время, получать в отсортированном виде все значения, связанные с заданным ключом. Ну и в идеале чтобы эта структура не превращала кэш CPU в щепки 😂

P.S. Перечитал пост и понял, что действительно из того, что я знаю, подходит либо B+-дерево, либо хэштабличка с отсортированными цепочками. Скорее всего, на завтрашнем стриме буду делать второй вариант, хотя B+ тоже интересно, раньше никогда руками такого не делал.

#лытдыбр #common_lisp

На этой неделе решил взяться за behaviour trees — паттерн, используемый для построения сценариев функционирования NPC в играх, и заодно попытаться натянуть его на паттерн ECS 😅 Даже изобразил простенькое тестовое дерево для персонажа-вражины, пытающегося догнать игрока и пнуть его в ближнем бою (см. рис. 1). Правда, с первого раза реализовать не получилось, — мозг запнулся о тот факт, что возвращаемое из узлов дерева булевское значение (успех/неуспех) нужно хранить для каждого узла дерева, а не по одному на всего персонажа, что неизбежно приводит к тому, что своя копия дерева должна быть у каждого персонажа; а мне изначально хотелось сэкономить памяти и хранить только один экземпляр дерева на всех. В общем, завтра с утра на стриме попытаюсь переделать ровно 😊

#лытдыбр

Решил на пару недель сделать перерыв от стриминга, чтобы уже домучать серию туториалов по своему ECS-фреймворку, тем более что я календарь перевернул и снова дофига занятий, которые нужно вести по работе. Заодно по ходу дела надо будет что-то уже решить с поддержкой MacOS и своей дистрибуцией Quicklisp со свежими версиями фреймворка.

Первая часть туториала уже готова где-то на две трети, так что, думаю, в ближайшее время будет. Как говорится, оставайтесь тунцом 😋

#мемасики

Дзен-буддизм, который мы заслужили 😂

#мемасики

В лиспочатике тут прекрасное запостили)

#common_lisp #лытдыбр #проекты

На этой неделе на утренних стримах решил переключиться на GUI-шную библиотеку Nuklear, она (а точнее мои биндинги к ней) давно требует любви ❤️
Уже успел пофиксить всякие мелочи и добавить парочку клёвых макросов в её DSL, а сейчас вот закодил вот такую реализацию assert для неё — надоело, что если хоть что-то с ней делаешь не так, она тут же вызывает сишный ассерт, что приводит к тому, что SBCL вываливается в LLDB (низкоуровневый отладчик), а в Emacs'овских Sly/Slime этого не видно, и кажется, что просто "всё зависло". Теперь хоть будет видно, что произошло, всяко дружелюбнее к пользователю 😊

#лытдыбр #common_lisp

Стою перед сложным выбором, в какую сторону начать бухтеть:
• Экзотической ОС Ш1ИДОШ5;
• Мейнтейнеров MSYS, которые даже не берут на себя труд запустить тот софт, который они распространяют;
• Г-на Фукамачи, который пишет код так, как будто его никто не видит.

Прямо дилемма 🤔

#common_lisp #лытдыбр

Есть у меня в гуёвой библиотеке cl-liballegro-nuklear макрос, with-style-item, который вызывает сишную функцию nk_style_push_style_item, которая, в свою очередь, принимает на вход среди всего прочего два указателя, на "контекст" (по сути точка входа в сишную библиотеку, структура, в которой хранится вся нужная инфа о текущем состоянии GUI), и указатель на ту деталь стиля оформления, которая меняется внутри этой структуры, по сути тот же первый указатель, но со (сравнительно) небольшим оффсетом. Так вот, как выяснилось по итогам экспериментов и треда на реддите, SBCL не умеет аллоцировать свои обёртки для сишных указателей на стеке. От слова "совсем". Наглядная демонстрация:

> (macroexpand-1 '(nk:with-style-item c nk:+style-window-fixed-background+
                   (nk::style-item-image* i)))
(LET ((#:ITEM353 (CL-LIBALLEGRO-NUKLEAR:STYLE-ITEM-IMAGE* I))
      (#:OFFSET354
       (CFFI-SYS:INC-POINTER C
                             CL-LIBALLEGRO-NUKLEAR:+STYLE-WINDOW-FIXED-BACKGROUND+)))
  (DECLARE (DYNAMIC-EXTENT #:ITEM353 #:OFFSET354))
  (CL-LIBALLEGRO-NUKLEAR:STYLE-PUSH-STYLE-ITEM C #:OFFSET354 #:ITEM353)
  (CL-LIBALLEGRO-NUKLEAR:STYLE-POP-STYLE-ITEM C))


> (disassemble #'(lambda (c i)
                   (declare (type cffi:foreign-pointer c i)
                            (optimize (speed 3) (safety 0) (debug 0)))
                   (nk:with-style-item c nk:+style-window-fixed-background+
                       (nk::style-item-image* i))
                   nil))
; ... snip ...
; full: https://gist.github.com/lockie/24fa8c730eb82f53e7e79db418a71b8b
; 343: L2:   6A10             PUSH 16
; 345:       FF142578050050   CALL [#x50000578]               ; #x52A004F0: ALLOC-TRAMP
; 34C:       5F               POP RDI
; 34D:       4080CF0F         OR DIL, 15
; 351:       EB9A             JMP L0

Обратите внимание, как SBCL упорно ложит с прибором на декларацию dynamic-extent и выделяет под CFFI-ный указатель 16 байт (видимо, сам указатель и тэг типа) с кучи. Чтобы такое зафиксить, придётся лезть глубоко в кишки SBCL и перетирать с его разработчиками, а мне чёт неловко таких серьёзных людей от их дел отвлекать 😅

#лытдыбр #common_lisp

Сегодня закончил с оптимизацией функции поиска пути персонажа по алгоритму A* — теперь уже ни в самой функции, ни в её окрестностях улучшать в плане производительности нечего, всё вылизано до блеска. В итоге путь в сложном лабиринте с большим количеством длинных коридоров и поворотов на 180° со скриншота находится чуть меньше, чем за половину миллисекунды. Это, наверное, не очень впечатляющий результат для какой-нибудь RTS, но в столь специфичном жанре нужны будут свои хаки вроде кэширования путей или предварительного вычисления графа с компонентами связности для карты и запуска A* на нём. Если сравнивать с моим кринжовым опытом реализации A* на лиспах четырёхлетней давности, который глючный, дёрганый и тормозной, сейчас получился прямо огонь 🔥