Часть иллюстраций сделана через скриншоты слайдов из Google Slides. :)
Остальное через GIMP. Мне этот редактор очень не нравится, но я к нему привык. Не рекомендую.
Самая последняя картинка повторяет стиль иллюстрации из этой статьи. Я накидал такую "карту" по 1 пикселю на клетку, потом заскейлил и добавил сетку. :)
Мне тоже было бы интересно, но я думаю этот эксперимент кто-то другой может провести. Бенчмарки для Go я выложил, как их запускать - тоже. Если идентично реализовать алгоритмы на плюсах, то оно ожидаемо будет быстрее.
Наверное вопрос скорее в том, есть ли на плюсах более хитрые либы для поиска пути. Скорее всего, есть (сомневаюсь, что я что-то принципиально новое делал), но это надо будет несколько просмотреть, собрать, позапускать. Мне это будет сделать значительно сложнее, чем практикующему плюсовику (я уже больше года на C++ не пишу). И на Rust стоит поискать, там же всё blazing fast. :D
Из любопытства можно добавить в сравнения реализацию AStar2D из Godot, она тоже на C++ написана.
Я пробую не очень привычный для себя формат, где я выбрасываю из статьи почти всё лишнее. Интересно, как вам такое зайдёт. В этой статье мне удалось удалить примерно 30% текста, который не добавлял той информации, которую нельзя было бы вывести из уже присутствующей.
Не то, чтобы я всегда не пытался лить поменьше воды, но здесь я удалял даже места "по делу". Тем не менее, они какие-то очень опциональные и без них осилить статью должно быть проще. А самым любопытным всё равно придётся в код заглянуть. :)
Уверен, что можно было бы ещё сильнее сжать статью и сохранить всю важную информацию. Но здесь уже конфликт с тем, что я хотел бы ограничить время, которое я трачу на написание статьи. :)
GenerationsMap именно что в этой статье и описан (ctrl+f "Разбор genMap"), я больше его нигде не видел. Да и название просто от себя такое придумал. Не знаю, как правильно эта штука называется.
Интересно, на хабре действительно никто не делал перевода этой статьи Расса?
К каждой статье кто-то приходит и ставит минус за низкий технический уровень материала. :D Демотивирует, конечно, но хрен с ним. Не понятно, какого именно технического уровня не хватает.
Да, более хаотичные доступы к памяти были бы тоже хорошим кейсом для бенчмарков. Я таких не делал, но замерял на задаче поиска пути, где операции с этой структурой не занимают 100% времени и где доступы хаотичнее. Там тоже измеримое ускорение получилось.
Предложенные бенчмарки могу попробовать и дописать их в статью чуть позже.
Сегодня я узнал, что markdown на хабре не поддерживает align для столбиков таблицы (штуки типа --: и :--). Переформатировал таблицу, так вроде бы стало понятнее, хотя всё равно не очень удобно, когда числовые значения слева.
Что именно недоумение вызывает? Мы сравниваем альтернативы: Unity и какой-нибудь Ebitengine. А не мёртвые биндинги для Godot.
В Ebitengine (единственный самый живой движок на Go) для шейдеров используется язык Kage. Для него нет редакторов.
Я лично не имею ничего против языка go.
А с чего вы взяли, что я имею? Я на Go уже больше 5 игрушек написал, если считать те, что дошли до релиза. Если бы мне совсем не нравилось, я бы этим не занимался. Просто надо понимать, что экосистема не такая зрелая, как в других альтернативах.
Предлагаю прекратить этот диалог. Как-то в нём мало пользы. Мне очень не нравится заход "я неудомеваю, как вы можете считать, что ...".
Речь идёт сугубо о разработке игр на Go. Не бекендов, не чего-то консольного, а именно графических игр с клиентом (!) на Go. У нас нет графического редактора шейдеров, нет графической IDE для разработки игр (в отличие от других языков, где обычно таки есть хотя бы один движок с IDE, типа Godot, Unity, Game Maker, etc). А с библиотеками есть трудности при поиске эффективной либы: есть около 4-5 библиотек для поиска пути (A*, greedy BFS), но все они слишком неэффетивные и для игруше не годятся, где есть квант времени на фрейм и в него надо уложиться. Если хотите, я могу продолжить список, чего ещё не хватает, но думаю и без этого моё уточнение понятно.
Пожалуйста, не упускайте контекст из виду. Если вам интересно погрузиться в разработку игр на Go и пообщаться на эту тему, приглашаю в чатик: https://t.me/go_gamedev
Красивое. У меня очень мало опыта с шейдерами, поэтому почти всегда вместо лаконичного преобразования получается какое-то императивное шаманство с пикселями и кучей if/else. :)
Я могу ещё в статью что-нибудь из шейдеров закинуть (только не дублируя то, что уже есть в ebitengine примерах), если будут пожелания. При этом на звание хорошего шейдерописца я претендовать не могу, поэтому оптимальных решений не ждите. :)
Фаззер для PHP/KPHP не вполне доделан, так что рановато пока говорить о результатах. Там сейчас очень плохой раннер, которые запускает генератор и проверяет результаты, а генератор более-менее нормальный. Какие-то проблемы нашлись, но хотелось бы большего.
В нашем конкретном случае есть ещё проверка того, что output у программ, запущенных на двух реализациях (компилируемый KPHP и интерпретатор PHP), одинаковый.
Как в эту картину вписываются генераторы программ, типа csmith, gosmith, phpsmith? Они генерируют вход для компилятора/интерпретатора, а потом проверяют output и крашнулся ли он или нет.
ktest гоняет бенчмарки со включенным JIT-компилятором в режиме PHP. В целом, разрыв стал меньше, хотя KPHP теперь тоже оптимизациями обрастает. Если интересно на недавние сравнения посмотреть, можете глянуть https://habr.com/ru/company/vk/blog/698532/ Там есть бенчмарки и сравнение PHP8+ с KPHP на задаче шаблонизации.
Идея интересная, я не сталкивался с такими решениями. Возможно потому что никогда не генерировал из шаблонов мегабайты данных. Обычно даже десятки вложенных шаблонов создают относительно скромные объёмы текста.
В целом можно сделать возможность потоковой обработки результатов шаблонизации. Вопрос в том, где эти точки передачи данных вставлять. Если слишком часто - будут какие-то мелкие куски и высокий overhead на эту логику. А вообще было бы любопытно на каких-то больших объёмах глянуть, будет ли там прирост скорости или нет. Потому что для средних шаблонов я почти уверен, что писать всё в строку будет быстрее.
Я немного расширил статью. У меня спросили, почему в исходниках KTemplate используются phpdoc комментарии вместо тайпхинтов. Ответ в том, что тайпхинты в этом случае могут вызвать измеримое замедление (цифры приведены в статье). Для KPHP разницы, откуда брать информацию о типах, нет, поэтому типизацию я проверяю при компиляции в KPHP, а при запуске на PHP считаем, что проверять типы уже не нужно, пусть в рантайме хотя бы немного быстрее будет работать. Быстрее Twig для PHP оно всё равно не будет, но по крайней мере отставание можно сократить.
Ещё добавил опции JIT, использованные для бенчмарков. Я пробовал opcache.jit=1235 и некоторые другие комбинации, но on оказался лучше всех. Считаю, что это оптимальный и разумный default.
Занимательный факт: если использовать KPHP, а не PHP, то подгрузить новый шаблон или изменить существующий без перекомеляции будет очень проблематично, ведь эти PHP-скрипты станут частью бинарника.
Движки типа KTemplate как раз решают это ограничение. Они реализуют ту малую часть динамизма в рантайме, которая нужна для задачи динамической шаблонизации. Если динамичные шаблоны не нужны, то можно и другие решения рассмотреть. KTemplate тут играет роль маленького компилятора и интерпретатора, который умеет прямо во время исполнения что-то новое собрать и запустить.
Внутри рантайма KPHP использовать что-то, что использует стандартный аллокатор ("системный"), может быть чревато утечками памяти.
Например, исполнение кода может быть прервано сигналом при таймауте. В этом случае управление перейдёт обработчику сигнала, который потом через getcontext переключится в сетевой контекст и... исполнение прерванного кода никогда не продолжится. Деструкторы всяких std::regex вызваны не будут.
Для того, чтобы использовать динамическую аллокацию памяти подобного рода нужно или критическую секцию выставить, чтобы сигнал в этот момент не прилетел, либо подменять аллокатор на скриптовый (примеры кода можно найти в самом рантайме). Память скриптового аллокатора автоматически чистится при завершении запроса.
Из относительно полезного, из статьи ушло (что смог вспомнить):
Совсем не разбираю альтернативы для размеров клеток в Grid (можно их по 1 или 4 бита делать)
Не расписываю как вместо 56 шагов получить 112 (взять 4 uint64)
Иллюстрации как работает bucket queue через серию push и pop с дампом состояния
Как эмулировать диагональные ходы, не меняя сам алгоритм
На пальцах разобранный способ строить маршрут, длиннее 56 шагов (инкрементально)
Краткое описание принципов работы generations map (для этого отдельная статья написана)
Описание того, почему
container/heapтакой плохой и почему надо брать генерики для minheapВсякие такие вот мелочи. Большая часть из этого была в слайдах, поэтому я не ощущаю невосполнимой утраты знаний в материале.
Часть иллюстраций сделана через скриншоты слайдов из Google Slides. :)
Остальное через GIMP. Мне этот редактор очень не нравится, но я к нему привык. Не рекомендую.
Самая последняя картинка повторяет стиль иллюстрации из этой статьи. Я накидал такую "карту" по 1 пикселю на клетку, потом заскейлил и добавил сетку. :)
Мне тоже было бы интересно, но я думаю этот эксперимент кто-то другой может провести. Бенчмарки для Go я выложил, как их запускать - тоже.
Если идентично реализовать алгоритмы на плюсах, то оно ожидаемо будет быстрее.
Наверное вопрос скорее в том, есть ли на плюсах более хитрые либы для поиска пути. Скорее всего, есть (сомневаюсь, что я что-то принципиально новое делал), но это надо будет несколько просмотреть, собрать, позапускать. Мне это будет сделать значительно сложнее, чем практикующему плюсовику (я уже больше года на C++ не пишу). И на Rust стоит поискать, там же всё blazing fast. :D
Из любопытства можно добавить в сравнения реализацию AStar2D из Godot, она тоже на C++ написана.
Я пробую не очень привычный для себя формат, где я выбрасываю из статьи почти всё лишнее. Интересно, как вам такое зайдёт. В этой статье мне удалось удалить примерно 30% текста, который не добавлял той информации, которую нельзя было бы вывести из уже присутствующей.
Не то, чтобы я всегда не пытался лить поменьше воды, но здесь я удалял даже места "по делу". Тем не менее, они какие-то очень опциональные и без них осилить статью должно быть проще. А самым любопытным всё равно придётся в код заглянуть. :)
Уверен, что можно было бы ещё сильнее сжать статью и сохранить всю важную информацию. Но здесь уже конфликт с тем, что я хотел бы ограничить время, которое я трачу на написание статьи. :)
GenerationsMap именно что в этой статье и описан (ctrl+f "Разбор genMap"), я больше его нигде не видел. Да и название просто от себя такое придумал. Не знаю, как правильно эта штука называется.
Интересно, на хабре действительно никто не делал перевода этой статьи Расса?
К каждой статье кто-то приходит и ставит минус за низкий технический уровень материала. :D
Демотивирует, конечно, но хрен с ним.
Не понятно, какого именно технического уровня не хватает.
Да, более хаотичные доступы к памяти были бы тоже хорошим кейсом для бенчмарков.
Я таких не делал, но замерял на задаче поиска пути, где операции с этой структурой не занимают 100% времени и где доступы хаотичнее. Там тоже измеримое ускорение получилось.
Предложенные бенчмарки могу попробовать и дописать их в статью чуть позже.
Сегодня я узнал, что markdown на хабре не поддерживает align для столбиков таблицы (штуки типа
--:и:--). Переформатировал таблицу, так вроде бы стало понятнее, хотя всё равно не очень удобно, когда числовые значения слева.Что именно недоумение вызывает? Мы сравниваем альтернативы: Unity и какой-нибудь Ebitengine. А не мёртвые биндинги для Godot.
В Ebitengine (единственный самый живой движок на Go) для шейдеров используется язык Kage. Для него нет редакторов.
А с чего вы взяли, что я имею? Я на Go уже больше 5 игрушек написал, если считать те, что дошли до релиза. Если бы мне совсем не нравилось, я бы этим не занимался. Просто надо понимать, что экосистема не такая зрелая, как в других альтернативах.
Предлагаю прекратить этот диалог. Как-то в нём мало пользы. Мне очень не нравится заход "я неудомеваю, как вы можете считать, что ...".
О, я только сейчас обратил внимание, что мы знакомы. :)
Разные аватарки на разных платформах делают своё дело. :)
Лучше тогда awesome-ebitengine приводить в качестве примера.
Речь идёт сугубо о разработке игр на Go. Не бекендов, не чего-то консольного, а именно графических игр с клиентом (!) на Go. У нас нет графического редактора шейдеров, нет графической IDE для разработки игр (в отличие от других языков, где обычно таки есть хотя бы один движок с IDE, типа Godot, Unity, Game Maker, etc). А с библиотеками есть трудности при поиске эффективной либы: есть около 4-5 библиотек для поиска пути (A*, greedy BFS), но все они слишком неэффетивные и для игруше не годятся, где есть квант времени на фрейм и в него надо уложиться. Если хотите, я могу продолжить список, чего ещё не хватает, но думаю и без этого моё уточнение понятно.
Пожалуйста, не упускайте контекст из виду. Если вам интересно погрузиться в разработку игр на Go и пообщаться на эту тему, приглашаю в чатик: https://t.me/go_gamedev
Красивое.
У меня очень мало опыта с шейдерами, поэтому почти всегда вместо лаконичного преобразования получается какое-то императивное шаманство с пикселями и кучей if/else. :)
Я могу ещё в статью что-нибудь из шейдеров закинуть (только не дублируя то, что уже есть в ebitengine примерах), если будут пожелания. При этом на звание хорошего шейдерописца я претендовать не могу, поэтому оптимальных решений не ждите. :)
Доклад посмотрю, спасибо!
Фаззер для PHP/KPHP не вполне доделан, так что рановато пока говорить о результатах. Там сейчас очень плохой раннер, которые запускает генератор и проверяет результаты, а генератор более-менее нормальный. Какие-то проблемы нашлись, но хотелось бы большего.
В нашем конкретном случае есть ещё проверка того, что output у программ, запущенных на двух реализациях (компилируемый KPHP и интерпретатор PHP), одинаковый.
Как в эту картину вписываются генераторы программ, типа csmith, gosmith, phpsmith? Они генерируют вход для компилятора/интерпретатора, а потом проверяют output и крашнулся ли он или нет.
ktest гоняет бенчмарки со включенным JIT-компилятором в режиме PHP.
В целом, разрыв стал меньше, хотя KPHP теперь тоже оптимизациями обрастает.
Если интересно на недавние сравнения посмотреть, можете глянуть https://habr.com/ru/company/vk/blog/698532/
Там есть бенчмарки и сравнение PHP8+ с KPHP на задаче шаблонизации.
Идея интересная, я не сталкивался с такими решениями.
Возможно потому что никогда не генерировал из шаблонов мегабайты данных.
Обычно даже десятки вложенных шаблонов создают относительно скромные объёмы текста.
В целом можно сделать возможность потоковой обработки результатов шаблонизации. Вопрос в том, где эти точки передачи данных вставлять. Если слишком часто - будут какие-то мелкие куски и высокий overhead на эту логику. А вообще было бы любопытно на каких-то больших объёмах глянуть, будет ли там прирост скорости или нет. Потому что для средних шаблонов я почти уверен, что писать всё в строку будет быстрее.
Я немного расширил статью. У меня спросили, почему в исходниках KTemplate используются phpdoc комментарии вместо тайпхинтов. Ответ в том, что тайпхинты в этом случае могут вызвать измеримое замедление (цифры приведены в статье). Для KPHP разницы, откуда брать информацию о типах, нет, поэтому типизацию я проверяю при компиляции в KPHP, а при запуске на PHP считаем, что проверять типы уже не нужно, пусть в рантайме хотя бы немного быстрее будет работать. Быстрее Twig для PHP оно всё равно не будет, но по крайней мере отставание можно сократить.
Ещё добавил опции JIT, использованные для бенчмарков. Я пробовал
opcache.jit=1235и некоторые другие комбинации, ноonоказался лучше всех. Считаю, что это оптимальный и разумный default.Занимательный факт: если использовать KPHP, а не PHP, то подгрузить новый шаблон или изменить существующий без перекомеляции будет очень проблематично, ведь эти PHP-скрипты станут частью бинарника.
Движки типа KTemplate как раз решают это ограничение. Они реализуют ту малую часть динамизма в рантайме, которая нужна для задачи динамической шаблонизации. Если динамичные шаблоны не нужны, то можно и другие решения рассмотреть. KTemplate тут играет роль маленького компилятора и интерпретатора, который умеет прямо во время исполнения что-то новое собрать и запустить.
Небольшое предостережение для читателей.
Внутри рантайма KPHP использовать что-то, что использует стандартный аллокатор ("системный"), может быть чревато утечками памяти.
Например, исполнение кода может быть прервано сигналом при таймауте. В этом случае управление перейдёт обработчику сигнала, который потом через getcontext переключится в сетевой контекст и... исполнение прерванного кода никогда не продолжится. Деструкторы всяких
std::regexвызваны не будут.Для того, чтобы использовать динамическую аллокацию памяти подобного рода нужно или критическую секцию выставить, чтобы сигнал в этот момент не прилетел, либо подменять аллокатор на скриптовый (примеры кода можно найти в самом рантайме). Память скриптового аллокатора автоматически чистится при завершении запроса.