Re: Questionable regex performance when using lazy matching and inverted character classes

Robert Klemme wrote in post #1098199:
> On Thu, Feb 21, 2013 at 12:12 PM, Tikhon B. <[e-mail]>
> wrote:
>> Hi All,
>>
>> I am trying to figure out a performance question with the ruby regex
>> matcher. Running the following code takes excessively longer than
>> expected.
>
> You are doing the measurement wrong.  You do not only measure matching
> but also creation of the String.  Given that fact, all your results
> are moot.

I actively considered this matter when submitting the post, but in the
end I included the string creating in the test to allow anyone to try
out the example by copying one line. The time necessary for the actual
creation process is negligible; I need to run the string creation ten
thousand times before the result is substantial enough to significantly
affect the numbers I'm getting.

Benchmark.measure {10_000.times {"a" * 10_000}}
=>   0.100000   0.000000   0.100000 (  0.105442)

Case in point:

val = "a" * 10_000
3a. Benchmark.measure {val.match(/(?>a[^b]*b)/)}
=>   1.430000   0.000000   1.430000 (  1.490874)

4a. Benchmark.measure {val.match(/aa*b/)}
=>   1.310000   0.000000   1.310000 (  1.366131)

>> 3. Benchmark.measure {("a" * 10_000).match(/(?>a[^b]*b)/)}
>> =>   1.400000   0.000000   1.400000 (  1.462178)
>>
>> 4. Benchmark.measure {("a" * 10_000).match(/aa*b/)}
>> =>   1.270000   0.000000   1.270000 (  1.331137)
>>
>> 5. Benchmark.measure{val.match(/a.*b/)}
>> =>   0.460000   0.000000   0.460000 (  0.487267)
>
> Where does 'val' come from and what does it reference?

As I just mentioned, I included the string creating as part of the
benchmark for simple reproduction. While I was figuring out the answer
myself, I assigned `val = "a" * 10_000` for ease of use.

I added that final example shortly before submitting, and simply did not
notice that I would need to re-write it to

>> engines. Writing this message I think I got a better grasp of the cause
>> of the issue, but I still feel that it needs to be addressed for the
>> sake of security.
>
> Before we jump to conclusions please provide the proper and complete
> test.  Note also that it is a common fact that NFA's can suffer from
> backtracking in certain conditions.  So I am not too surprised nor
> worried.  I did not look closely at all your test cases but often
> backtracking issues can be remedied by using greediness modifiers
> (either "greedy" or "reluctant").
>
> Kind regards
>
> robert

I am not sure what sort of proper and complete tests you are looking
for. Regarding the actual slowdown, the issue comes down to the engine
repeating the match from the start for every single "a" in the string,
then failing and trying again with the next letter. I do not see how a
greedy modifier can help in this situation, and I do not know enough
about the ruby regex engine to comment on the underlying design.

-- 
Posted via http://www.ruby-forum.com/.