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

В общем, выбрал я себе тему курсовой работы на 3-й курс. Озвучивать её не буду, но в целом это распределённая система с фокусом на безопасность, E2EE, offline-first и другие важные концепты. В ходе проектирования я задумался:

А что, если часть инструментов я напишу сам и конкретно под свою задачу?

В моей голове это звучало так: публичные библиотеки обычно пытаются охватить как можно больше функционала, чтобы угодить всем, а мне не хотелось тащить лишние зависимости, которые я даже не буду использовать. Заодно и попрактикуюсь.

Вступление

Собственно говоря, я написал сервер на Java и взялся за клиентскую часть. В планах было сделать основное ядро клиента на C++, а рендерить всё через Dart/Flutter. И тут я совершенно случайно узнал про Rust. Слышал-то я о нём и раньше, но не особо понимал, зачем он нужен. Если вкратце — разобрался…

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

Модель данных

Я сразу понял, что буду хранить всё в векторах (Vec). Разделил их по типам в рамках структуры Content. Потом пришёл к концепции zero-copy и стал сохранять в векторах интервалы на типы разметки по глобальному офсету.

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

Парсер Markdown

Так удачно вышло, что именно в семестр написания парсера у меня шёл курс «Теория компиляторов», в рамках которого мы эти самые компиляторы и писали. Однако я отказался от AST в пользу плоской модели данных, а это не совсем то, чему учит академическая теория (как минимум в рамках вуза).

