Вступление

"Не используйте регулярки, иначе вместо 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 🥴🙆🏼‍♂️. Возможно это нам пытается объяснить автор данного решения в своем репозиторие.

В результате, почти все альтернативные решения дают нам прирост в скорости в 8-130 раз! За исключением Regexp2, который оказался медленней стандартной библиотеки.

Бенчмарк #2

Вопросы

Изучая уже существующие бенчмарки и результаты Бенчмарка#1, мне не хватило ответов на следующие вопросы:

1. Насколько быстро приведенные библиотеки будут обрабатывать большие файлы?

2. Насколько быстрее будет обработка при группировке регулярных выражений?

3. Как быстро будут прогоняться регулярки без совпадений в тексте?

4. Сколько памяти потребляют разные библиотеки?

5. Сколько регулярок я смогу скомпилировать при группировке?

Отличия бенчмаркера

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

Стоит выделить следующие особенности этого бенчмарка:

• В тестах ниже я использовал 5 различных регулярных выражений:

allRegexps["email"] = `(?P<name>[-\w\d\.]+?)(?:\s+at\s+|\s*@\s*|\s*(?:[\[\]@]){3}\s*)(?P<host>[-\w\d\.]*?)\s*(?:dot|\.|(?:[\[\]dot\.]){3,5})\s*(?P<domain>\w+)`
allRegexps["bitcoin"] = `\b([13][a-km-zA-HJ-NP-Z1-9]{25,34}|bc1[ac-hj-np-zAC-HJ-NP-Z02-9]{11,71})`
allRegexps["ssn"] = `\d{3}-\d{2}-\d{4}`
allRegexps["uri"] = `[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?`
allRegexps["tel"] = `\+\d{1,4}?[-.\s]?\(?\d{1,3}?\)?[-.\s]?\d{1,4}[-.\s]?\d{1,4}[-.\s]?\d{1,9}`

По хорошему, следовало бы использовать хитровынаписанные регулярки, как это делают авторы других бенчмарков - для того чтобы проверить "слабые" места алгоритмов. Но я не сильно разбираюсь в подкопотных деталях движков и взял простые регулярки из народа. Поэтому, думаю, должно получиться оценить различные параметры библиотек сразу с практической точки зрения.

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

var data = bytes.Repeat([]byte("123@mail.co nümbr=+71112223334 SSN:123-45-6789 http://1.1.1.1 3FZbgi29cpjq2GjdwV8eyHuJJnkLtktZc5 Й"), config.repeatScanTimes)

• Дополнительно к последовательному прогону регулярок по данным, будет производится отдельный, с именованной группировкой регулярных выражений, где в итоге они примут следующую форму:

`(?P<имя_1>регулярка_1)|(?P<имя_2>регулярка_2)|...|(?P<имя_N>регулярка_N)`

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

• В отличие от Бенчмарка#1, для каждой регулярки я буду замерять время нахождения результата без учёта времени их компиляции;

• В итоге мы получим результаты для каждой библиотеки и каждой регулярки в следующем виде:

Generate data...
Test data size: 100.00MB

Run RURE:
  [bitcoin] count=1000000, mem=16007.26KB, time=2.11075s 
  [ssn] count=1000000, mem=16007.26KB, time=62.074ms 
  [uri] count=1000000, mem=16007.26KB, time=69.186ms 
  [tel] count=1000000, mem=16007.26KB, time=83.101ms 
  [email] count=1000000, mem=16007.26KB, time=172.915ms 
Total. Counted: 5000000, Memory: 80.04MB, Duration: 2.498027s
...

1-2. Обработка больших файлов и группировка регулярных выражений

Под "большим файлом" я буду понимать сгенерированный из нашей предопределенной строки объем данных в памятий равный 100МБ. Конечно же, это трудно назвать большим файлом, но не хотелось бы ждать часами результатов в некоторых случаях 😅.

Так же, есть смысл попробовать сгруппировать все регулярные выражения в одно и посмотреть насколько это отразится на производительности. Гипотеза заключается в том, что последовательная прогонка регулярок по данным должна быть дольше, чем один прогон с помощью сгруппированной регулярки.

Чтож, давайте запустим бенчмаркер и посмотрим на то как быстро отдельные библиотеки будут обрабатывать данные. Сделать это с помощью тулзы можно написав:

