On 7/21/21 6:19 PM, Phil Endecott via Boost wrote:

Dear Experts,

I recently wanted to add some input-sanitising code to a C++ web application, and as I had some existing Javascript code I decided to port its regex-based input checking to the C++ code. This didn't go as well as I had expected!

Here's an example of the sort of thing I have:

if (!regexp_match(s, regex("[A-Za-z0-9-_/]{1,8192}"))) throw MalformedInput();

The Javascript equivalent seems to be fine. In C++, with libstdc++'s regex implementation, it seems to take about 2 seconds to run. Boost.Regex didn't like the '-' after the '9' but when I fixed that the execution time became negligible. Boost.Xpressive seems also to be fast.

I haven't benchmarked regex implementations for a few years, but my past experience was that libstdc++ std::regex indeed was very slow. I don't remember the numbers, but my general impression was that all std::regex implementations were slow compared to Boost.Regex, which seems to be one of the fastest implementations. Boost.Xpressive is slower than Boost.Regex, but faster than std::regex. Its main advantage was that it is header-only. Basically, use Boost.Regex unless you really can't.

On investigation it seems that this is due to there being two different algorithms, one of which (DFA) is linear in the string size but exponential in the pattern size (which in this case seems to mean exponential in the max repeat value of 8192), and the other (backtracking) is linear in the pattern size but exponential in the string size.

