Bug 16458 – REGRESSION (r28164): regular expressions can now hang due to lack of a match limit

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Darin Adler]

When we removed the match limit in http://trac.webkit.org/projects/webkit/changeset/28164 we made it possible to create regular expressions that hang because of exponential complexity of matching. Here's an example:

    /(?:[^(?!)]||){23}\z/

<rdar://problem/5636067>

[Darin Adler]

I'd like to get bug 16438 reviewed and landed before fixing this one.

[Darin Adler]

Created attachment 17953 [details]
patch

[Darin Adler]

Created attachment 17954 [details]
patch

[Darin Adler]

Created attachment 17955 [details]
patch

[Eric Seidel (no email)]

Comment on attachment 17953 [details]
patch

I'm curious as to what sunspider says.

[Darin Adler]

Unfortunately this does slow down the regexp-dna test 1.13x times; a big slowdown! Overall effect on SunSpider is 1.01x as slow.

If we can find a faster way to do it, I'm all for it!

[Darin Adler]

By the way, I made a loop to run this expression with various numbers and you can see the problem:

    /(?:[^(?!)]||){1}z/ took 0 milliseconds.
    /(?:[^(?!)]||){2}z/ took 0 milliseconds.
    /(?:[^(?!)]||){3}z/ took 0 milliseconds.
    /(?:[^(?!)]||){4}z/ took 0 milliseconds.
    /(?:[^(?!)]||){5}z/ took 0 milliseconds.
    /(?:[^(?!)]||){6}z/ took 1 milliseconds.
    /(?:[^(?!)]||){7}z/ took 2 milliseconds.
    /(?:[^(?!)]||){8}z/ took 4 milliseconds.
    /(?:[^(?!)]||){9}z/ took 11 milliseconds.
    /(?:[^(?!)]||){10}z/ took 25 milliseconds.
    /(?:[^(?!)]||){11}z/ took 60 milliseconds.
    /(?:[^(?!)]||){12}z/ took 144 milliseconds.
    /(?:[^(?!)]||){13}z/ took 341 milliseconds.
    /(?:[^(?!)]||){14}z/ took 805 milliseconds.
    /(?:[^(?!)]||){15}z/ took 1885 milliseconds.
    /(?:[^(?!)]||){16}z/ took 10120 milliseconds.
    /(?:[^(?!)]||){17}z/ took 29980 milliseconds.

This is an exponential curve. To handle expressions like this one we need some sort of limit.

[Maciej Stachowiak]

the performance hit hurts. I wonder if there is a way to do the check that would be less costly.

[Darin Adler]

(In reply to comment #8)
> the performance hit hurts. I wonder if there is a way to do the check that
> would be less costly.

It'd great! I'd love it if someone could figure out a new optimization other than just removing the match limit. Knowing that it's a 13% speed-up to remove the match limit may point us at something.

But I think the right thing to do is to restore the feature, and remove the incorrect optimization. Then we can look for effective, correct optimizations.

I don't think it makes sense to leave this incorrect optimization in just because it was a good speed-up!

Could someone review the patch, please?

[Geoffrey Garen]

Comment on attachment 17955 [details]
patch

r=me

Might be good to file a bug recording the potential speed gain from optimizing this code path.

[Darin Adler]

(In reply to comment #10)
> Might be good to file a bug recording the potential speed gain from optimizing
> this code path.

Done, bug 16503.

[Darin Adler]

Committed revision 28833.