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

RESOLVED WORKSFORME

Status

()

Core
JavaScript Engine
RESOLVED WORKSFORME
7 years ago
5 years ago

People

(Reporter: Ellis Lau, Unassigned)

Tracking

(Blocks: 1 bug, {perf})

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

7 years ago
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
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.
Status: UNCONFIRMED → NEW
Ever confirmed: true
Summary: Unresponsive script warning when using String.replace to trim whitespace character \u00a0 → Unresponsive script warning when using String.replace to trim whitespace character \u00a0 (much slower than jsc or carakan)
ccing the folks I meant to cc.
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?
yeah, could be string woes -- there were some strange rope behaviours in another bug recently, I forget which but jseward was pointing them out...
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.
Or something, too late at night for me :).
Oh .... \s matches \u00a0, so the backtracking is going to be exponential in this example.  Oops!
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.
Assignee: general → cdleary
Status: NEW → ASSIGNED
(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.
(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.
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.
(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.

Updated

7 years ago
Keywords: perf
Blocks: 579390
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.
Assignee: cdleary → general
Status: ASSIGNED → NEW
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.
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → WORKSFORME
You need to log in before you can comment on or make changes to this bug.