Comments 41
Я пробую не очень привычный для себя формат, где я выбрасываю из статьи почти всё лишнее. Интересно, как вам такое зайдёт. В этой статье мне удалось удалить примерно 30% текста, который не добавлял той информации, которую нельзя было бы вывести из уже присутствующей.
Не то, чтобы я всегда не пытался лить поменьше воды, но здесь я удалял даже места "по делу". Тем не менее, они какие-то очень опциональные и без них осилить статью должно быть проще. А самым любопытным всё равно придётся в код заглянуть. :)
Уверен, что можно было бы ещё сильнее сжать статью и сохранить всю важную информацию. Но здесь уже конфликт с тем, что я хотел бы ограничить время, которое я трачу на написание статьи. :)
Крутая работа. Не знаю что вы выкинули, но читалось хорошо.
Из относительно полезного, из статьи ушло (что смог вспомнить):
Совсем не разбираю альтернативы для размеров клеток в Grid (можно их по 1 или 4 бита делать)
Не расписываю как вместо 56 шагов получить 112 (взять 4 uint64)
Иллюстрации как работает bucket queue через серию push и pop с дампом состояния
Как эмулировать диагональные ходы, не меняя сам алгоритм
На пальцах разобранный способ строить маршрут, длиннее 56 шагов (инкрементально)
Краткое описание принципов работы generations map (для этого отдельная статья написана)
Описание того, почему
container/heapтакой плохой и почему надо брать генерики для minheap
Всякие такие вот мелочи. Большая часть из этого была в слайдах, поэтому я не ощущаю невосполнимой утраты знаний в материале.
Не удержался и добавил краткий разбор github.com/kelindar/tile в самом конце. Эту библиотеку мне скинули уже после написания статьи. Эта библиотека во многом сделана гораздо лучше остальных рассматриваемых. Например, там хотя бы не используют container/heap, а ещё map с хорошим хинтом размера создают.
без лишней скромности, читалось как будто автор из вайред или хакерньюс на окладе
А графики и обложку сами или знакомый дизайнер? Фотошоп и похожий редактор, или сейчас научились простые картинки через простые программы вставлять?
А графики и обложку сами или знакомый дизайнер?
Часть иллюстраций сделана через скриншоты слайдов из Google Slides. :)
Остальное через GIMP. Мне этот редактор очень не нравится, но я к нему привык. Не рекомендую.
Самая последняя картинка повторяет стиль иллюстрации из этой статьи. Я накидал такую "карту" по 1 пикселю на клетку, потом заскейлил и добавил сетку. :)
сравните с какойто нормальной с++ библиотекой. Будет довольно интересно посмотреть.
Мне тоже было бы интересно, но я думаю этот эксперимент кто-то другой может провести. Бенчмарки для Go я выложил, как их запускать - тоже.
Если идентично реализовать алгоритмы на плюсах, то оно ожидаемо будет быстрее.
Наверное вопрос скорее в том, есть ли на плюсах более хитрые либы для поиска пути. Скорее всего, есть (сомневаюсь, что я что-то принципиально новое делал), но это надо будет несколько просмотреть, собрать, позапускать. Мне это будет сделать значительно сложнее, чем практикующему плюсовику (я уже больше года на C++ не пишу). И на Rust стоит поискать, там же всё blazing fast. :D
Из любопытства можно добавить в сравнения реализацию AStar2D из Godot, она тоже на C++ написана.
А почему остановились на 56 шагах а не 57? там два бита в размере совершенно никому не нужны же, плюс маскировка нужна только пока размер маленький...
Очень сомнительное ограничение в 56 на путь, так-то змейка на карте в 60x60 что-то порядка 1700 дает. В мире плюсов аллокацию из библиотеки можно избежать output iterator-ом, там такое на шаблонах бесплатно, в го так не выйдет.
Но ведь никто не заставляет брать именно такие значения. Я взял самый простой вариант, который работал для меня. Чтобы и исполнялось быстро, и код был несложным (маски в uint64 понять проще, чем в абстрактном bitset, который нужно ещё эффективно реализовать).
Вся идея выражается в:
Вместо координат {x,y} мы храним дельты, они компактные
А раз они компактные, можно в малое количество байт положить много шагов
Вместо 16 байтов под путь можно взять 32 и будет уже 112 сегментов.
А в bucket queue под это нужно будет взять пару uint64 под маску (так как встроенного int128_t в Go нет).
Я описал несколько принципов, которые можно крутить как хочется, но они в любом случае лучше, чем, например, массив для точек. Если на каком-то языке это можно ещё эффективнее реализовать - это же прекрасно.
Отдельно придётся проверять, не будет ли такой крупный (100+ бакетов) bucket queue уже хуже, чем minheap через один массив. Я таких замеров не делал, но перерасход памяти там будет расти с увеличением количества бакетов, а каждый дополнительный байт в маске может выражаться в более медленных push/pop.
А если оставаться в рамках 56 шагов, то размер клетки может быть разный, в либе есть маппинг из world координат (позиций) в клеточные. Можно матрицы разной гранулярности - мелкая сетка типа 32x32 для локального обхода препятствий и матрица покрупнее, чтобы какой-то более масштабный маршрут строить между ними.
Другой вариант - строить несколько частичных путей, где точка финиша первого маршрута будет стартом для второго. Для игр, где открытого пространства достаточно, это будет нормально работать.
И второй способ, который подойдёт для случаев, когда у нас очень много повторяющихся шагов типа up up up up.
Вместо 2 битов используем 3 бита на одну "единицу" информации. Дополнительный бит используем как префикс. И дальше выбираем под нужду, как кодировать там информацию. Для случая, когда повторы направлений очень частые, можно сделать такой encoding:
000 left
001 right
010 down
011 up
100 left+repeat
101 right+repeat
110 down+repeat
111 up+repeat
Для случая +repeat следующие 3 бита содержат количество+3 повторений (потому что 0 не имеет смысла, а 1-2 проще/эффективнее кодировать через отдельные 3 бита):
000 => 3 шага
001 => 4 шага
010 => 5 шагов
011 => 6 шагов
100 => 7 шагов
101 => 8 шагов
110 => 9 шагов
111 => 10 шагов
Так получится за 6 бит сохранить 10 шагов (в 3 раза больше).
Хотя тот же A* любит строить лесенки вида up left up left, и с ним это будет реже полезно.
Удалите статью мне лень её читать
А JPS не пробовали запилить/включить в бенчмаркинг? Интересно было бы посмотреть на результаты.
Jump point search - алгоритм поиска путей на сетчатых графах (который скипает много промежуточных вычислений по сравнению с A* и за счет этого на многих картах (но не на всех) оказывается ощутимо быстрее).
О таком раньше не слышал, спасибо.
Я в целом на эту тему уже несколько недель убил (сравнения, своя библиотека, статьи и доклады), поэтому в ближайшом времени точно не буду ещё глубже уходить. Мне же для игрушки это нужно было, следовательно делать игрушки важнее, чем посвятить свою жизнь задаче поиска путей. :D
Выбор библиотек на Go был не очень хорош, поэтому пришлось своё писать. Результаты сейчас достаточно удовлетворительны.
Так что я был бы очень признателен, если бы кто-то принял эстафету.
Меня тоже не покидает ощущение, что чем выше язык, тем больше ресурсы используются на переливание из пустого в порожнее. Однажды увидел тут на Хабре фрактал (множество) Мандельброта реализованный на чистом C. Чтобы понять, насколько быстрый алгоритм реализован там, запилил свой на Асм, с распараллеливанием расчётов в SIMD инструкциях процессора и в 8 потоков. Так вот, даже по сравнению с языком C, выигрыш был 5-6 раз. И это с выводом на экран. (Возможно, когда разгребу дела, выложу процесс написания и результат). Сам собой напрашивается вопрос - не многовато ли мы используем энергии процессоров просто на отопление помещений без какой-либо полезной работы.. Особенно это заметно на всяких, прости г-ди, python...
А вы статью то читали? :)
Я не с упрёком, но мне честно больно читать такие комментарии. Вы не поверите, но я старался, писав её. Я нашёл набор достаточно универсальных приёмов, которые можно использовать для более оптимальных библиотек поиска пути, которые очень редко используются. На это есть свои причины: мои трюки работают из-за введений ограничений. Но это же тоже здорово, когда можно найти такие ограничения, которые открывают портал в дополнительные оптимизации.
И да, даже на вашем любимом асме их можно применить и будет буст по сравнению с более прямолинейным подходом.
Я постараюсь описать, почему же статья вообще не про ограниченность Go, а про более фундаментальные вещи. Но это имеет смысл только если вы действительно хотите понять, какой посыл был в статье (как его воспринимать уже ваше дело). Дальше по пунктам.
Есть сотни способов представить матрицу проходимости и я показал один из них, который достаточно компактный и простой в реализации. В статье ещё есть ссылка на "страничный" подход и на Morton space-filling curve. Это всё потому, что да, иногда в либах используют и менее компактные, и менее эффективные структуры. Это не вина Go, на любом языке люди готовы везде воткнуть hashmap или обычный 2D array.
В 99% библиотек путь возвращается как набор точек, а не как value-объект из дельт. Этот принцип можно применить в любом языке и выигрыш будет везде.
Аналогично с generations map (ссылка есть в статье). Я вообще пока не нашёл, чтобы где-то применяли эту структуру. Чаще всего используют просто map. Кто-то берёт sparse map, но он тоже не оптимален.
Бакетная очередь приоритетов с битовой маской тоже не самая частая структура. У неё есть несколько вариаций, но используют её крайне редко в том числе из-за её ограничений. Но в задаче поиска пути её применить можно и буст ощутимый. Это тоже в любом языке будет работать, где у нас есть доступ к интринсикам или функциям типа "верни индекс первого ненулевого бита" (в Go есть такой интринсик, в C/C++ и подавно, а на асме можно напрямую инструкции вызвать, которые я в статье упомянул).
Конечно читал, просто именно про алгоритмическую оптимизацию сказать было нечего, а про ускорение работы программ в целом я любитель поговорить:)
Напомните, пожалуйста, где в С/С++ интринсик "верни индекс первого ненулевого бита"?
Сам бит легко: return x & ~(x-1), а как получить индекс без использования цикла?
https://gcc.gnu.org/onlinedocs/gcc-4.3.2/gcc/Other-Builtins.html
ctrl+f __builtin_ctz
Скорее всего это.
Спасибо! Не знаю, как реализовано в gcc, но я бы реализовал вот так. Индекс младшего ненулевого бита.
x &= ~(x-1);
return 16*!(x & 0xFFFF0000)
+ 8*!(x & 0xFF00FF00)
+ 4*!(x & 0xF0F0F0F0)
+ 2*!(x & 0xCCCCCCCC)
+ !(x & 0xAAAAAAAA);
Смысл интринсиков в том, что они часто мапятся на 1-2 машинные инструкции. В процессорах серии x86-64 (Intel, AMD64, ...) есть инструкция BSF, и, скорее всего, её вычисление будет быстрее, чем несколько операций выше. Когда дело касается низкоуровневых оптимизаций, всё же лучше использовать доступные для железа возможности.
Вот примерно такой машинный код (в виде ассемблера) будет для вашего решения:
mov rdx, rdi
xor ecx, ecx
neg rdx
and rdx, rdi
test edx, 4278255360
sete cl
xor eax, eax
test edx, 4294901760
sete al
sal eax, 4
lea eax, [rax+rcx*8]
xor ecx, ecx
test edx, 4042322160
sete cl
lea eax, [rax+rcx*4]
xor ecx, ecx
test edx, 3435973836
sete cl
and edx, 2863311530
lea eax, [rax+rcx*2]
cmp rdx, 1
adc eax, 0
cdqe
ret
И вот такой для интринсика (x86-64):
xor eax, eax
rep bsf eax, edi
ret
И для ARM тоже будет работать:
rbit r0, r0
movs r1, #0
clz r0, r0
bx lr
Это просто пример. Но вы сами можете проверить в godbolt. Главное не забыть передать условные -O3 и прочее.
Гипотетическую разницу в производительности посчитать можно через таблицы Агнера. Например, можно просуммировать latency первого и второго вариантов, а потом сравнить. BSF - не самая дешёвая операция (плюс там rep), но против нескольких других инструкций она будет выигрывать (в теории).
Можно эмпирически на какой-то машине побенчмаркать и разницу нащупать. Здесь стоит быть осторожным и не намерить шум.
В отсутсвии чего бы то ни было еще, gcc/clang компилируют в rep bsf: https://godbolt.org/z/38arb3x8r
Сегодня я что-то новое изучил: O_O https://pernos.co/blog/tzcnt-portability/
Опечатка. "!" надо удвоить или явно написать "!= 0".
Я просто оставлю это здесь https://youtu.be/4lbYrgoEE-g. Быстрый поиск пути в динамических условиях. Свяжитесь со мной если интересно. Автор молодец, проделал серьезную и кропотливую работу.
Прошу прощения за вопрос не по теме, а это опять на хабре что-то поломали, или вы не смоги в ABBR? Есть жеж специальный инструмент для этого...
А тут пойди ещё пойми, какие теги хабр разрешает, а какие вырезает. Про abbr не знал, сейчас попробую.
Заменил на abbr, но в некоторых местах, по ощущениям, стало едва заметно, что у текста есть декоратор. Хотя в среднем выглядит лучше.
Так в этом то и суть abbr, чтобы пояснять тем, кто не понял о чем суть. А то был тайтл у картинки, на которую я случайно жмякнул, и у меня распердолило её на весь экран десктопа. Не помню как там в старом редакторе, но в новом делается это красивенько, есть кнопочка
А в тексте потом вот так выделяется:
Я пишу статьи в markdown и вставляю через старый редактор.
И вот там хабр вырезает почти любые теги и я не находил списка что он поддерживает, а что - нет. Перебирать все теги довольно утомительно, а про abbr я, если честно, даже не знал. Я всегда делал tooltip через title у span.
Так что вот, узнал что-то новое. Теперь буду юзать в новых статьях!
А ещё для фотографий лучше использовать JPG, а не PNG.
Вроде бы в некоторых редких случаях PNG весит меньше, чем JPG, поэтому видимо неплохой тактиков будет брать в каждом случае то, что занимает меньше байтиков.
Достаточно вот такие сложные картинки сжимать в JPG, не прогадаете:
https://habrastorage.org/webt/g_/bv/ix/g_bvixdflizisyhmn9la7zeg4k4.png
Самый быстрый поиск пути на Go без аллокаций и СМС