613398 - Unresponsive script warning when using String.replace to trim whitespace character \u00a0 (much slower than jsc or carakan)

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, defect)

Description

[Ellis Lau]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.2.7) Gecko/20100713 Firefox/3.6.7
Build Identifier: 3.6.7

I attempted to trim a string that had ~30 consecutive whitespace characters in the middle of the string, many of which were non-breaking whitespace \u00a0. The trim used String.replace with the regex /(\s|\u00a0)+$/ to remove trailing space. This can apparently take over a minute to evaluate, triggering unresponsive scripts warnings. Running time appears to be exponential relative to the number of whitespace characters.

Reproducible: Always

Steps to Reproduce:
1. construct a string of ~25 consecutive non-breaking whitespace characters, followed by any other character. 
2. attempt to trim trailing whitespace using String.replace(/(\s|\u00a0)+$/g, "")
Example: "\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Z".replace(/(\s|\u00a0)+$/g, "")
Actual Results:  
the single statement takes several seconds to evaluate

Expected Results:  
the statement should complete evaluation almost immediately

Comment 1

[Boris Zbarsky [:bzbarsky]]

This testcase:

javascript:var start = new Date; "\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Z".replace(/(\s|\u00a0)+$/g,""); alert(new Date - start)

runs in about 2s in Firefox 3.6 over here.  On the same machine, it runs in 128ms in Firefox 4 betas.

Other relevant numbers:

V8: 250ms
JSC: 44ms
Opera: 0ms

So we're better than we used to be, but this could be way faster.... somehow.

Comment 2

[Boris Zbarsky [:bzbarsky]]

ccing the folks I meant to cc.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Oh, a profile says:

 93% under match
  21% self time
  34% under operator new called from match
  24% under szone_free_definite_size called from match
  13% under free called from match

This is all in pcre.  So we're not jitting this... but why are we slower than jsc?  Do they manage to avoid the new/free crap?

Comment 4

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

yeah, could be string woes -- there were some strange rope behaviours in another bug recently, I forget which but jseward was pointing them out...

Comment 5

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

This looks like a missed simplification to me, that opera seems to be making.  /(?:\s|\u00a0)/ is equivalent to /[\s\u00a0]/, and indeed

javascript:var start = new Date;
var s = "\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Z";
s.replace(/[\s\u00a0]+$/g,"");
alert("'"+s+"'"+(new Date - start))

gives
'                      Z'0
whereas the original gives
'                      Z'83

/(\s|\u00a0)/ is apparently forcing pcre into O(n^2) backtracking.

Comment 6

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Or something, too late at night for me :).

Comment 7

[Chris Jones [:cjones] inactive; ni?/f?/r? if you need me]

Oh .... \s matches \u00a0, so the backtracking is going to be exponential in this example.  Oops!

Comment 8

[Chris Leary [:cdleary] (not checking bugmail)]

Yeah, it's doing exponential backtracking.

You can peephole-optimize this "second alternative is a superset of the first" mistake pretty easily.

Also, another peephole that builds on the first: when you're not in multiline mode and fail to match on an EOL assertion with a greedy repetition that has no alternate, you can immediately conclude you've done as well as you can for that match.

Now, optimizations aside, I'm doing something quite sub-optimal in terms of saving offsets to deal with one of our spec "extensions" -- this is why JSC doesn't exhibit the memory allocation overhead. I just came up with a much better way to do it that I don't think will get the PCRE gods too angry with me, so that'll be the primary goal of this bug. More explanation to follow.

Comment 9

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #8)
> Yeah, it's doing exponential backtracking.
> 
> You can peephole-optimize this "second alternative is a superset of the first"
> mistake pretty easily.

Er sorry, meant "one alternative is a subset of the other". And the only reason it's easy here is because understanding character classes is simple, in case that wasn't clear.

Comment 10

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #8)
> Yeah, it's doing exponential backtracking.

Also forgot to mention that, because it's a global match, it's also doing exponential backtracking at every \u00a0 in the string. Given n characters, it tests 2 choices in iteration 0, 4 choices in iteration 1, 8 choices in iteration 2, giving sum(2**(i + 1) for i in range(n)) for each matching start index in the string.

Comment 11

[Chris Leary [:cdleary] (not checking bugmail)]

Crazy thought, while I'm at it: eliminating RegExpStatics would provide an opportunity to DCE capture groups in patterns with no backreferences. For example, in the case of String.prototype.replace, no match object is created, searchValue has no backreferences, and replaceValue is not a lambda, therefore, without RegExpStatics, the capture group values could never be observed.

If the regexp is a literal temporary (JSOP_REGEXP), we can do an op-fusion with a replace JSOP_CALLPROP to guard on the identity of String.prototype.replace and lazily compile a version without capturing groups.

/me guesses this doesn't happen much in the benchmarks. The promising thing for the web is that getting rid of capture groups can get us out of PCRE and into JIT-land, and lots of people use capture groups erroneously.

Comment 12

[Chris Leary [:cdleary] (not checking bugmail)]

(In reply to comment #11)
> eliminating RegExpStatics would provide an
> opportunity to DCE capture groups

Or we could just have RegExpStatics paren-based accesses be slow and re-run the original regexp to discourage use. Okay, seriously at the end of this tangent now.

Comment 13

[Till Schneidereit [:till]]

Mass-reassigning cdleary's bugs to default. He won't work on any of them, anymore. I guess, at least.

@cdleary: shout if you take issue with this.

Comment 14

[Till Schneidereit [:till]]

Great success! The testcase takes 50ms for me, compared to 70ms in JSC and 132ms in d8.

Adding another \u00a0 increases that to 262ms (i.e., 2x), yet another quadruples, etc in d8, whereas SpiderMonkey and JSC don't budge at all, even when adding hundreds of repetitions.