Аннотация
ВВЕДЕНИЕ 1
1. Описание 3
1.1. Обработка текста при помощи регулярных выражений 3
1.1.1. Многострочные шаблоны в регулярных выражениях 4
1.2. Решение проблемы обработки текстового потока 4
1.3. Конечные автоматы как способ представления регулярных
выражений 6
1.4. Сравнительная характеристика библиотек регулярных выражений 8
2. Особенности реализации 9
2.1. Менеджер памяти 9
2.2. Парсер 10
2.3. Оптимизация AST 13
2.4. Компиляция AST в промежуточное представление 14
2.4.1. Сопо ставление с сохранением контекста 22
2.5. Формирование целевого представления 23
2.5.1. JIT 27
3. Сравнение производительности 36
ЗАКЛЮЧЕНИЕ 41
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ И ЛИТЕРАТУРЫ 42
Регулярные выражения - последовательности символов, определяющие шаблоны поиска по тексту и широко применяющиеся для первичного анализа текстов на предмет наличия определенных закономерностей и извлечения информации из них, обработки и форматирования. С ростом вычислительных мощностей растут и объемы обрабатываемых данных, естественным образом постанавливая задачу эффективной их обработки, в первую очередь эффективной по памяти. Решения этой задачи сводятся к обработке данных по частям, сохраняя в оперативной памяти лишь необходимую их часть. В языках программирования подпрограммы, выполняющие с регулярными выражениями, обычно оформляются в виде библиотек. Программный интерфейс, предоставляемый такими библиотеками, будем называть «потоковым». Напротив, программный интерфейс, выполняющий обработку исключительно текста целиком, будем называть «классическим», поскольку именно такие интерфейсы появились первыми. Важно отметить, что данные можно обрабатывать по частям (обычно построчно) и при помощи классических интерфейсов - ценой значительного усложнения программы и невозможности корректно обработать данные в ряде случаев.
Потоковые интерфейсы оказываются необходимы уже при достаточно малых размерах обрабатываемых данных. Примером может послужить текстовый редактор vis, в котором текст представлен в виде двусвязного списка буферов [1]. Такое представление позволяет эффективно реализовать множественные вставку и удалению, редактирование при помощи нескольких курсоров и операции над несколькими выделенными областями разом и, в отличие от, например, представления текста в виде массива строк, не вызывает просадок производительности при увеличении длины строк. Поиск по такому представлению текста невозможен с применением классических интерфейсов библиотек регулярных выражений.
Потоковые интерфейсы необходимы и при обработке потоков данных, поступающих небольшими порциями - например, при выполнении аудита системы на признаки типовых атак посредством мониторинга системного журнала. Схожую задачу выполняет утилита monit, анализирующую вывод процесса и выполняющую заданные пользователем действия в соответствии с результатами анализа. Эта утилита часто используется для автоматизации повседневных задач в Unix-подобных системах. Она выполняет построчный разбор ввода, что приводит к необходимости хранения промежуточной информации о текущем состоянии при разборе многострочных шаблонов. Применение поточного разбора позволило бы избежать этого.
Проведенный сравнительный анализ показал, что число предоставляющих потоковый интерфейс библиотек регулярных выражений невелико, а предоставляемый ими интерфейс в подавляющем большинстве случаев осложняет эффективное управление памятью, что накладывает ограничения на размер обрабатываемых текстов.
Разработана библиотека, предоставляющая потоковый интерфейс требуемого вида, что обеспечивает хранение в оперативной памяти лишь требуемого для извлечения совпадения участка текстового потока. Применение технологии JIT-компиляции, ценой дополнительных затрат памяти и времени на компиляцию в исполняемый код, позволяет кратно ускорить поиск совпадения в текстовом потоке по сравнению с более широко распространенным подходом использования байткода. При этом предоставляется и возможность использования интерпретируемого байткода, если затраты времени и/или памяти по каким-либо причинам неприемлемы для пользователя; разработанный байткод более компактен, чем байткод библиотеки sregex. Библиотека реентрантна1 и пригодна для использования в многопоточном окружении, полностью поддерживает Unicode.
Библиотека отличается высокой производительностью на сценариях, не сводящихся к поиску фиксированной строки. Сравнительные замеры проводились относительно библиотеки sregex, на указанных сценариях ускорение достигает 2-3 раз при исполнении байткода, и 4-10 раз при JIT- компиляции. На остальных сценариях результат можно улучшить, применив описанную технику определения набора символов, с которых может начинаться совпадение.
