`regex::bytes::Regex::is_match` with a simple pattern with long sequences of wildcards is significantly slower than a naïve alternative about regex HOT 2 OPEN

Oh sorry, I just stepped back for a second and realized that this is an slightly unfair comparison. regex_match checks if there is a match directly at the start of the slice, while regex::bytes::Regex::is_match checks for a match anywhere in the slice. The slices I'm passing as input are exactly the same size as the pattern and either have a matching pattern or not, so in this particular case there shouldn't really be a difference.

Tomorrow I'll try and write an equivalent of regex::bytes::Regex::find as I'm not super happy with the performance of that with these patterns either. I'll use that to generate another comparison.

from regex.

I'm happy to write a test program if that's required for this issue to get attention

Yes, please provide a reproduction program. While you did provide a good amount of details, it's no substitute for the real thing. Otherwise, I have to spend time deciphering exactly what you meant in your prose and possibly make guesses on things. But if you give me the code, the inputs and the specific commands you're running, then it takes all of the guesswork out of the process. I can then be reasonably sure that I'm looking at the same thing you are.

With that said...

My expectation is that this kind of pattern would be at-worst slightly slower than the naïve alternative that follows:

I think your expectation is way off personally. I wouldn't call your code naive in any way. It's a bespoke targeted solution to a specific problem. There are a variety of reasons why it might be faster here:

1. My guess is that your benchmark is latency oriented. Your bespoke code is small and likely has little to almost no overhead at all. Compare that with a regex engine which has to execute a pile code for every search before it even gets to executing the search itself.
2. Regex engines support a very general pattern language, and it just doesn't take advantage of every possible optimization opportunity. Sometimes it's because it's difficult to do. Sometimes it's because it might not be worth it. And in other less interesting cases, it's just because nobody has attempt to implement it. In this case, from what I can see, your bespoke matcher is doing something very critical to performance here that the regex engine is likely not doing: it's recognizing the bounded repeat as a simple skip instruction and literally jumping over an entire portion of the haystack. The regex engine, by contrast, is still going to match . 1023 times one byte at a time. That's going to lose---and lose big---to the simple pointer offset you've implemented.

With respect to (2), it's possible the regex engine could implement this optimization, but it would be limited to specific cases. And I haven't thought through all of it.

from regex.