Investigate benefit of computing max regex match length

[stephentoub]

Today we compute the minimum length an input is required to be to match an expression; that's then used in a variety of ways, e.g. checking the input length and failing immediately if we've reached a point where the remaining input is shorter than required. We could also in some situations compute a maximum length. This could have various benefits, in particular if the expression ends with a $ anchor and isn't anchored at the beginning, if the current positron is less than the max match length from the end, we can just jump forward to that position, potentially saving on large amounts of unnecessary match attempts. We'd want to investigate how common this is, though, to determine if it's worth the extra compute time.

[ghost]

Tagging subscribers to this area: @dotnet/area-system-text-regularexpressions
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Today we compute the minimum length an input is required to be to match an expression; that's then used in a variety of ways, e.g. checking the input length and failing immediately if we've reached a point where the remaining input is shorter than required. We could also in some situations compute a maximum length. This could have various benefits, in particular if the expression ends with a $ anchor and isn't anchored at the beginning, if the current positron is less than the max match length from the end, we can just jump forward to that position, potentially saving on large amounts of unnecessary match attempts. We'd want to investigate how common this is, though, to determine if it's worth the extra compute time.

Author:	stephentoub
Assignees:	-
Labels:	area-System.Text.RegularExpressions, tenet-performance
Milestone:	7.0.0

[danmoseley]

worth the extra compute time.

My assumption was that the analyses we do before kicking off the engine take negligible time - is that not right? would this be especially expensive?

of course, in a generator, it's "free".

[stephentoub]

My assumption was that the analyses we do before kicking off the engine take negligible time - is that not right? would this be especially expensive?

Negligible compared to performing a match many, many times? Yes. Negligible on the startup path / performing a match once? No.

of course, in a generator, it's "free".

We can have a higher budget, but it still impacts compilation time, which is something we do care about.