Процесс написания логики парсинга оказался тривиальным, поскольку я сознательно отказался от спецификации CommonMark. Не то чтобы для моей задачи она была избыточной — я просто посчитал, что некоторые её элементы редко встречаются в реальности (например, использование _ наравне с *, или ~~~ наравне с «`). Из-за этого я теряю обратную совместимость, но я за ней и не гнался.

В итоге получился рабочий парсер, полностью закрывающий задачи проекта. Замеры пропускной способности показали неплохие, но довольно скромные результаты. Точные цифры на тот момент не назову, но актуальные бенчмарки приведу ниже. Именно тогда я понял, что хочу сделать парсер по-настоящему быстрым.

Оптимизации

Я начал изучать этот вопрос и пришёл к нескольким вещам:

• Эвристики на преаллокацию по типам для каждого вектора. Казалось бы, можно было перейти на итераторы, лениво всё вычислять, а в конце вызывать .collect(). Но тогда я ещё слишком слабо знал Rust, и эта мысль пришла ко мне намного позже.

• Смена аллокатора. Поскольку эвристики дают лишь приблизительный результат, было принято решение заменить global_allocator на Mimalloc.

• Крейт memchr. Он дал отличный прирост при поиске спецсимволов за счёт векторного сканирования байтов. Однако масштабировать грамматику языка без ощутимой потери производительности стало трудно: этот крейт ограничен поиском до 3 байт за один проход. Тем не менее глупо отрицать, что моя линейная структура данных идеально подошла под memchr.

В итоге я получил первые сотни MiB/s в бенчмарках, но особого восторга не испытал.

Масштабирование грамматики через… оптимизацию?

С учётом того, что я отказался от спецификации CommonMark, поиска по трём байтам сразу должно было хватить с головой. Но мне не хватало. Вызывать отдельные инстансы memchr — дорого по производительности. Запускать их параллельно можно, НО теряется контекст синтаксиса, а это требует сложных архитектурных надстроек.

И тут я открыл для себя аббревиатуру SWAR. Это как SIMD, но без явного использования SIMD-инструкций — чистые битовые маски и математика. С SWAR падение пропускной способности при усложнении грамматики стало куда более плавным. Именно тогда на бенчмарках criterion я пробил свой первый заветный GiB/s на уже более богатой грамматике.

Был ли я рад? Снова нет. Код для курсовой готов, оставалось лишь описать его академическим языком. Но сам процесс оптимизации и решения проблем по ходу дела приносил куда больше удовольствия, и я решил двигаться дальше.

Уход от универсальных решений к декларативности

Высокие показатели производительности — это здорово, но я задался вопросом: ради чего всё это? Просто игрушка? Тогда я поставил перед собой новую задачу:

Найти структурные примитивы, присущие подавляющему большинству текстовых форматов данных.

За основу был взят тот же самый Markdown. Скажу честно: по сравнению с тем, что планировалось изначально, проект в его исходном виде не казался мне чем-то достойным курсовой работы, так что смена вектора выглядела логичной.

Основные структурные примитивы текстовых форматов данных

Выделить эти примитивы оказалось несложно — всё в рамках базовой логики:

• inline (внутристрочный примитив) — фрагменты текста, которые находятся внутри строк. Имеют спецсимволы конкретного типа, иначе — fallback.

• line (строчный примитив) — фрагменты, которые начинаются строго в начале строки и заканчиваются в её конце (целая строка).

• block (блочный примитив) — фрагменты текста, которые начинаются на одной строке, а заканчиваются на другой. Имеют спецсимволы конкретного типа, иначе — fallback.

Если спроецировать это на Markdown, то обычный текст — это inline fallback, а параграф — block fallback. Каждый примитив также имеет подтип simple, подробное описание этой архитектуры доступно в репозитории проекта, дабы не растягивать и без того не самую маленькую статью.

Основные правила парсинга

Структура понятна, но внутри каждого примитива действуют свои правила парсинга. Пара самых стандартных для inline-элементов:

• symmetric — один и тот же символ в одинаковом количестве служит как открывающим (слева), так и закрывающим (справа).

asymmetric — открывающий и закрывающий символы различаются.

key_value — классические ключ и значение с настраиваемым разделителем.

Есть и менее стандартное правило — chained, поддерживающее две пары спецсимволов для двух разных отрезков байтов (так реализована поддержка ссылок в Markdown). Оно также поддерживает префиксы для обработки изображений.

DSL

Собственно говоря, не буду затягивать, вот как выглядит описание подмножества Markdown:

define_parser!(Markdown {sep = b' ', eol = b'\n', tab = b'\t', escape = b'\\';inline {merge_simple = true;hard_break(b'\\', b' ', 2) => hard_breaks [500];on_trigger(b'*', b'`', b'[', b'<') {symmetric b'`' {parse_inside = false;balanced = false;1 => codes [80],}symmetric b'*' {parse_inside = true;balanced = false;1 => italics [40], 2 => bolds [40], 3 => bold_italics [80],}asymmetric b'<', b'>' {balanced = false;parse_inside = false;1 => autolinks [100],}chained: Link {| b'[', b']' | {parse_inside = false;balanced = false;} => text,| b'(', b')' | {parse_inside = false;balanced = false;} => url,prefix | b'!' | => is_image,} => links [100]}fallback => texts [10];}lines {line(b'#', max = 6) |n|:Heading { level: NonZeroU8::new(n).unwrap_or(NonZeroU8::MIN) }=> headings [200];line_simple(b'-' | b'*' | b'_', min = 3) |b|:ThematicBreak { kind: b }=> thematic_breaks [200];}blocks {block_simple {fence(b'`', min = 3) => fenced_codes [400];cont(b'>') => blockquotes [200];}block {(b'-' | b'*' | b'+') |b|:BulletItem { kind: b }=> bullet_items [80];num(b'0'..=b'9', end = b'.' | b')') |n, k|:OrderedItem { kind: k, num: n }=> ordered_items [80];}fallback => paragraphs [80];}});

Читаемость, возможно, не совсем идеальная. Числа в квадратных скобках [N] — это делители для эвристик. Конечный пользователь обычно лучше понимает специфику своих файлов и то, какие объёмы ему нужно парсить.

Что под капотом

Под капотом — месиво из макросов. Сам DSL вынесен в отдельный крейт в виде proc-macro define_parser!. Этот макрос разворачивается в два других:

• define_content! — определяет структуру данных <Имя>Content.

• parse_text! — генерирует правила парсинга под этот конкретный Content.

Помимо быстрого доступа, библиотека предоставляет методы для парсинга конкретных типов вне основного контекста. Например, можно вызвать метод find_bolds(&[u8]) — и он вернёт итератор со всеми интервалами, внутри которых этот тип находится.

Важный нюанс: интервалы указывают на чистые данные (без спецсимволов). То есть для *text* вернётся интервал (1, 5). Для извлечения как «грязных», так и «чистых» байтов из исходного среза генерируются отдельные методы для каждого типа.

Бенчмарки

Для тестов у меня есть 3 конфигурации, две из которых — это фичи, завязанные на portable_simd (доступны только в nightly-версии Rust). Тулчейн зафиксирован в репозитории через flake.nix. Если у вас процессор на архитектуре Zen 3 и выше, можно протестировать --features avx2, а для Zen 4+ доступна --features avx512(которая, лично мной, не тестировалась).

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

┌─ corpus: plain│ size: 280.17 MiB (293780000 bytes)│ elements: 2 (0.0 per KiB)│ span mem: 0.00 MiB (~0.0% of input, 8 B/span lower bound)┌─ corpus: hot│ size: 75.40 MiB (79060000 bytes)│ elements: 6500000 (84.2 per KiB)│ span mem: 49.59 MiB (~65.8% of input, 8 B/span lower bound)┌─ corpus: heavy│ size: 116.66 MiB (122322000 bytes)│ elements: 12600000 (105.5 per KiB)│ span mem: 96.13 MiB (~82.4% of input, 8 B/span lower bound)

Сами тестовые корпуса синтетические. В реальности разметка обычно менее плотная, поэтому на реальных данных масштабирование будет более объективным.

parse/plain/full time: [105.96 ms 106.08 ms 106.21 ms]thrpt: [2.5762 GiB/s 2.5793 GiB/s 2.5822 GiB/s]parse/hot/full time: [97.604 ms 97.740 ms 97.885 ms]thrpt: [770.27 MiB/s 771.40 MiB/s 772.48 MiB/s]parse/heavy/full time: [176.51 ms 176.74 ms 176.98 ms]thrpt: [659.14 MiB/s 660.03 MiB/s 660.89 MiB/s]

Выше приведены результаты без использования portable_simd.

Fuzz-тестирование

Поскольку статья получается объёмнее, чем планировалось, кратко: 1 поток, включённый санитайзер (хотя unsafe в коде нет, для надёжности). Около 104 млн итераций, ((35k exec/s**, cov = 841.

Заключение

Курсовую работу я уже успешно защитил и даже релизнул первую версию, но эйфории от результата пока нет. Я вижу огромный роадмап, так что проект далёк от завершения. Название выбрано со смыслом — meon (привет философии, в которую меня влюбили на втором курсе).

Из минусов: проект сложно расширять и поддерживать из-за тысяч строк макросов. Ну и время компиляции, само собой, вырастает.

Исходный код проекта, ссылки на crates.io и подробную документацию можно найти в репозитории: GitHub

Открыт для критики и предложений.