# Бенч всех либ, повторяем строку 1000000 раз (100МБ)
regexcmp 1000000 
# Бенч отдельной либы
regexcmp 1000000 rure

В итоге имеем следующие результаты:

На графике отобразил время обработки 100МБ данных всеми регулярками в последовательном режиме и с помощью группы:

Выводы:

• Группировка действительно может значительно улучшить скорость исполнения, но в некоторых случаях и ухудшить :);

• Самым быстрым в последовательной обработке оказался - Rure, с группировкой - Re2;

• Определенные регулярки могут вызывать труднусти у некоторых библиотек (время нахождения email у Regexp2 и PCRE);

• Сейчас уже не получится сказать, что некоторые решения быстрее стандартной библиотеки в 180 раз, максимальный прирост x8-9.

3. Несовпадающие регулярки

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

В этом тесте я дополнительно добавил 5 видоизменненных регулярок для SSN, которые не матчятся с тестируемыми данными. В данном случае под SSN мы будем иметь в виду \d{3}-\d{2}-\d{4} регулярку, а под Non-matching - \d{3}-\d{2}-\d{4}1. Не сильное отличие? Но давайте посмотрим как это скажится на времени нахождении всех совподений:

На графике показал, затраченное время на обработку всех 10 регулярок, с сортировкой по времени обработки Non-matching:

Выводы:

• В этот раз так же: самым быстрым в последовательной обработке оказался - Rure, с группированными выражениями - Re2;

• PCRE снова отличается, с 2х временем на обработку non-matching регулярок в последовательном режиме;

• Некоторые алгоритмы наоборот, значительно быстрее справляются в случае отсутствия совпадений (Re2, Hyperscan);

4. Потребление памяти

А теперь посмотрим сколько памяти затрачивают различные решения при обработке 100МБ файла. Ниже предоставил результаты для каждой отдельной регулярки и общий объем затраченной памяти:

На графике показал затрачиваемую библеотками память на обработку 10 регулярок (как и в прошлом тесте), с сортировкой по затратам на non-mathcing:

Выводы:

• Rure удивляет практическим отсутствием потребляемой памяти;

• Regexp2 напротив сильно прожорлив, потребляя значительно больше памяти среди конкуретнов;

• Re2, несмотря на свою быстроту, оказался не самым экономичным в плане памяти решением;

• Go regex показывается себя с хорошой стороны в данной случае, с относительно невыскоими затратами в последовательном режиме.

5. Максимальное количество регулярок

На основные вопросы ответы вроде бы получены. А давайте теперь посмотрим максимальный объем регулярки, которой мы можем скомпилировать с разными решениями. В данном случае мы возьмем отдельную регулярку и многократно повторим её в группах.
Для данной ситуации я буду использовать URI regexp:

`[\w]+://[^/\s?#]+[^\s?#]+(?:\?[^\s#]*)?(?:#[^\s]*)?

Далее я привел результаты компиляции регулярок, с затраченными на них памятью. Тут цифры в первой строке это количество URI выражений в группе:

Выводы

• Как мы видим, некоторые решения имеют ограничения на объем компилируемых регулярных выражений;

• Hyperscan не только позволяет использовать большое количество регулярок, но и затрачивает минимальное количество памяти на регулярки в скомпилированном состоянии;

• Regexp2 и Go regex имеют сопоставимые затраты на память, и так же позволяют компилировать большое количество регулярок;

• Re2 затрачивает наибольшее количество памяти при компиляции.

Заключение

Надеюсь вам было полезно узнать про альтернативные решения для регулярок на Go и исходя из данных, которые я привел, каждый сможет сделать для себя определенные выводы, которые позволят выбрать наиболее подходящее для вашей ситуации Regex решение.

Можно долго и в деталях сравнивать эти библиотеки, алгоритмы которые они используют, их лучшие\худшие стороны. Своим "топорным" сравнением я лишь хотел показать разницу между ними в самых общих случаях.

Таким образом, для максимального ускорения регулярок я бы посоветовал обратить внимание на Rure-Go, но если вам нужна наиболее простая установка библиотеки без зависимойстей, то есть Go-Re2. А в случае с обработкой большого количества регулярок хорошим выбором будет Hyperscan. Также не стоит забывать про затраты на использование CGo в некоторых библиотеках.

Что касается меня, то несомненной использую полученные "открытия" в своем будущем проекте. Если кому-то была интересная тема, то предлагаю подписаться тут или на Гитхабе :).