"Если компьютеры станут слишком мощными, мы можем организовать их в комитеты. Это их прикончит" (с) неизвестный автор

Введение

Так или иначе сталкиваться с регулярными выражениями приходилось большинству разработчиков. Мое первое знакомство произошло с реализацией regexp в STL std::regexp. Чаще всего регулярки используются в проверке входных данных, что-то вроде проверки корректности введенного пользователем URL, адреса IPv4, адреса IPv6, телефонного номера и при этом скорость выполнения операции regex не сильно влияет на время отклика от приложения. Но, что если вам приходится проверять сотни, тысячи или даже десятки тысяч правил и все это на постоянно меняющихся наборах входных данных в реальном времени? В этой ситуации вам не просто нужен быстрый алгоритм, вам понадобится лучший из них, вам понадобится чемпион!

Выбираем участников соревнований

Критерии отбора участников довольно просты:

• наличие исходных кодов

• совместимость по самим правилам, хотя бы на базовом уровне

• код написан на С/С++

Итак, погуглив пояндексив немного находим следующих претендентов:

Методология

Теперь нужно определиться как будем проверять участников.

1. Есть заранее составленный список регулярных выражений одинаковый для всех участников.

2. Есть заранее составленный список наборов данных одинаковый для всех участников.

3. Для выравнивания замеров времени будем итеративно проверять каждое (из NR) правило IR раз на ID итерациях наборов данных (из ND), т.е. количество проверок для каждого участника будет: SUM = IR * NR * ID * ND

4. Для снижения взаимного влияния участников друг на друга будем собирать отдельные приложения для каждого участника.

5. Для сохранения актуальности проекта, исходный код участника клонируется из его репозитория, из ветки master или толерантного main.

6. Если участник - это библиотека, то проводится его сборка.

7. Непосредственно код который осуществляет проверку состоит из класса c двумя абстрактными методами - один для подготовки правил (в том числи для их компиляции) и один для непосредственной проверки скомпилированных правил на наборе данных.

8. Запускать гонки будем на виртуальной машине в облаке

Большая гонка

Код представлен в репозитории https://github.com/shvit/regexp_checker

Для желающих самостоятельно провести гонку на своем компьютере, потребуется установить зависимости. Для Ubuntu 20.04 (подходит также и для ubuntu-latest):

sudo apt install build-essential cmake ragel git libboost-all-dev

git clone https://github.com/abseil/abseil-cpp abseil-cpp && cd abseil-cpp && mkdir -p bin && cd bin && cmake -DCMAKE_CXX_STANDARD=17 -DCMAKE_POSITION_INDEPENDENT_CODE=ON .. && cmake --build . && sudo cmake --install .

теперь клонируем гонку себе на комп и запускаем

git clone https://github.com/shvit/regexp_checker
cd regexp_checker
make check

Проще, конечно же, воспользоваться готовым результатом запуска на виртуалке в GitHub Actions:

В качестве проверки, вместо юнит тестов - все участники выдали одинаковое количество совпадений - по 2'800'000.

Проверки проводились с параметрами: NR=10, IR=20'000, ND=5, ID=10. Общее количество проверок для одного участника SUM=10'000'000.

Заключение

При текущем составе участников бесспорным чемпионом является проект hyperscan, но также порадовал участник занявший второе место - boost.

Также необходимо отметить, что проекты tiny-regex-c и ximtech поддерживают сокращенный набор элементов regexp, из-за чего пришлось существенно сократить список правил. Проект ximtech является развитием проекта tiny-regex-c. Также в проекте tiny-regex-c есть баги и также он не позволяет компилировать более одного правила из-за своей архитектуры.

Для использования проекта google-re2 потребуется установка библиотек Abseil и также потребуется не тривиальная линковка готового проекта.

В заключение, хочется отметить наличие у проекта hyperscan возможности применения правил на потоках (streams), что в некоторых случаях может быть решающим.

Если кто-то знает других потенциальных участников гонки - предлагайте в комментариях.