Best Regexp Alternative for Go; Benchmarks and Plots

"Don't use regular expressions, otherwise you'll have 2 problems instead of 1" - that's what the experts say. And what is left for the naughty ones who want to efficiently search through a huge number of templates?

Sure, there are cool solutions like Ragel or re2c for this specific problem. However, for my project it seemed impractical to master these fine technologies for the time being.

In this article, we will look at alternatives to the standard regexp library in Go and benchmark them for speed and memory consumption. We will also consider the differences between them from a practical point of view.

Analogues

At the moment, I've found the following working alternatives to the default regexp that can be used to find patterns in Go (the versions used in the benchmarks are given in brackets):

• go-re2 (1.3.0) - as simple as possible replaces the default regexp. Uses C++ re2 to improve performance when dealing with large inputs or complex expressions;
• regexp2 (1.10.0) - a feature-rich regexp engine for Go. It does not have runtime guarantees like the built-in regexp package, but is compatible with Perl5 and .NET;
• go-pcre (1.0.0) - provides support for Perl compatible regular expressions using libpcre or libpcre++. JIT compilation is available, making this fork much faster than its counterparts. On the downside, you'll need the libpcre3-dev dependency;
• rure-go (regex 1.9.3) - uses the Rust regex engine with CGo bindings. The downside is a Rust library dependency that needs to be compiled;
• gohs (1.2.2 + hs5.4.1) - regex engine designed for high performance. It is implemented as a library that provides a simple C-API. It also requires compilation and linking of third-party dependencies;
• go-yara - A tool for identifying and classifying malware samples. Although YARA has functionality for templating and regular expressions, it is very limited, so I will not include this library in the upcoming tests.

Existing benchmarks

Before we start comparing the aforementioned solutions, it is worth to show how bad things are with the standard regex library in Go. I found the project where the author compares the performance of standard regex engines of various languages. The point of this benchmark is to repeatedly run 3 regular expressions over a predefined text. Go came in 3rd place in this benchmark! From the end...

As far as I can tell, benchmarking regex engines is not the easiest topic, because you need to know implementation and algorithm details for a correct comparison. From other benchmarks I can highlight the following:

• Benchmarks Game - comparison of engines with optimized versions for each language. For example, Go is no longer at the bottom, but it is still far from ideal there... And of course it does not use a native library, but a wrapper over PCRE - go-pcre, which was specified in analogues.

• Performance comparison of regular expression engines - Comparison of different regex engines (PCRE, PCRE-DFA, TRE, Oniguruma, RE2, PCRE-JIT).

• A comparison of regex engines - here the author tries to compare engines using different regular expressions, which can complicate things depending on the engine implementation. In this benchmark, the author's top three engines are: Hyperscan, PCRE (with JIT compilation) and Rust regex (rure uses it):

  

Benchmark #1

Now let's try to compare the analogues with default regex engine libraries of other languages. And also see how much faster they are compared to the default Go regex. To do this, I updated the above project by adding new libraries code. Here is what I got after running it on my machine:

Ps. Shortened the table a bit, so please check the project fork to see all the results.. Pss. In this case, virtualization might have affected the results (the tests were performed in a Docker environment on Windows 11).

Still, you can see how much faster regexps can be with some libraries! We even outperformed Rust with a Go library that uses the Rust library 🥴🙆🏼‍♂️. Perhaps this is what the author of this solution is trying to explain to us in his repository.

As a result, almost all alternative solutions give us a speedup of 8-130 times! Except for Regexp2, which turns out to be slower than the standard library.

Benchmark #2

Questions

While studying the existing benchmarks and the results of Benchmark#1, I was lacking the answers to the following questions:

1. How fast do the above libraries process large files?
2. How much faster is the processing when grouping regular expressions?
3. How fast will regular expressions with no matches in the text be processed?
4. How much memory do the different libraries use?
5. How many regexps will I be able to compile using grouping?

Benchmarker differences

To answer these questions, I wrote a small benchmarking program that can be used to compare different regex engines in terms of speed and memory usage. If you want to test it yourself or evaluate the correctness of the used methods, here is the code.

The following features of this benchmark are worth mentioning:

