awh::regex и Grok
Свой движок регулярных выражений с порождением машинного кода и надстройка разбора журналов над ним. Писался, чтобы убрать из AWH библиотеку PCRE2, — и убрал: штатная сборка о ней не знает, а эталон остался только ради сверки.
Быстрее PCRE2 почти везде, а на «Эльбрусе» в разы
Пять способов приложить выражение к тексту
Движок выбирает способ по свойствам выражения и текста, а не держит один на все случаи.
| Способ | Когда | Что делает |
|---|---|---|
| Prefilter | до всякого автомата | набор допустимых начальных байтов и обязательный литерал: участки текста пропускаются без запуска автомата |
| DFA | нужен ответ «есть или нет» | состояния строятся по мере надобности, один проход по тексту |
| Pike | нужны границы групп | все состояния разом, захваты за линейное время — без взрыва на подобранном выражении |
| Backtrack | вне регулярного подмножества | обратные ссылки, просмотр вперёд и назад, атомарные группы, рекурсия |
| Codegen | ARM64, x86-64 и e2k | программа выражения превращается в машинный код сопоставителя |
Собранное выражение после сборки не изменяется и разделяется потоками без замков; рабочее состояние сопоставления у каждого потока своё.
Перемещаемый код — решение, принятое до первой строки
Всё, что лежит вне порождённого кода — таблицы, подпрограммы разбора, классы символов, — достигается смещением от одного указателя. Прямых адресов в коде нет, и потому он сохраняется вместе с выражением: на миллионе выражений это двенадцать секунд, не потраченных при запуске.
Участок памяти никогда не бывает записываемым и исполняемым разом; на Apple ARM64 — через MAP_JIT, на OpenBSD — с метками BTI.
Рычаг кода над нашим же толкователем с каждой правкой толкователя убывает, и это мера успеха: прежде он доходил до ×153, ныне наибольший — ×34,7. Толкователь догнал код там, где отставал от него в десятки раз.
| Выражение | Рычаг кода |
|---|---|
| \w+(?=@) | ×34,7 |
| (\w+)@(\w+)\.(\w+) | ×32,6 |
| (?>\w+)@\w+ | ×28,0 |
| .*?needle | ×14,0 |
| Content-Length | ведёт отбор |
Сорок пять сценариев, две меры
Сопоставлений в секунду; ARM64 (Apple M4 Max), обе стороны собраны с -O3. Сличаются порознь две пары: наш машинный код против машинного кода PCRE2 и наш толкователь против её толкователя. Смешивать их нельзя: прежде единственная мера — код против кода — скрывала отставание толкователя, и вскрылось оно лишь на «Эльбрусе».
| Машинный код против машинного кода | AWH | PCRE2 | Доля |
|---|---|---|---|
| .*needle | 113 314 | 8 935 | 12,68 |
| (?>\w+)@\w+ | 9 086 432 | 2 429 420 | 3,74 |
| (?:[a-z]* ?)*dog | 42 179 841 | 11 491 479 | 3,67 |
| alpha|bravo|charlie|delta|echo|foxtrot | 11 405 | 6 201 | 1,84 |
| ^(GET|POST) (\S+) HTTP/(\d)\.(\d)$ | 105 297 795 | 59 989 513 | 1,76 |
| (\w+) \1 | 7 014 364 | 4 372 819 | 1,60 |
| \((?:[^()]|(?R))*\) | 28 721 849 | 25 997 930 | 1,10 |
| (?:HT|TP)/1 | 71 259 965 | 84 772 703 | 0,84 |
| Толкователь против толкователя | AWH | PCRE2 | Доля |
|---|---|---|---|
| (?:fox|dog)trap | 212 390 | 2 629 | 80,77 |
| \bneedle\b | 210 046 | 10 329 | 20,33 |
| .*needle | 73 076 | 5 104 | 14,32 |
| Content-Length | 122 768 379 | 24 091 306 | 5,10 |
| \((?:[^()]|(?R))*\) | 2 409 010 | 1 652 545 | 1,46 |
| (?:[a-z]+/)+v1 | 16 252 673 | 22 992 913 | 0,71 |
Машинным кодом: быстрее PCRE2 в 37 сценариях из 41, из четырёх оставшихся три — 0,99, заметно уступаем лишь в (?:HT|TP)/1; медиана доли 1,18. Толкователем: впереди в 21 сценарии из 45, вровень в 24, позади — ни в одном; медиана доли 1,46. «Впереди» — доля от 1,5, «позади» — ниже 0,67. Сборка выражения у нас в 2,3 раза дороже (0,44 от PCRE2): строятся две программы — прямая и обратная — и выражение разбирается глубже; собирается оно однажды, прикладывается миллионы раз.
Машинный код под «Эльбрус», которого нет у PCRE2
Порождатель обучен набору команд e2k (Эльбрус-8С2, lcc): 23 метода посредника, кодировщик сверен с ассемблером стенда байт в байт. У PCRE2 порождение под эту архитектуру невозможно вовсе, поэтому здесь наш код сличается с её толкователем.
| Выражение | Наш код | PCRE2 | Доля |
|---|---|---|---|
| (?:fox|dog)trot | 3 753 | 109 | 34,4 |
| \w+(?=@) | 132 249 | 5 765 | 22,9 |
| (?>\w+)@\w+ | 210 074 | 12 330 | 17,0 |
| (\w+)@(\w+)\.(\w+) | 17 223 | 1 030 | 16,7 |
| .*needle | 3 007 | 216 | 13,9 |
| [0-9]{3,5} | 1 032 221 | 1 131 070 | 0,91 |
Итог: впереди в 39 сценариях из 41, медиана доли 6,6. Толкователи между собой: впереди в 22, вровень в 23, позади — ни в одном.
Собранные выражения — без повторного разбора
Образ памяти
Программа выражения пишется как есть, восстановление — установка обзора на участок записи без размещения и копирования.
Недоверие к записи
Проверяются все адреса переходов, классы, ячейки и номера групп: испорченная запись — отказ, а не блуждание по памяти.
Шифрование и срок
Шифрование и сжатие обработчиками потребителя, срок годности записи, опознание машины и набора команд.
Двадцать стендов сверки и одно намеренное расхождение
| Стенд | Сличений | Расхождений |
|---|---|---|
| свойства Юникода, 1 225 свойств | 1 362 278 400 | 0 |
| сокращённые классы символов | 26 689 536 | 0 |
| границы совпадения на наборе выражений | 112 261 | 0 |
| вердикт и обратный проход | 236 498 | 0 |
| приём и отклонение выражений | 200 000 шаблонов | 0 |
| графемные кластеры | 48 218 624 | 69 131 |
Графемы разбиваются по действующей редакции UAX #29, а таблица PCRE2 отстаёт от неё в трёх правилах. Два отдельных стенда показывают, что расхождение ограничено этими правилами: у обоих ноль расхождений на тех же 48 млн сличений.
Разбор журналов именованными шаблонами
Реестр шаблонов, разворот ссылок вида %{ИМЯ:поле:вид} в регулярное выражение и извлечение полей в JSON.
grok.build("%{IP:client} %{WORD:method} %{URIPATHPARAM:request} %{INT:code:int}"); // 192.168.1.10 GET /api/v1/orders?id=17 200 {"client":"192.168.1.10","method":"GET","request":"/api/v1/orders?id=17","code":200}
- Ссылки разворачиваются текстом, а не вызовом подшаблона: сборщику открыто всё дерево, и работают и отбор начальных байтов, и порождение кода.
- Названия полей шире имён групп — дефис, точка, повторы: %{IP:src-ip}:%{INT:src.port}.
- Число — только по объявленному виду. Номер версии и код с ведущим нулём остаются текстом, а вывод — правильным JSON.
- Ошибки — отказом сборки: несуществующий шаблон и зацикленные ссылки не проходят молча.
Разбор по шаблонам Grok есть и в онлайн-конвертере ACU: строку журнала можно превратить в JSON, XML или YAML прямо в браузере.