579173 - Use ropes to avoid large copies in simple string replace cases

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alan Pierce]

See bug 571549, comment 17, second paragraph. In regexp-dna, we're doing a very simple string replace on a huge string 11 times, and this takes up about 1/3 of the test (8ms on my machine, which is about 1.5% of SS as a whole) because we're copying the string over and over. This can be brought down to essentially zero time if we build a rope of substrings during string replacement and we allow replacement over ropes.

Comment 1

[Alan Pierce]

Attachment: Patch

This patch does flat replacement over ropes, where the string being matched is at most 8 characters.

In an attempt to avoid making small cases slower, I added some code to keep track of the number of nodes in a rope, and I only avoid flattening if the rope consists of relatively few large segments (more precisely, the ratio of string length to number of rope leaves is at least some constant). I wasn't able to measure any difference on SunSpider before/after this change; it's just meant to avoid the case where we get a rope with lots of small segments, which would slow down RopeMatch quite a bit. My replacement code has some potential for off-by-one errors, so it might be safer to not use the heuristic, so that my code gets exercised more.

JSStringBuilder is really simple right now (it just uses js_ConcatStrings), but it may be useful to modify it in the future to be used instead of JSCharBuffer in some cases.

Comment 2

[Alan Pierce]

Attachment: SunSpider before/after

regexp-dna is the main difference to notice here. string-unpack-code tends to fluctuate on my machine from small code changes, so that's probably why it changed here (it doesn't ever do the kind of replacement that this patch speeds up).

Comment 3

[Luke Wagner [:luke]]

Attachment: test RopeMatch perf

First, a general observation: this optimization will only apply to SS 0.9.1 (which removed the "g" argument to replace).  If we care about people measuring 0.9, we need to relax the "no optional arguments" limitation in tryFlatMatch.  Filed bug 580480 as a separate possible todo.

So I applied the patch and played around with it for a bit.  I think it is important to tune this isHeavyRope predicate.  E.g., in the attached micro-bench, the rope that is searched is heavy, but, due to the rope overhead, it runs 30% slower.  If you make s really long, then this overhead goes down, as you would expect.  So perhaps, while I review the rest of this patch, you can drill down on this and pick a nice safe, large, heavyRopeThreshold.  It would also make sense to make a similar benchmark for 'replace'.

Comment 4

[Alan Pierce]

Attachment: Alternate perf test

