Интересно, но в моём случае, с учётом специфики Flutter, - мне необходимы глобальные офсеты. То есть это неизбежная часть + появятся ссылки в куче, от чего я так старательно убегал в своей архитектуре. Плюс достать тип - снова бегать по дереву. Но если строить это дерево уже после парсинга, а не в процессе, то может быть, но увеличит оверхед по оперативной памяти.
Если быть вообще честным - при текущей пропускной способности проще перепарсить абсолютно весь текст.
Тут ещё момент такой, что конкретно в моём случае - парсинг на клиенте. И там не будет больших файлов. Но в то же время я сделал из этого библиотеку и добавил поддержку инструкций 512 битных регистров, что уже намекает на серверное использование. А вот там может и могут быть какие-то большие файлы, хотя утверждать это не берусь.
Но с другой стороны - как часто на сервере нужен инкрементальный репарсинг? Что-то типа Google документов с общим доступом и CRDT? Редкость, я туда, как минимум пока что, не целюсь.
Тут вам можно накидать бесчисленное множество вариантов. Если брать вот самый банальный из моей конкретной реализации - найти интервал внутри которого были изменения (а координаты изменения у нас есть, ибо тогда мы бы даже не знали об изменениях внутри буфера). Найти интервалы, в которые входит данный интервал. Перепарсить конкретно этот кусок. Вычислить смещения глобальных офсетов относительно старых данных. Прибавить дельту ко всем данным после.
Это ну вот самый очевидный и не самый оптимальный вариант. Я искренне не понимаю почему мы ведём диалог про инкрементальность. Там буквально было сказано что эта идея отложена на потом.
Так вот именно я про то, что это вы смешиваете два уровня. Доступ к данным чисто физически не может замеряться пропускной способностью. Это вопрос сложности, а не пс.
И именно тут вытекает, что именно структура данных определяет сложность доступа к этим самым данным, верно. Но тут теперь важно смотреть не на конечный результат всей программы, а на то сколько шагов она делает и какие они уже по сложности. В моей реализации нет промежуточных шагов между парсингом и возможностью мгновенного доступа к типам. Если выводить данные в структуру после pulldown - эти шаги, очевидно, есть. Я даю доступ к типам из коробки без накладных расходов именно сверху самой реализации.
Почему это имеет значение? Потому что библиотеки работают не в вакууме. После парсинга данные сто процентов зачем-то нужны.
ps: откуда у вас возьмётся инкрементальный репарсинг если на вход поступает весь текст? Инкрементальный репарсинг возможен только если парсер общается с редактором, который говорит ему, в какой позиции произошло изменение и какое оно.
как на инкрементальность парсинга влияет то, поступил весь текст или дельта?
Вообще слабо понимаю к чему этот вопрос, если всё, что я писал про инкрементальность -
В рамках проекта мне необходимо редактирование данных, а значит, в идеале — и инкрементальный репарсинг. Поэтому я хотел отказаться от глобальных офсетов в пользу локальных (в рамках каждой строки). Но эту идею пришлось отложить, так как тогда я потерял бы возможность доступа к конкретным байтам данных за O(1).
Локальные оффсеты на одну строку позволили бы мне избавиться от вечного сдвигания всех индексов после изменённой части. Но, как я и указал, я бы лишился возможность быстрого доступа, потому что для этого самого доступа я был бы обязан вычислять длину всех строк до той, где находится то, что я достаю.
Да и в целом если опираться на то, что писал я в этой статье - Flutter проще воспринимал бы глобальные оффсеты, насколько мне известно.
Markdown не плоский, например цитаты могут быть вложены друг в друга
А кто с этим спорит?
В моём случае вложенность определяется как интервал входящий в другой интервал. Все вектора отсортированы по стартовому оффсету, правда в данный момент вложенность ограничена лишь одним активным блоком, потому что это v0.1.0. Поверх всех этих векторов спокойно можно построить дерево или что надо.
Тут суть не в парсинге Markdown, а в подходе к парсингу. Минимизация аллокаций в куче + уменьшение ветвлений через вырожденный генерируемый автомат состояний + декларативность. Markdown парсинг, в данном проекте, - демонстрация факта работы конкретной архитектуры.
При чём здесь тогда производительность парсинга, если речь про производительность доступа?
- Замеры идут по пропускной способности на конкретных входных данных, с конкретной плотностью, с конкретными размерами. По вашему мои слова про нелинейность масштабирования при выходе за кэш процессора - про доступ к данным? Так что тут буквально оптимизирована запись в память на уровне архитектуры, если мы говорим про парсинг.
Про pulldown - там подход принципиально другой. pulldown-cmark ведёт итератор как event-stream. Это чисто физически не может вам обеспечить быстрый доступ к типу, потому что придётся бегать по всему итератору. И в итоге мы имеем - двухпроходный парсинг, который очевидно медленнее моего однопроходного, потом **N** количество `.next()` (с кучей ветвлений, если надо расфасовать каждый тип в свою структуру данных).
Я же специально уклонялся от сравнений с pulldown, потому что хоть он и другой архитектурно, но его суть в соответствии спецификации. Это просто несправедливо сравнивать. Я указал ограничения, я указал преимущества внутри данной модели, я дал бенчмарки.
Интересно, но в моём случае, с учётом специфики Flutter, - мне необходимы глобальные офсеты. То есть это неизбежная часть + появятся ссылки в куче, от чего я так старательно убегал в своей архитектуре. Плюс достать тип - снова бегать по дереву. Но если строить это дерево уже после парсинга, а не в процессе, то может быть, но увеличит оверхед по оперативной памяти.
Если быть вообще честным - при текущей пропускной способности проще перепарсить абсолютно весь текст.
Тут ещё момент такой, что конкретно в моём случае - парсинг на клиенте. И там не будет больших файлов. Но в то же время я сделал из этого библиотеку и добавил поддержку инструкций 512 битных регистров, что уже намекает на серверное использование. А вот там может и могут быть какие-то большие файлы, хотя утверждать это не берусь.
Но с другой стороны - как часто на сервере нужен инкрементальный репарсинг? Что-то типа Google документов с общим доступом и CRDT? Редкость, я туда, как минимум пока что, не целюсь.
Тут вам можно накидать бесчисленное множество вариантов. Если брать вот самый банальный из моей конкретной реализации - найти интервал внутри которого были изменения (а координаты изменения у нас есть, ибо тогда мы бы даже не знали об изменениях внутри буфера). Найти интервалы, в которые входит данный интервал. Перепарсить конкретно этот кусок. Вычислить смещения глобальных офсетов относительно старых данных. Прибавить дельту ко всем данным после.
Это ну вот самый очевидный и не самый оптимальный вариант. Я искренне не понимаю почему мы ведём диалог про инкрементальность. Там буквально было сказано что эта идея отложена на потом.
Так вот именно я про то, что это вы смешиваете два уровня. Доступ к данным чисто физически не может замеряться пропускной способностью. Это вопрос сложности, а не пс.
И именно тут вытекает, что именно структура данных определяет сложность доступа к этим самым данным, верно. Но тут теперь важно смотреть не на конечный результат всей программы, а на то сколько шагов она делает и какие они уже по сложности. В моей реализации нет промежуточных шагов между парсингом и возможностью мгновенного доступа к типам. Если выводить данные в структуру после pulldown - эти шаги, очевидно, есть. Я даю доступ к типам из коробки без накладных расходов именно сверху самой реализации.
Почему это имеет значение? Потому что библиотеки работают не в вакууме. После парсинга данные сто процентов зачем-то нужны.
Про вот эту часть
как на инкрементальность парсинга влияет то, поступил весь текст или дельта?
Вообще слабо понимаю к чему этот вопрос, если всё, что я писал про инкрементальность -
Локальные оффсеты на одну строку позволили бы мне избавиться от вечного сдвигания всех индексов после изменённой части. Но, как я и указал, я бы лишился возможность быстрого доступа, потому что для этого самого доступа я был бы обязан вычислять длину всех строк до той, где находится то, что я достаю.
Да и в целом если опираться на то, что писал я в этой статье - Flutter проще воспринимал бы глобальные оффсеты, насколько мне известно.
А кто с этим спорит?
В моём случае вложенность определяется как интервал входящий в другой интервал. Все вектора отсортированы по стартовому оффсету, правда в данный момент вложенность ограничена лишь одним активным блоком, потому что это
v0.1.0. Поверх всех этих векторов спокойно можно построить дерево или что надо.Тут суть не в парсинге Markdown, а в подходе к парсингу. Минимизация аллокаций в куче + уменьшение ветвлений через вырожденный генерируемый автомат состояний + декларативность. Markdown парсинг, в данном проекте, - демонстрация факта работы конкретной архитектуры.
- Замеры идут по пропускной способности на конкретных входных данных, с конкретной плотностью, с конкретными размерами. По вашему мои слова про нелинейность масштабирования при выходе за кэш процессора - про доступ к данным? Так что тут буквально оптимизирована запись в память на уровне архитектуры, если мы говорим про парсинг.
Про pulldown - там подход принципиально другой. pulldown-cmark ведёт итератор как event-stream. Это чисто физически не может вам обеспечить быстрый доступ к типу, потому что придётся бегать по всему итератору. И в итоге мы имеем - двухпроходный парсинг, который очевидно медленнее моего однопроходного, потом **N** количество `.next()` (с кучей ветвлений, если надо расфасовать каждый тип в свою структуру данных).
Я же специально уклонялся от сравнений с pulldown, потому что хоть он и другой архитектурно, но его суть в соответствии спецификации. Это просто несправедливо сравнивать. Я указал ограничения, я указал преимущества внутри данной модели, я дал бенчмарки.