Closed Bug 509725 Opened 11 years ago Closed 11 years ago

use JSTempVector in String.prototype.replace

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
Tracking Status
status1.9.2 --- beta1-fixed

People

(Reporter: luke, Assigned: luke)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(2 files, 1 obsolete file)

Attached file 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.
Attached patch patch (obsolete) — Splinter Review
Attachment #393790 - Flags: review?(jwalden+bmo)
Blocks: 509826
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...
Attachment #393790 - Flags: review?(jwalden+bmo) → review+
Attached patch v.2Splinter Review
(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.
Attachment #393790 - Attachment is obsolete: true
Whiteboard: fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/b947ce74e235
Status: ASSIGNED → RESOLVED
Closed: 11 years ago
Resolution: --- → FIXED
Duplicate of this bug: 410445
You need to log in before you can comment on or make changes to this bug.