Как я случайно написал что-то быстрое и декларативное (на Rust)

[Cheater]

2.5762 GiB/s

Живая иллюстрация анекдота про блондинку, печатающую 600 символов в минуту.:) Markdown не плоский, например цитаты могут быть вложены друг в друга, как вы это представите плоским массивом слайсов? Если при парсинге не собирать AST, естественно инпут можно жрать гигабайтами в секунду, но то, что спарсено, это будет не markdown, а какое-то его упрощённое подмножество/диалект. Сделать производительный парсинг легко; трудно (невероятно трудно) организовать структуру данных для AST, которая показывает приемлемую производительность при редактировании.

был необходим мгновенный доступ к конкретным типам данных. По этой причине pulldown-cmark я сразу отсёк

При чём здесь тогда производительность парсинга, если речь про производительность доступа? Вы можете спарсить md неэффективным алгоритмом за O(N!) но выдать структуру данных с доступом за O(1). Ну и в любом pull down парсере при наступлении события входа в элемент можно просто взять и заполнять свою структуру индексов какую хочешь. В т.ч. индексировать куски текста с данным типом форматирования, как в вашем случае.

ps: откуда у вас возьмётся инкрементальный репарсинг если на вход поступает весь текст? Инкрементальный репарсинг возможен только если парсер общается с редактором, который говорит ему, в какой позиции произошло изменение и какое оно.

[Vgnapuga]

Markdown не плоский, например цитаты могут быть вложены друг в друга

А кто с этим спорит?

В моём случае вложенность определяется как интервал входящий в другой интервал. Все вектора отсортированы по стартовому оффсету, правда в данный момент вложенность ограничена лишь одним активным блоком, потому что это v0.1.0. Поверх всех этих векторов спокойно можно построить дерево или что надо.

Тут суть не в парсинге Markdown, а в подходе к парсингу. Минимизация аллокаций в куче + уменьшение ветвлений через вырожденный генерируемый автомат состояний + декларативность. Markdown парсинг, в данном проекте, - демонстрация факта работы конкретной архитектуры.

При чём здесь тогда производительность парсинга, если речь про производительность доступа?

- Замеры идут по пропускной способности на конкретных входных данных, с конкретной плотностью, с конкретными размерами. По вашему мои слова про нелинейность масштабирования при выходе за кэш процессора - про доступ к данным? Так что тут буквально оптимизирована запись в память на уровне архитектуры, если мы говорим про парсинг.

Про pulldown - там подход принципиально другой. pulldown-cmark ведёт итератор как event-stream. Это чисто физически не может вам обеспечить быстрый доступ к типу, потому что придётся бегать по всему итератору. И в итоге мы имеем - двухпроходный парсинг, который очевидно медленнее моего однопроходного, потом **N** количество `.next()` (с кучей ветвлений, если надо расфасовать каждый тип в свою структуру данных).

Я же специально уклонялся от сравнений с pulldown, потому что хоть он и другой архитектурно, но его суть в соответствии спецификации. Это просто несправедливо сравнивать. Я указал ограничения, я указал преимущества внутри данной модели, я дал бенчмарки.

[Cheater]

По вашему мои слова про нелинейность масштабирования при выходе за кэш процессора - про доступ к данным?

Ничего не понял. Вы продолжаете смешивать парсинг и доступ к данных внутри распарсенной структуры. Это 2 разных действия. Когда мне говорят “доступ к данным” я считаю что имелось в виду 2е действие.

pulldown-cmark ведёт итератор как event-stream. Это чисто физически не может вам обеспечить быстрый доступ к типу, потому что придётся бегать по всему итератору.

Ничего не понял. 1 раз проходимся по тексту любым парсером, хоть nom хоть pulldown-cmark, пусть он заполняет этот ваш struct MarkdownContent. Далее все гарантии по скорости доступа даёт MarkdownContent а не парсер.

[Vgnapuga]

Так вот именно я про то, что это вы смешиваете два уровня. Доступ к данным чисто физически не может замеряться пропускной способностью. Это вопрос сложности, а не пс.

И именно тут вытекает, что именно структура данных определяет сложность доступа к этим самым данным, верно. Но тут теперь важно смотреть не на конечный результат всей программы, а на то сколько шагов она делает и какие они уже по сложности. В моей реализации нет промежуточных шагов между парсингом и возможностью мгновенного доступа к типам. Если выводить данные в структуру после pulldown - эти шаги, очевидно, есть. Я даю доступ к типам из коробки без накладных расходов именно сверху самой реализации.

Почему это имеет значение? Потому что библиотеки работают не в вакууме. После парсинга данные сто процентов зачем-то нужны.

[Vgnapuga]

Про вот эту часть

ps: откуда у вас возьмётся инкрементальный репарсинг если на вход поступает весь текст? Инкрементальный репарсинг возможен только если парсер общается с редактором, который говорит ему, в какой позиции произошло изменение и какое оно.

• как на инкрементальность парсинга влияет то, поступил весь текст или дельта?

Вообще слабо понимаю к чему этот вопрос, если всё, что я писал про инкрементальность -

В рамках проекта мне необходимо редактирование данных, а значит, в идеале — и инкрементальный репарсинг. Поэтому я хотел отказаться от глобальных офсетов в пользу локальных (в рамках каждой строки). Но эту идею пришлось отложить, так как тогда я потерял бы возможность доступа к конкретным байтам данных за O(1).

Локальные оффсеты на одну строку позволили бы мне избавиться от вечного сдвигания всех индексов после изменённой части. Но, как я и указал, я бы лишился возможность быстрого доступа, потому что для этого самого доступа я был бы обязан вычислять длину всех строк до той, где находится то, что я достаю.

Да и в целом если опираться на то, что писал я в этой статье - Flutter проще воспринимал бы глобальные оффсеты, насколько мне известно.

[Cheater]

как на инкрементальность парсинга влияет то, поступил весь текст или дельта?

напишите пожалуйста псевдокодом, как вы понимаете работу инкрементального парсера, если входом является весь текст

[Vgnapuga]

Тут вам можно накидать бесчисленное множество вариантов. Если брать вот самый банальный из моей конкретной реализации - найти интервал внутри которого были изменения (а координаты изменения у нас есть, ибо тогда мы бы даже не знали об изменениях внутри буфера). Найти интервалы, в которые входит данный интервал. Перепарсить конкретно этот кусок. Вычислить смещения глобальных офсетов относительно старых данных. Прибавить дельту ко всем данным после.

Это ну вот самый очевидный и не самый оптимальный вариант. Я искренне не понимаю почему мы ведём диалог про инкрементальность. Там буквально было сказано что эта идея отложена на потом.