From: "Tikhon B." Date: 2013-02-22T09:21:19+09:00 Subject: 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. > 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/.