509725 - use JSTempVector in String.prototype.replace

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Luke Wagner [:luke]]

Attachment: synthetic benchmark

Currently, replace_glob (called by match_or_replace on every match) calls realloc() every time to a character buffer by an exact amount.  For n matches, this is O(n^2) copying.  This patch swaps in JSTempVector.

On SunSpider, this boosts string-tagcloud by 4% and string-unpack-code by 16%.

On the attached micro-benchmark, the largest gain is 53% and the lowest is 6%.  I had to make two small changes to prevent slowdown on the low-gain tests:
 - js_NewStringFromCharBuffer does a realloc if more than 25% of the buffer extracted from JSTempVector would be wasted.
 - JSTempVector::growBy does not zero-initialize POD elements.  Since this functionality only seems to be used when we'd like to fill the vector ourselves (instead of using the safer 'append' members), the zeroing is a waste.

Comment 1

[Luke Wagner [:luke]]

Attachment: patch

Comment 2

[Jeff Walden [:Waldo]]

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

>diff --git a/js/src/jsstr.cpp b/js/src/jsstr.cpp

> typedef struct ReplaceData {
>-    GlobData    base;           /* base struct state */
>-    JSObject    *lambda;        /* replacement function object or null */
>-    JSString    *repstr;        /* replacement string */
>-    jschar      *dollar;        /* null or pointer to first $ in repstr */
>-    jschar      *dollarEnd;     /* limit pointer for js_strchr_limit */
>-    jschar      *chars;         /* result chars, null initially */
>-    size_t      length;         /* result length, 0 initially */
>-    jsint       index;          /* index in result of next replacement */
>-    jsint       leftIndex;      /* left context index in base.str->chars */
>-    JSSubString dollarStr;      /* for "$$" interpret_dollar result */
>+    ReplaceData(JSContext *cx) : cb(cx) {}
>+    GlobData      base;           /* base struct state */
>+    JSObject      *lambda;        /* replacement function object or null */
>+    JSString      *repstr;        /* replacement string */
>+    jschar        *dollar;        /* null or pointer to first $ in repstr */
>+    jschar        *dollarEnd;     /* limit pointer for js_strchr_limit */
>+    jsint         index;          /* index in result of next replacement */
>+    jsint         leftIndex;      /* left context index in base.str->chars */
>+    JSSubString   dollarStr;      /* for "$$" interpret_dollar result */
>+    bool          globCalled;     /* record whether replace_glob has been called */
>+    JSCharVector  cb;             /* buffer built during match_or_replace */
> } ReplaceData;

While you're changing this, get rid of the unnecessary typedef.  Also, since sizeof(bool) != sizeof(uintptr_t) on Windows, there may be a decent bit of extra "slop" with this arrangement; switch the ordering of the last two members and that can be avoided.


>+#define MIN_WASTE_SIZE 16

const size_t please.


>+    /* For medium/big buffers, avoid wasting more than 1/4 of the memory. */
>+    if (capacity > MIN_WASTE_SIZE && capacity - length > (length >> 2)) {

Add a JS_ASSERT(capacity >= length) sanity check before this.

Post an updated patch and it's good to go...

Comment 3

[Luke Wagner [:luke]]

Attachment: v.2

(In reply to comment #2)

Thanks!

> While you're changing this, get rid of the unnecessary typedef.  Also, since
> sizeof(bool) != sizeof(uintptr_t) on Windows, there may be a decent bit of
> extra "slop" with this arrangement; switch the ordering of the last two members
> and that can be avoided.

Heh, I just did that on a new patch that depends on this one.  I'll do the reordering there too.

Comment 4

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/b947ce74e235

Comment 5

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/b947ce74e235

Comment 7

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/7770e7c0ae3f