1219337 - regular expressions are VERY slow in firefox, see article and code

Status: NEW

(Core :: JavaScript Engine, defect, P3)

Description

[Sergey]

User Agent: Mozilla/5.0 (X11; Linux i686; rv:44.0) Gecko/20100101 Firefox/44.0
Build ID: 20151028030432

Steps to reproduce:

Open browser, press F12, select "Console" tab, execute:
  RegExp(Array(50).join('a?')+Array(50).join('a')).exec(Array(50).join('a'))



Actual results:

100% CPU, frozen window and no result...



Expected results:

instant answer


Additional information:
Firefox regexps are exponential-time instead of O(N²).
See explanation and example code here: https://swtch.com/~rsc/regexp/regexp1.html

Comment 1

[Jan de Mooij [:jandem]]

I see the same behavior in Chrome (Firefox and Chrome use the same regex engine).

It's fast in Safari.

Comment 2

[Mayank Bansal]

I tried this as a HTML page, and these are the results:

Nightly: https://share.firefox.dev/47MdDKQ (18s without the profiler)
Chrome: https://share.firefox.dev/3XDJJDJ (9s)

Comment 3

[Mayank Bansal]

Attachment: Reporters_Standalone_Testcase.HTML

Comment 4

[Iain Ireland [:iain]]

The difference between us and Chrome here is weird, because to a first approximation the entire profile is spent compiling the regex (in recursive calls to ChoiceNode::FillInBMInfo and TextNode::FillInBMInfo), and that code is in the shared part of the regex engine. So it's not clear why Chrome's performance would differ at all.

(Note that unlike most reports of pathological regex performance, it looks like this one is spending time compiling the regex, not running it. Without looking into it, my best guess is that irregexp may be doing something clever with Boyer-Moore to make a fast matcher, but it takes an unreasonable amount of time to generate that matcher. Otherwise we'd see time spent executing the regex, which seems to be absent from the profile.)