0

I have multiple regexes matching an input in greedy-first mode. All regexes are already compiled and I don't see what I can do more to speed-up things. I mean using tools coming with .Net framework.

Since I don't do any replace, or capturing, I wonder if it makes sense to built my own regex matching -- in result I would execute matching only once (per multi-regex) instead of multi matching (per each single regex).

Am I thinking too far? Is there other way to speed it up?

  • I think your question is too general. To get a useful anwer, you should be more concrete, ideally including a sample of your code. – svick Dec 6 '13 at 16:25
  • @svick, think of lexer (because it is exactly this). The regexes are completely arbitrary, the only known thing is there are many of them. So for example you have N regexes, you select longest-first match, you match again from the last position, and so on. At each step N regexes are used. – greenoldman Dec 6 '13 at 21:27
2

most regex engines use a backtracking mechanism that may slow down on bad inputs (called catastrophic backtracking). I don't know if C# does but my guess is that it does. Read this article if you want to know more

one way to fix it is tuning your regexes to avoid the backtracking pitfall

another is to use a regex engine that builds a DFA and doesn't need to backtrack (not possible when you use backrefs but you aren't doing that) or build your own DFA

1

All regexes are already compiled and I don't see what I can do more to speed-up things.

Do you reuse Regex objects? Compiling will not speed things up if you don't; quite the contrary.

See https://stackoverflow.com/a/7707369/168719 for reference.

Is the pattern complex? Sometimes regular expressions are too heavy weight for the job. If the matching is not that sophisticated, it would certainly be faster to implement it "manually", with a loop and some hand-made logic etc.

  • Thank you. Regexes (yes, Regex objects) are given by the user, but they should fall into "simple" category, like "[a-zA-Z][a-zA-Z0-9]*". Compiled regexes MIGHT be slower, but if you re-use them it is not the case. And I saw profiler number, regex.match slows me down, not making Regex. – greenoldman Dec 6 '13 at 14:21
  • 1
    If that's [a-zA-Z][a-zA-Z0-9]* type, then I'd try and time it against "hand-made" implementation. – Konrad Morawski Dec 6 '13 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.