It seems that the standard deliberately doesn't specify complexity guarantees for std::regex, leaving the choice of algorithm to the implementation. I find this a bit surprising. It's true that both algorithms have their strengths, but not knowing which you are going to get is the worst of both worlds - you would have to assume that it will be exponential in both pattern and string sizes in portable code! (Imagine a container that doesn't disclose whether it has vector or list complexity!)

So I'm wondering if it would be useful for regex libraries to somehow be explicit about which algorithm they are and what the complexity is.

Compare, for example, with the text search algorithms (Boyer-Moore etc) which indicate the algorithm in their names. Could we have regex_dfa / regex_backtracking, or something?

Now having said that, I think that what I really need for my application is something that is worst-case linear in both the pattern size and the input string. I'm not sure if the apparently-fast Boost.Regex algorithm has a worst-case input that is slow. ("Regular Expression Denial Of Service"). It's clear that my example can be written without a regex as a simple linear loop, and maybe some regex libraries have heuristics that do that.

Thoughts anyone?

Have you tried to cache the regex object? I suspect, parsing the regex might have a non-negligible cost. As for the complexity specification, it obviously depends on the regex. I don't think it is possible to specify an abstract complexity estimate for a regex library. The best you could have is to specify the complexity of various elements of the expression - both when constructing a regex and when applying it. Complexity is not everything you need to know when you care about performance. You should benchmark it anyway. It is not unusual to have a higher complexity algorithm outperform a lower complexity one in some conditions, which may happen to match yours. Even two algorithms having the same formal complexity estimate may perform very differently in practice. I remember Boost.Regex docs had some benchmark results, although by now they are probably outdated.

Have you tried Russ Cox's RE2 from https://github.com/google/re2 ?

From https://swtch.com/~rsc/regexp/regexp3.html :

The result, RE2, provides most of the functionality of PCRE using a C++ interface very close to PCRE's, but it *guarantees linear time execution* and a fixed stack footprint

Thanks all for your replies. John Maddock wrote:

Complexity for regular expression is really really hard to specify

I disagree. Pretty much by definition, Regular Expressions can be matched in time linear in the length of the string and that's what I'd expect a std::c++ spec to require, just as it requires sorting to be N log N etc. etc. The fact that Perl >bleurgh< chose to provide what I'd call "irregular expressions" 25 years ago doesn't mean that we had to copy that. I reject the idea that we have to support back-references in patterns because "people expect that" - I've never used them. Dominique Devienne wrote:

Have you tried Russ Cox's RE2 from https://github.com/google/re2

Thanks for the pointer. He has a series of three really good documents explaining the history of regular expression implementations and how we've slipped into this hole where the most common implementations have poor complexity guarantees. See: https://swtch.com/~rsc/regexp/ This also prompted me to look at CTRE, which compiles regular expressions from strings at compile time and even works pre-C++20. See: https://github.com/hanickadot/compile-time-regular-expressions Gavin Lambert wrote:

In pretty much all regexp languages, if you want to match '-' inside a character set then you must specify it as the first character

I was looking at the cppreference docs here: https://en.cppreference.com/w/cpp/regex/ecmascript The grammar they give includes: CharacterClass :: [ [ lookahead ∉ {^}] ClassRanges ] [ ^ ClassRanges ] ClassRanges :: [empty] NonemptyClassRanges NonemptyClassRanges :: ClassAtom ClassAtom NonemptyClassRangesNoDash ClassAtom - ClassAtom ClassRanges ClassAtom :: - ClassAtomNoDash ClassAtomExClass(C++ only) ClassAtomCollatingElement(C++ only) ClassAtomEquivalence(C++ only) ClassAtomNoDash :: SourceCharacter but not one of \ or ] or - \ ClassEscape I believe that allows [A-Z0-9-_/], doesn't it? Anyway, all this prompted me to do some more investigation and some benchmarking. The libraries that I have tried are libstdc++ (as supplied with g++ 8.3, so rather old), Boost.Regex, Boost.Xpressive (with run-time expression strings, not the Spirit-like compile time mode) (both Boost version 1.75), RE2, and CTRE. What I'm trying to do is to sanitise the input to an internet- exposed process, to reject malicious input'); drop table users; As an example I'll look at input that is supposed to be base-64 encoded and no more than a couple of kilobytes long. Typical-case performance doesn't matter much as this runs once per process invocation (and hence also caching the compiled regex doesn't help), but I do want to be sure that it doesn't have bad worst-case complexity in the face of pathological input. So my first test is a quick check with a regular expression that should might trigger worst-case behaviour in a non-linear implementation: a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?a?aaaaaaaaaaaaaaaaaaaa matched against: aaaaaaaaaaaaaaaaaaaa The execution times were: CTRE: 1.1 us RE2: 148 us Xpressive: 27286 us Boost.Regex: 31 us libstdc++: 88632 us Based on that, Xpressive and libstdc++ can be rejected immediately. (Of course this doesn't prove that the others use exclusively-linear algorithms; they may have heuristics that handle that case or just got lucky; this is why I believe there should be complexity guarantees.) Here are the patterns that I have benchmarked for my base64 test: 1. [A-Za-z0-9/+=]{0,8192} 2. [A-Za-z0-9/+=]* 3. (?:[A-Za-z0-9/+]{4}){0,2048}(?:|(?:[A-Za-z0-9/+]{2}==)|(?:[A-Za-z0-9/+]{3}=)) 4. (?:[A-Za-z0-9/+]{4})*(?:|(?:[A-Za-z0-9/+]{2}==)|(?:[A-Za-z0-9/+]{3}=)) Recall that base64 has chunks of four printable characters with the final chunk using = to pad. Variants 3 & 4 strictly check the padding. Variants 1 and 3 check for excessive length while 2 & 4 require a separate check to do that. Note that I'm using the "non capturing" syntax (?: ) rather than ( ) because I only need the boolean match result. First a note on compatibility. I noted before that expressions like [A-Za-z0-9-_/] were accepted by some libraries but not others. I found two other issues: only libstdc++ would accept [A-Z]{4}*, while the others all required ([A-Z{4})*. Then RE2 rejected the {0,8192} and {0,2048} repeats - it limits them to some smaller value. A note on compile times (g++ 8.3 -O3): there was a substantial variation, with RE2 and CTRE being the fastest, Boost.Regex and libstdc++ in the middle, and Boost.Xpressive slowest. The difference from fastest to slowest was about 10X. It was interesting that the "Compile Time Regular Expression" library CTRE was one of the fastest to compile! Regarding run-time performance, testing with about 3 kbytes of input data: CTRE was fastest. RE2 was second in the two expressions that it did not reject. Boost.Regex was last. My conclusion is that CTRE is the best choice, and I would recommend it unless (a) you need to specify the regular expression at runtime, or (b) you need some of the "irregular" Perl extension syntax. I hope that is of interest. Regards, Phil. P.S. I am subscribed to the list digest, which used to flush whatever had been posted at least once per day; now it doesn't seem to send anything until it has reached its threshold. Do others see this or is it just me? Can it be fixed? I would have replied earlier, and separately to the other replies, if I had received a digest at some point.