# Why Except is so slow as compared to equivalent RegularExpression?

When comparing performance of the solutions suggested for this question I discovered that StringExpression involving Except is two orders of magnitude slower for large strings as compared to equivalent RegularExpression. Here is a simplified example demonstrating the problem:

With[{str = StringRepeat["a", 10^6] <> "b"}, {
AbsoluteTiming[StringMatchQ[str, Except["b"] .. ~~ "b"]][[1]],
AbsoluteTiming[StringMatchQ[str, RegularExpression["[^b]+b"]]][[1]]}]

Divide @@ %

{0.719855, 0.00323316}

222.648


The string pattern is 220 times slower than pure regex! But the regular expression [^x]+x is the direct semantic translation of the string pattern Except["x"] .. ~~ "x", and this translation is unique and unambiguous. Why then the latter is so insanely slow?

Using StringPatternPatternConvert we can find the regexp into which Mathematica converts the original string expression:

StringPatternPatternConvert[Except["b"] .. ~~ "b"][[1]]

"(?ms)(?:[^b])+b"


The only difference as compared to the direct semantic translation is that the negated character class [^b] is enclosed by redundant non-capturing group (?: … ). Since this group is non-capturing, one would expect that it can't introduce noticeable overhead. But is it so in practice? Let us check:

With[{str = StringRepeat["a", 10^6] <> "b"}, {
AbsoluteTiming[StringMatchQ[str, Except["b"] .. ~~ "b"]][[1]],
AbsoluteTiming[StringMatchQ[str, RegularExpression["(?:[^b])+b"]]][[1]],
AbsoluteTiming[StringMatchQ[str, RegularExpression["[^b]+b"]]][[1]]}]

{0.721896, 0.717353, 0.00325354}


We see that this redundant non-capturing group is responsible for all the slowdown we observe.

It is interesting that the overhead isn't constant but grows step-wise with the length of the string up to approximately 95000 characters:

PrintTemporary[Dynamic[n]];

timings = Transpose[Table[With[{str = StringRepeat["a", n] <> "b"},
{{n, AbsoluteTiming[StringMatchQ[str, RegularExpression[".+b"]]][[1]]},
{n, AbsoluteTiming[StringMatchQ[str, RegularExpression["(?:.)+b"]]][[1]]}}],
{n, 100, 100000, 100}]];

ListPlot[timings, PlotRange -> All, Frame -> True, Axes -> False, ImageSize -> 600,
FrameLabel -> {"string length", "seconds"}]


(evaluated with Mathematica 11.1.0 on Windows 7 x64.)

• good question and great analysis. If I'd had seen this earlier I would have simply suggested that if you have enough knowledge to formulate as regexp and care about speed, you should always use regexps. I think there are many other examples with similar, although not as extreme differences. And AFAIK all string expressions are internally converted to regexps anyway so they are always adding at least the overhead to generate the regexp... – Albert Retey Mar 22 '17 at 21:47
• @AlbertRetey Fuerthermore each time you will call the function, the regex expression will be recreated, and this operation is far from being free in a loop in contrary of when you instiated once before. – Walfrat Mar 23 '17 at 9:17
• @Walfrat Actually the Documentation states (emphasis is mine): "The regular expression is then compiled by PCRE, and the compiled version is cached for future use when the same pattern appears again. The translation from symbolic string pattern to regular expression only happens once." My tests seem to support this statement: I didn't observe any difference in timings between, for example, StringMatchQ[#, patt]&/@list and StringMatchQ[list, patt]. But I didn't test this aspect carefully. – Alexey Popkov Mar 23 '17 at 9:27