Лучший regexp для Go. Benchmark c другими ЯП. Сравнение библиотек

Вступление

"Не используйте регулярки, иначе вместо 1 проблемы, у вас их станет 2!" - как то так говорят знатоки. А что остается делать непослушным, желающим эффективный поиск по большому количеству шаблонов?

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

В этой статье мы рассмотрим альтернативы стандартной библиотеке для регулярных выражений в Go, проведем их бенчмарк по скорости и потребляемой памяти. А также с практической точки зрения рассмотрим различия между ними.

Аналоги

На данный момент можно выделить следующие рабочие альтернативы стандартному regexp, которые можно использовать для нахождения паттернов в Go:

• go-re2 - максимально легко заменяет стандартный regexp. Использует C++ re2 для повышения производительности при работе с большими входными данными или сложными выражениями;

• regexp2 - многофункциональный движок Regexp для Go. Он не имеет гарантий по времени исполнения, как встроенный пакет regexp, но совместим с Perl5 и .NET;

• go-pcre - обеспечивает поддержку Perl-совместимых регулярных выражений с помощью libpcre или libpcre++. Доступна JIT-компиляция, что делает этот форк намного быстрее аналогов. Из минусов - нужно ставить зависимость в виде libpcre3-dev;

• rure-go - использует регекс-движкок Rust с помощью привязок CGo. Но есть зависимость от Rust библиотеки, которую необходимо скомплировать;

• gohs - regex движок, разработанный с учетом высокой производительности и гибкости. Реализован в виде библиотеки, предоставляющей простой С-API. Тут так же необходимо компилировать и связывать сторонние зависимости;

• go-yara - инструмент для помощи в идентификации и классификации образцов вредоносного ПО. Хоть YARA и имеет функционал для шаблонирования и регулярных выражений, но он сильно ограничен, поэтому не буду включать эту библиотеку в тестах далее.

Существующие бенчмарки

Прежде чем начать сравнивать приведенные решения, стоит показать насколько плохо обстоят дела со стандартной regex библиотекой в Go. Я нашел проект, где автор сравнивает быстродействие стандартных regex движков многих ЯП. Суть этого бенчмарка заключается в многократной прогонке 3 регуляркок над предопределенным текстом. Go в этом бенчмарке оказалсяна 3 месте! С конца...

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

Из других бенчмарков можно выделить следующие:

• Benchmarks Game - сравнение движков с оптимизированными версиями под каждый ЯП. Например здесь Go уже не в конце, но и далек от идеала... И конечно же не использует нативную библиотеку, а обертку над PCRE - go-pcre, которую указывал в аналогах.

• Performance comparison of regular expression engines - сравнение различных regex движков (PCRE, PCRE-DFA, TRE, Oniguruma, RE2, PCRE-JIT).

• A comparison of regex engines - тут автор пытается сравнить движки используя различные регулярки, которые могут представлять сложности в зависимости от имплементации движка. В этом бенчмарке автор в тройку лучших движков выделяет: Hyperscan, PCRE c JIT компиляцией и Rust regex (rure использует его):

  

Бенчмарк #1

Давайте попробуем теперь сравнить приведенные в аналогах библиотеки с дефолтными regex движками других ЯП. А также посмотрим насколько они будут быстрее стандартного Go regex. Для этого я обновил вышеупомянутый проект, добавив код с новыми библиотеками. Вот что получилось после прогонки на моей машине:

Ps. Немного сократил таблицу, поэтому прошу на форк проекта, чтобы посмотреть все результаты.
Pss. В данном случае на результаты могла повлиять виртуализация (тесты проводились в среде Docker на Windows 11).

Тем не менее, видно насколько быстрее могут быть регулярки с некоторыми библиотеками! Мы даже обогнали Rust библиотекой на Go, которая использует библиотеку Rust