• In the tests below, I used 5 different regular expressions:

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}`

In a good way, I should have used tricky regular expressions, like other benchmark authors do - to check the "weaknesses" of the algorithms. But I don't have much insight into the under-the-hood details of engines, so I used general-purpose regexps. That's why I think it should be possible to evaluate different parameters of libraries from a practical point of view.

• Instead of a static file, we will use a string containing our matches, repeated many times in memory to simulate files of different sizes:

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

• In addition to running the regexps sequentially over the data, there will be a separate run with named grouping of regular expressions, where they will take the following form:

`(?P<name_1>regexp_1)|(?P<name_2>regexp_2)|...|(?P<name_N>regexp_N)`

By the way, Hyperscan has a special functionality where we can build a database of regexps and use it against data. In the benchmarks I will use this method.

• Unlike in Benchmark#1, for each regexp I will measure the time to find the result, without taking into account the compilation time;
• In the end, we will get the results for each library and each regexp in the following form:

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. Processing large files and grouping regular expressions

By "large file" I mean the amount of data generated from our predefined string in memory equal to 100MB. Of course it's hardly a big file, but I didn't want to wait hours for results in some cases 😅.

Also, it makes sense to try grouping all regular expressions into one and see how much it affects performance. The hypothesis is that a sequential run of regexps over the data should take longer than a single run with a grouped regexp.

Well, let's run the benchmark and see how fast each library processes the data. You can do this with my tool as follows:

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

As a result, we have the following data:

The plot below shows the processing time of 100MB of data by all regexps in sequential mode and using grouping:

Conclusions:

• Grouping can indeed significantly improve execution speed, but in some cases it can make it worse :);
• The fastest in sequential processing turned out to be - Rure, with grouping - Re2;
• Certain regexps may cause problems with some libraries (time to find email in Regexp2 and PCRE);
• Now it is hard to say that some solutions are 180 times faster than the standard library, the maximum gain is x8-9.

3. Non-matching regexps

In the previous case, we simulated the ideal situation where there are always matches in the data. But what if there are no hits for regexp in the text, how much will that affect performance?

In this test, I additionally added 5 modified regexps for SSN that do not match the data. In this case, SSN means \d{3}-\d{2}-\d{4} regexp, and Non-matching - \d{3}-\d{2}-\d{4}1. Not a big difference? But let's see how it affects the time it takes to find all the matches:

The plot below shows the time taken to process all 10 regexps, sorted by Non-matching processing time:

Conclusions:

• This time is the same: the fastest in sequential processing was - Rure, with grouped expressions - Re2;
• PCRE is once again different, with 2x time to process non-matching regexps in sequential mode;
• Some algorithms are much faster when there are no matches (Re2, Hyperscan);

4. Memory consumption

Now let's see how much memory the different solutions consume when processing a 100MB file. Below, I have provided the results for each individual regexp and the total amount of memory consumed:

The graph below shows the memory used by the libraries to process 10 regexps (as in the last test), sorted by the time of `non-mathcing':

Conclusions:

• Rure surprises with its practically zero memory consumption;
• Regexp2 is resource hungry, consuming significantly more memory than its competitors;
• Re2, despite its speed, is not the most memory-efficient solution;
• Go regex is on the good side, with relatively low costs in sequential mode.

5. Maximum number of regexps

The main questions seem to be answered. Now let's see the maximum number of regexps we can compile with different solutions. In this case we will take a single regexp and repeat it many times in groups.

For this purpose I will use the URI regexp:

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

Next, I've listed the results of compiling the regexps, along with the memory they use. The numbers in the first line are the number of URI expressions in the group:

Conclusions:

• As we can see, some solutions have limitations on the size of compiled regexps;
• Hyperscan not only allows to use a large number of regexps, but also uses minimal memory for compiled regexps;
• Regexp2 and Go Regex have comparable memory consumption and also allow to compile a large number of regexps;
• Re2 consumes the most memory at compile time.

Conclusion

I hope it was useful for you to learn about alternative solutions for regexps in Go, and based on the data I presented, everyone will be able to draw some conclusions for themselves, which will allow you to choose the most suitable regex solution for your situation.

We can compare these libraries, the algorithms they use, their best/worst sides in details and for a long time. I just wanted to show the difference between them in the most general cases.

Thus, I would advise you to look at rure-go for maximum speedup of regexps, but if you need the easiest library installation without dependencies, that is go-re2. And in the case of handling a large number of regexps hyperscan would be a good choice. Also, don't forget the cost of using CGo in some libraries.

As for me, I will definitely use these "findings" in my future project :).