I think this perf test is more accurate. Yours has the issue that, in the regular replace case (where my code isn't run), we flatten the rope in the first iteration and then do fast matching at every later iteration. The real tradeoff is the cost of searching through a segmented rope vs. the cost of flattening the rope and searching through a flat string, so each replace/search call should be given a rope.

From experimentation on my test and similar ones, it looks like we break even at around 32 chars per rope node, both when searching and when doing replacements. Notice that my test does a replacement over 8 characters, which should produce the worst-case slowdown for my code.

Comment 5

[Luke Wagner [:luke]]

(In reply to comment #4)
> Created attachment 458981 [details]
> Alternate perf test
> 
> I think this perf test is more accurate. Yours has the issue that, in the
> regular replace case (where my code isn't run), we flatten the rope in the
> first iteration and then do fast matching at every later iteration.

Why would it be flattened?  I can verify, in a debugger, that it calls RopeMatch repeatedly.

Comment 6

[Luke Wagner [:luke]]

Attachment: tweak

So I've been looking over the patch and the code is clean and I like the JSStringBuilder and JSRopeIter abstractions.

A few things have been bothering me, though, and I took a stab at a solution to them all with the attached patch (which applies one top of the first replace patch)
1) this numNodes needs to be maintained in the hot concat-strings path for this one special case
2) the circular buffer length limits the pattern length where this optimization applies

So what the patch does is:
- remove the circular buffer and instead do the simple thing: match within a string using StringMatch, then use a nested for loops to match over the edge.
- because matching over the edge requires finding the next leaf, which can be slow, build a list of leaves ahead of time
- because building a list of leaves ahead of time can be slow if there are a lot of leaves, limit the number of leaves to rope->length() / SOME_CONSTANT, after which point RopeMatch just flattens and uses StringMatch.
- because the above limit achieves roughly the same thing as numNodes, remove numNodes.

On the "Alternate perf test" you attached, the time goes from 1186ms (original patch) to 940ms (with this patch on top).  SS doesn't show any change.  More testing/tweaking is probably required.

Comment 7

[Luke Wagner [:luke]]

Ah, duh, I misunderstood comment 4, which was referring to flattening occurring *without* the patch.

Comment 8

[Luke Wagner [:luke]]

Comment on attachment 458498 [details] [diff] [review]
Patch

Alan and I talked in person, and we are going with my posted modification.  This review assumes that it is applied:

Only minor nits below:

>+    if (size < sizeof(JSRopeBufferInfo))
>+        size = sizeof(JSRopeBufferInfo);

I didn't remove this in the patch, but I think it can go too.

>+            size_t matchEnd = match + g.patlen;

Can this be hoisted up with 'match'?

>+                    if (!leftSide)
>+                        return false;
>+                    if (!builder.append(cx, leftSide) ||
>+                        !builder.append(cx, repstr))
>+                        return false;

I know its not the most natural, but normal SM style is:

 if (!leftSide ||
     !builder.append(cx, leftSide) ||
     !builder.append(cx, repstr)) {
     return false;
 }

Don't you love how 'return false' aligns with the condition :P

>+                if (strEnd > matchEnd) {
>+                    JSString *rightSide = js_NewDependentString(cx, str,
>+                                          matchEnd - pos, strEnd - matchEnd);
>+                    if (!rightSide)
>+                        return false;
>+                    if (!builder.append(cx, rightSide))
>+                        return false;

Same as above, but also align js_NewDependentString's arguments with the opening ( like you did earlier.

>+        if (textstr->isInteriorNode())
>+            textstr->flatten();
>+        JSString *leftSide = js_NewDependentString(cx, textstr, 0, match);

js_NewDependentString seems to handle the textstr->isInteriorNode() case, so I think the 'if' can be removed.

>+        if (!rightSide)
>+            return false;
>+        if (!builder.append(cx, leftSide) ||
>+            !builder.append(cx, repstr) ||
>+            !builder.append(cx, rightSide))
>+            return false;

Same merging.

>diff --git a/js/src/jsstr.h b/js/src/jsstr.h
>--- a/js/src/jsstr.h
>+++ b/js/src/jsstr.h
> #include <ctype.h>
> #include "jsapi.h"
> #include "jsprvtd.h"
> #include "jshashtable.h"
>+
> #include "jslock.h"
> #include "jsobj.h"
> #include "jsvalue.h"

rm \n

>+class JSRopeIterator {

You named the other one JSRopeNodeIterator; perhaps JSRopeLeafIterator would be a clearer name for this one?

>+class JSStringBuilder {

Since this doesn't so much build a single string as a rope, perhaps JSRopeBuilder ?

If you can post the merged and revised patch, I'll do another quick once-over.

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> >+                    if (!leftSide)
> >+                        return false;
> >+                    if (!builder.append(cx, leftSide) ||
> >+                        !builder.append(cx, repstr))
> >+                        return false;
> 
> I know its not the most natural, but normal SM style is:
> 
>  if (!leftSide ||
>      !builder.append(cx, leftSide) ||
>      !builder.append(cx, repstr)) {
>      return false;
>  }
> 
> Don't you love how 'return false' aligns with the condition :P

That's true with or without the braces. The sanctioned optional-to-taste fix, first introduce by Norris Boyd in the '90s, is to put the { on its own line in the same column as the }. This is the only allowed exception to K&R brace style.

/be

Comment 10

[Alan Pierce]

Attachment: Patch

Complete patch, with the tweak. I haven't tuned the threshold ratio yet; I'll do that after posting this.

I incorporated Luke's changes to RopeMatch and addressed his comments.

RopeMatch uses Vector::append, which can fail, so I made RopeMatch propagate error and give the match index as an output argument. I also fixed a bug in RopeMatch (|pos + (t - text) - 1| should have been |pos + (t - chars) - 1|) and moved |text| one character forward to avoid a small redundancy in our checking.

Comment 11

[Brendan Eich [:brendan]]

Comment on attachment 459209 [details] [diff] [review]
Patch

Being a style kook here, don't mind me:

>+                 */
>+                if (strEnd > matchEnd) {
>+                    JSString *rightSide = js_NewDependentString(cx, str,
>+                                                                matchEnd - pos,
>+                                                                strEnd - matchEnd);
>+                    if (!rightSide ||
>+                        !builder.append(cx, rightSide)) {
>+                        return false;
>+                    }

Some or all of the above fits in 100 columns, which helps get rid of braces for the then clause.

Also notice how the || and overflowed condition line forces braces, taking four lines total, which is the same number of lines you get by uncommoning the return false and writing two ifs.

>+        JSString *rightSide = js_NewDependentString(cx, textstr,
>+                              match + g.patlen,
>+                              textstr->length() - match - g.patlen);

Args don't underhang correctly here.

/be

Comment 12

[Alan Pierce]

Attachment: Patch

I changed the error handling so that RopeMatch is infallible and if it fails to grow the vector of strings, it falls back to just doing StringMatch. I also added some tests for this code and addressed Brendan's style nits.

From some experimentation (on my test, using the search line instead of the replace line), it looks like 32 is a good cutoff for the density of a string after Luke's tweak.

Comment 13

[Luke Wagner [:luke]]

Comment on attachment 459301 [details] [diff] [review]
Patch

>+static jsint
>+RopeMatch(JSContext *cx, JSString *textstr, const jschar *pat, jsuint patlen)

Can remove 'cx' since its no longer needed for strs.

>+    /*
>+     * List of leaf nodes in the rope. If we run out of memory when trying to
>+     * append to this list, we can still fall back to StringMatch, so use the
>+     * system allocator so we don't report OOM in that case.
>+     */
>+    Vector<JSString *, 16, SystemAllocPolicy> strs;

Good catch!

>+        /*
>+         * Start searching at the first place where StringMatch wouldn't have
>+         * found the match, which is usually one character after
>+         * chars[len - patlen].
>+         */

'usually' is usually an unsettling thing to read in a comment, either explain the special case or delete after the ,

>+                    if (++innerp == strs.end()) {
>+                        return -1;
>+                    }

no braces needed

>+            /* Matched! */
>+
>+            return pos + (t - chars) - 1;  /* -1 because of *t++ above */

rm \n

>+        const jschar *text;
>+        size_t textlen;
>+        if (textstr->isTopNode()) {
>+            match = RopeMatch(mCx, textstr, pat, patlen);
>+        } else {
>+            textstr->getCharsAndLength(text, textlen);
>+            match = StringMatch(text, textlen, pat, patlen);
>+        }

Scoot text and textlen into the else branch.

>+        JSRopeLeafIterator iter(textstr);
>+        JSString *str = iter.init();
>+        size_t pos = 0;
>+        do {
 [snip]
>+            str = iter.next();
>+        } while (str);

When its not super-super-hot, I generally prefer to pay the additional branch and change do/while to for.  This loop calls js_NewDependent string, so I think we can afford to do:

  for (JSString *str = iter.init(); str; str = iter.next())
    ...

Nice work adding rope tests!

So that's just a bunch of nits.  Post the new version and I'll push it.

Comment 14

[Alan Pierce]

Attachment: Patch

I rebased and addressed comments. It's ready to be pushed.

Comment 15

[Alan Pierce]

Attachment: Patch

Fixed last-minute stupid mistake where I was calling iter.next() twice in BuildFlatReplacement.

Comment 16

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/0777c65f92c9

Comment 17

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/0777c65f92c9