Бенчмарки. Сравнение библиотек. Участки

Введение

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

Конечно, для этой конкретной проблемы есть интересные решения, такие как Ragel или re2c. Однако для моего проекта освоение этих прекрасных технологий пока казалось нецелесообразным.

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

Аналоги

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

  • go-re2 (1.3.0) — максимально просто заменяет регулярное выражение по умолчанию. Использует C++ re2 для повышения производительности при работе с большими входными данными или сложными выражениями;
  • regexp2 (1.10.0) — многофункциональный механизм регулярных выражений для Go. Он не имеет гарантий времени выполнения, как встроенный пакет регулярных выражений, но совместим с Perl5 и .NET;
  • go-pcre (1.0.0) — обеспечивает поддержку регулярных выражений, совместимых с Perl, с использованием libpcre или libpcre++. Доступна JIT-компиляция, что делает этот форк намного быстрее, чем его аналоги. С другой стороны, вам понадобится зависимость libpcre3-dev;
  • rure-go (regex 1.9.3) — использует механизм регулярных выражений Rust с привязками CGo. Обратной стороной является зависимость библиотеки Rust, которую необходимо скомпилировать;
  • gohs (1.2.2 + hs5.4.1) — механизм регулярных выражений, рассчитанный на высокую производительность. Он реализован в виде библиотеки, предоставляющей простой C-API. Это также требует компиляции и связывания сторонних зависимостей;
  • go-yara — Инструмент для идентификации и классификации образцов вредоносного ПО. Хотя в YARA есть функциональность для шаблонов и регулярных выражений, она очень ограничена, поэтому я не буду включать эту библиотеку в предстоящие тесты.

Существующие тесты

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

Из других тестов могу выделить следующее:

  • Игра в тесты — сравнение движков с оптимизированными версиями для каждого языка. Например, Go уже не внизу, но до идеала там еще далеко… И конечно он использует не нативную библиотеку, а обертку над PCRE — go-pcre , который был указан в аналогах.
  • Сравнение производительности движков регулярных выражений — Сравнение различных движков регулярных выражений (PCRE, PCRE-DFA, TRE, Oniguruma, RE2, PCRE-JIT).
  • Сравнение движков регулярных выражений — здесь автор пытается сравнить движки, использующие разные регулярные выражения, что может усложнить ситуацию в зависимости от реализации движка. В этом тесте тремя лучшими движками автора являются: Hyperscan, PCRE (с JIT-компиляцией) и Rust regex (его использует rure):

Тест №1

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

Тем не менее, вы можете видеть, насколько быстрее могут быть регулярные выражения с некоторыми библиотеками! Мы даже превзошли Rust с библиотекой Go, использующей библиотеку Rust 🥴🙆🏼‍♂️. Возможно, именно это пытается объяснить нам автор данного решения в своем хранилище.

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

Тест №2

Вопросы

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

  1. Насколько быстро вышеуказанные библиотеки обрабатывают большие файлы?
  2. Насколько быстрее происходит обработка при группировке регулярных выражений?
  3. Насколько быстро будут обрабатываться регулярные выражения, не имеющие совпадений в тексте?
  4. Сколько памяти используют разные библиотеки?
  5. Сколько регулярных выражений я смогу скомпилировать с помощью группировки?

Различия в бенчмаркерах

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

Стоит отметить следующие особенности этого теста:

  • В приведенных ниже тестах я использовал 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("[email protected] nümbr=+71112223334 SSN:123-45-6789 http://1.1.1.1 3FZbgi29cpjq2GjdwV8eyHuJJnkLtktZc5 Й"), config.repeatScanTimes)
  • Помимо последовательного выполнения регулярных выражений над данными, будет отдельный прогон с именованной группировкой регулярных выражений, где они примут следующий вид:
`(?P<name_1>regexp_1)|(?P<name_2>regexp_2)|...|(?P<name_N>regexp_N)`

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

  • В отличие от Benchmark#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 МБ. Конечно, это не такой уж большой файл, но в некоторых случаях мне не хотелось часами ждать результатов 😅.

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

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

# Bench all libs, repeat the line 1000000 times (100MB)
regexcmp 1000000 
# Bench individual lib
regexcmp 1000000 rure
# See all options
regexcmp -h

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

На графике ниже показано время обработки 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 снова отличается: время обработки non-matching регулярных выражений в последовательном режиме составляет 2x;
  • Некоторые алгоритмы работают намного быстрее, когда совпадений нет (Re2, Hyperscan);

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

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

На графике ниже показан объем памяти, используемый библиотеками для обработки 10 регулярных выражений (как и в последнем тесте), отсортированный по времени «несоответствия»:

Выводы:

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

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

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

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

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

Выводы:

  • Как мы видим, некоторые решения имеют ограничения на размер скомпилированных регулярных выражений;
  • Hyperscan не только позволяет использовать большое количество регулярных выражений, но и использует минимум памяти для скомпилированных регулярных выражений;
  • Regexp2 и Go Regex имеют сопоставимое потребление памяти, а также позволяют компилировать большое количество регулярных выражений;
  • Re2 потребляет больше всего памяти во время компиляции.

Заключение

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

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

Таким образом, я бы посоветовал вам посмотреть на rure-go для максимального ускорения регулярных выражений, но если вам нужна самая простая установка библиотеки без зависимостей, то это go-re2. А в случае обработки большого количества регулярных выражений хорошим выбором будет hyperscan. Кроме того, не забывайте о стоимости использования CGo в некоторых библиотеках.

Что касается меня, то я обязательно использую эти находки в своем будущем проекте :).