427073 - Optimization of String.replace()

Status: RESOLVED WORKSFORME

(Core :: JavaScript Engine, enhancement)

Description

[Jeremy Martin]

User-Agent:       Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9b5) Gecko/2008032620 Firefox/3.0b5
Build Identifier: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9b5) Gecko/2008032620 Firefox/3.0b5

After running some tests it seems that Firefox does not handle String.replace() as fast as IE6+, Safari 3 for windows, or Opera 9 (the only other browsers I tested).  Although FF3 Beta 5 seems to be twice as fast as FF2, it still remains approximately 3 times slower than IE7 (the leader of the pack in my tests).  A brief summary and graph of the test I was conducting can be found here: http://blog.jeremymartin.name/2008/04/big-regex-improvements-for-firefox-3.html.

It might be significant to note that the regular expressions in the String.replace()'s were always matching one and only one character, and almost always replacing with an ascii encoded character entity.

Reproducible: Always

Steps to Reproduce:
1.  Get sample text input from: http://jmar777.googlecode.com/svn/trunk/for_bugzilla/sample_250K_char_input.txt
2.  Test String.replace() on sample text input.  I performed my tests with the following online utility: http://www.jeremymartin.name/projects.php?project=asciible using all the default options (execution time in milliseconds is displayed at the bottom).  You can examine the source for the utility here: http://jmar777.googlecode.com/svn/trunk/js/asciible.js
3.  Repeat tests in a variety of browsers and compare completion time.
Actual Results:  
Firefox was consistently out performed by other browsers.

Comment 1

[Håkan Waara]

A cursory look at the code gives me a feeling it's not particularly efficient. Isn't there a faster way than doing string-per-string replacement?

Anyway, moving to the right module.

Comment 2

[Håkan Waara]

Speaking of regex: s/string-per-string/character-per-character/g above :-)

Comment 3

[Jeremy Martin]

I have no doubt that the expression could be optimized, however the cross
browser comparisons were still made with respect to the same script.  I guess
I'll have to give the script some attention on my own end as well then... :p

Comment 4

[x0]

Attachment: Standalone testcase

Works for me on Linux, amd64. Konqueror is a bit faster, but Opera much slower. I get these timings with the testcase (note that I treated the test data as Windows-1252 because it contains invalid UTF-8 and ISO-8859-x chars):

js shell trunk     283 ms
Firefox trunk      260 ms
SeaMonkey 1.1.8    "too much recursion" error (doesn't even load)
Konqueror 3.5.9    208 ms
Opera 9.50 beta 1  980 ms

Almost all time is spent in ExecuteREBytecode and SimpleMatch, scanning the input string for chars to replace. The code doesn't look bad, although it could be optimized to work like a simple strstr when searching for a flat string to match.

If the performance is really bad on Windows, then it may be a compiler issue. Good optimization is critical here. It's important that SimpleMatch is inlined (without JS_INLINE the js shell needs 740 ms (gcc 4.2.3)), that re_debug is indeed optimized away as its comment assumes, and that the switch in SimpleMatch becomes a jump table. With -O0 (no DEBUG and re_debug removed), the js shell needs 1080 ms, with -O2 210 ms (don't know why -Os is the default).

When I optimize the script by replacing the concatenated .replace() with

  markup = markup.replace(/["'<>\xa1-\xff]/g,
                          function(c){ return '&#' + c.charCodeAt(0) + ';' });

then I get these timings:

js shell trunk      45 ms
Firefox trunk       80 ms
SeaMonkey 1.1.8    182 ms
Konqueror 3.5.9    135 ms
Opera 9.50 beta 1  225 ms

Also see bug 289669.

Comment 5

[x0]

Attachment: patch

This patch inlines the first call to SimpleMatch in ExecuteREBytecode and puts the switch outside the loop, so that every REOP gets its specialized search for an anchor in the string. The testcase is about 20% faster with the patch, but most important is the improvement for non-matching /^x/ with a long string (current code steps char for char through the string and tests for multiline everywhere).

The patch passes the test suite. Don't know who is the right person to review it.

Note that the case insensitive search at REOP_FLATi is now obviously inefficient (but still better than before). There should be a way to generally handle that better. Maybe the whole RegExp and the whole string could be uppercased before doing anything else (since there is no (?i:...)). But that's another bug (haven't searched for one yet).

Comment 6

[Håkan Waara]

Awesome.

Confirming and reassigning.

Comment 7

[Håkan Waara]

Comment on attachment 313847 [details] [diff] [review]
patch

Let's try brendan for review

Comment 8

[Brian Crowder]

If simplematch is not already being inlined, perhaps the right thing is a macro (shudder!)...  but WHY is it not?  It should be getting -force-inlined- now!

Comment 9

[Brian Crowder]

x0:  Can you create and test the -same- patch, except without the SimpleMatch inlining?  Also, how does this do on SunSpider?

Comment 10

[Brian Crowder]

Comment on attachment 313847 [details] [diff] [review]
patch

Stealing the review on this one too.  For sure, the cut-and-paste of code from SimpleMatch isn't going to fly, but there are some nice concepts here.

Comment 11

[x0]

SimpleMatch is being inlined with gcc. I don't know if it's being inlined on Windows, that was just a guess. I don't even know if it's really too slow on Windows.

The patch doesn't do much other than inlining SimpleMatch and optimizing it better than a compiler can, by shifting the switch outside the loop. That isn't possible without inlining.

Before I can test with SunSpider I have to figure out what that is.

Comment 12

[Jeff Walden [:Waldo]]

svn co http://svn.webkit.org/repository/webkit/trunk/SunSpider
Then take a look at SunSpider/sunspider.

Comment 13

[x0]

I ran it on the web: http://webkit.org/perf/sunspider-0.9/sunspider.html

2 runs without patch:
    4679.6ms +/- 1.1%
    4692.6ms +/- 0.5%

2 runs with patch:
    4636.4ms +/- 0.3%
    4657.0ms +/- 0.4%

Comment 14

[Brian Crowder]

If we're going to inline SimpleMatch like this, then we should do away with it as a function and make the rest of the state-machine use it properly.

Comment 15

[Robert Sayre]

(In reply to comment #14)
> If we're going to inline SimpleMatch like this, then we should do away with it
> as a function and make the rest of the state-machine use it properly.
> 

See bug 419225.

Comment 16

[Tom S [:evilpie]]

Current Nightly 34 ~ 35ms
Chrome 8 34ms

Comment 17

[Nicholas Nethercote [inactive]]

Tom, nice work closing out old bugs!