Да, колоночное представление есть в roadmap. MVP уже есть, но пока не открывали.
Правда, на колоночное хранение мы пока смотрели в первую очередь со стороны компактности, то есть это уже не чистый zero-copy. Там скорее итератор с proto-like интерфейсом, который декодирует данные во время обхода repeated-поля.
При этом действительно бывают места, где колонку выгодно читать именно zero-copy. Так что движение, думаю, будет встречным: у обычных layout'ов со временем появятся варианты с упором на компактность, а у колоночного — наоборот, к компактному режиму добавим zero-copy, и сделаем это перед тем, как его открывать.
Да, в этом и идея: оставаться на proto-схеме и получить zero-copy чтение с mmap-совместимым форматом.
Если нужно вернуться в обычный protobuf, придётся переложить данные из YaFF обратно в protobuf wire format. Для этого мы генерируем по схеме функции конвертации, так что по коду это просто, но не бесплатно по перформансу.
Конкретные сроки про Go пока не готовы назвать. Выигрыш ожидаем, что будет сопоставим с переездом с обычного protobuf на zero-copy формат (то есть основной эффект даст само отсутствие парсинга). Точнее можно будет сказать с бенчмарками.
Плоская база в памяти и передача данных как раз удачный юзкейс YaFF, у нас он активно используется. Когда нужно переварить большой объём (например, отфильтровать много кандидатов по запросу) используем плоское представление, а когда выбрали небольшое подмножество, его уже не так дорого сконвертировать в protobuf и отправить дальше.
Да, действительно нужно учитывать ещё настройки OS. Сейчас, насколько получилось нагрепать, по дефолту не включается A бит на macOS.
Мы пока пошли по безопасному пути с memcpy, поэтому оставили этот момент на откуп компилятору. Пока не подводит из-за ограниченной зоны применения, возможно, переключимся на подход с альтернативными способами (подобный lz4), если где-то всё-таки очень нужно будет.
Локально с clang на макбуке у меня чтения транслируются в обычные load, так что предполагается SCTLR_EL1.A равным нулю.
Спасибо за вопрос, в посте действительно про Cap'n'proto не упоминали.
Основных отличия два:
YaFF целится быть расширением для Protobuf экосистемы, у Cap'n'proto своя экосистема с отдельной схемой и правилами. Поэтому переход на Cap'n'proto (как и на FlatBuffers) для крупного сервиса означает полноценную сложную миграцию, с YaFF тут проще за счет переиспользования proto-схем и конвертации с proto.
YaFF не привязывается к какому-то отдельному layout и заточен под адаптивность, в отличие от фиксированного варианта в Cap'n'proto. Сейчас реализована только пара layout с упором на скорость чтения, но следующим шагом перейдем к реализации вариантов с упором на компактность.
То есть это разные подходы в целом. У Cap'n'proto отдельная экосистема, а YaFF скорее расширение (в каком-то смысле даже кодек) для Protobuf.
Речь в посте скорее про то, что мы не завязываемся на поддержку нетиповых для бэкенда архитектур (старые ARM и различные embedded-платформы).
На макбуках реализуется ARMv8+ (который уже умеет эффективно работать с невыровненным чтением), так что там всё работает корректно. В CI-матрицу пока не добавляли, но локально тестировали.
Она там есть в самом конце. Сейчас ещё раз отдельно вставлю.
Возможно, череда улучшений приведет к тому, что мы получим мощную библиотеку с алгоритмами, а программа станет приятной демкой для неё (Как PathFinding.js, только лучше).
Это в миллисекундах.
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Про JPS спасибо за совет, обязательно введу какое-нибудь обозначение.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Gif #1
Здесь вы на 100% правы
Gif #2
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
Тогда будет необходимо реализовывать длинную арифметику + во всех статьях используются именно такие методы подсчета, а планировалось, что программу нужно использовать в связке со справочным материалом. Следовательно, чтобы пользователю было удобно и привычно, я поставил такие величины
JPS тоже рекурентно просматривает множество клеток, но он не совершает с ними много операций(не заносит в открытий и закрытый список, не проверяет соседей, не вычисляет F, G, H), а лишь вызывает рекурсивную функцию далее, пока точка не будет соответствовать правилам перхода, это и значительно увеличивает скорость поиска. Об этом можно прочитать по ссылке из поста. Цвет в свою очередь показывает принадлежность закрытому(желтый) и открытому(синий) спискам, поэтому все честно)
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.
В этой программе пользователь может запустить правило руки только на самом простом лабиринте без циклов и галерей, поэтому правило руки всегда будет давать верное решение. Да и добавлял я его просто для введения в лабиринты и поиск пути.
Это связано с тем, что для Дейкстры и A* мы используем стоимость единичного перехода горизонталь и вертикаль 10, а диагональ 14, потом делим общий результат на 10. А в JPS мы более точно считаем 1 для горизонтали и вертикали, и sqrt(2) для диагонали. Делалось это для демонстации того, что можно по разному считать: для Дейкстры и AStar'а быстрее, но менее точно, а т.к. JPS сам очень эффективный и быстрый, можем пожертвовать капелькой времени, ради точности. Я хотел об этом сказать, но забыл) Спасибо, что напомнили
Да, колоночное представление есть в roadmap. MVP уже есть, но пока не открывали.
Правда, на колоночное хранение мы пока смотрели в первую очередь со стороны компактности, то есть это уже не чистый zero-copy. Там скорее итератор с proto-like интерфейсом, который декодирует данные во время обхода repeated-поля.
При этом действительно бывают места, где колонку выгодно читать именно zero-copy. Так что движение, думаю, будет встречным: у обычных layout'ов со временем появятся варианты с упором на компактность, а у колоночного — наоборот, к компактному режиму добавим zero-copy, и сделаем это перед тем, как его открывать.
Да, в этом и идея: оставаться на proto-схеме и получить zero-copy чтение с mmap-совместимым форматом.
Если нужно вернуться в обычный protobuf, придётся переложить данные из YaFF обратно в protobuf wire format. Для этого мы генерируем по схеме функции конвертации, так что по коду это просто, но не бесплатно по перформансу.
Конкретные сроки про Go пока не готовы назвать. Выигрыш ожидаем, что будет сопоставим с переездом с обычного protobuf на zero-copy формат (то есть основной эффект даст само отсутствие парсинга). Точнее можно будет сказать с бенчмарками.
Плоская база в памяти и передача данных как раз удачный юзкейс YaFF, у нас он активно используется. Когда нужно переварить большой объём (например, отфильтровать много кандидатов по запросу) используем плоское представление, а когда выбрали небольшое подмножество, его уже не так дорого сконвертировать в protobuf и отправить дальше.
Да, действительно нужно учитывать ещё настройки OS. Сейчас, насколько получилось нагрепать, по дефолту не включается A бит на macOS.
Мы пока пошли по безопасному пути с memcpy, поэтому оставили этот момент на откуп компилятору. Пока не подводит из-за ограниченной зоны применения, возможно, переключимся на подход с альтернативными способами (подобный lz4), если где-то всё-таки очень нужно будет.
Локально с clang на макбуке у меня чтения транслируются в обычные load, так что предполагается SCTLR_EL1.A равным нулю.
Спасибо за вопрос, в посте действительно про Cap'n'proto не упоминали.
Основных отличия два:
YaFF целится быть расширением для Protobuf экосистемы, у Cap'n'proto своя экосистема с отдельной схемой и правилами. Поэтому переход на Cap'n'proto (как и на FlatBuffers) для крупного сервиса означает полноценную сложную миграцию, с YaFF тут проще за счет переиспользования proto-схем и конвертации с proto.
YaFF не привязывается к какому-то отдельному layout и заточен под адаптивность, в отличие от фиксированного варианта в Cap'n'proto. Сейчас реализована только пара layout с упором на скорость чтения, но следующим шагом перейдем к реализации вариантов с упором на компактность.
То есть это разные подходы в целом. У Cap'n'proto отдельная экосистема, а YaFF скорее расширение (в каком-то смысле даже кодек) для Protobuf.
Речь в посте скорее про то, что мы не завязываемся на поддержку нетиповых для бэкенда архитектур (старые ARM и различные embedded-платформы).
На макбуках реализуется ARMv8+ (который уже умеет эффективно работать с невыровненным чтением), так что там всё работает корректно. В CI-матрицу пока не добавляли, но локально тестировали.
Время считают QTimer'ы, один считает общее время, второй считает время на паузы(отрисовка, переходы функций). Если использовать один и постоянно тормозить его, получалось вообще неточно. Эта часть статистики остро нуждается в доработке, желательно поискать какую-нибудь библиотеку для этого или, ещё лучше, попробовать QDebug или QTest для этого.
Это мой первый проект выше уровня тетриса :)Но если так положено приложу в ближайшее время.
Дейкстра реализовывалась строго по «учебникам», поэтому поиск должен быть верным. Приложу парочку гифок для понятности.
Здесь вы на 100% правы
Здесь расстояние между точками тоже, только появляется стена(вверх короче чем вниз). Пока левая сторона обходит стену, правая продолжает расширятся.
Мы могли бы и прерывать поиск в одну сторону, когда видим, что превышен радиус, в котором находится выход, но одним из ключевых преимуществ Дейкстры является то, что не нужна вообще никакая информация о выходе, и, добавляя проверку радиуса, мы это теряем.
Также этот эффект наблюдается и в проверенной многими библиотеке PathFinding.js (на случай, если вы мне не верите, можете попробовать :) ). Это объясняется тем, что когда мы натыкаемся на стену, например, слева (как на гифке), поиск влево временно прекращается, поэтому и нарушается равенства радиуса поиска во всех направлениях.
А Декстра слева ушел далеко, потому что правой стороне надо было еще искать путь обогнуть стену. Если оставить две точки на пустом поле ваше утверждение будет верным, как только появляются препятсвия, Дейкстра пойдет неравномерно.