571549 - Concatenate strings lazily to avoid unnecessary copying and realloc calls

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alan Pierce]

From bug 565841 and bug 555395, we can save a lot of malloc/realloc and strncpy time in js_ConcatStrings by representing strings using ropes (really, it's just lazy concatenation instead of a fully-general rope, since the right thing to do is to flatten the string as soon as we use it).

This would win in the case where we build a large string by repeated concatenation, which is done a number of times in sunspider. It also helps in smaller cases by avoiding realloc calls and ensuring that we effectively always take the optimized path in js_ConcatStrings.

Lazy concatenation also makes it so concatenating to the front of a string over and over takes O(n) instead of O(n^2).

Comment 3

[Alan Pierce]

An annoying consequence of this change is that JSString::chars now has a possibility of failure, since it sometimes needs to malloc a buffer to flatten a rope, and it uses a worklist to traverse the tree.

chars is used in about 500 places in the code, and there are some places where it doesn't seem like there's a simple way to handle failure. One example is StringToNumberType in jsnum.h. Another issue is that the spec for the API call JS_GetStringChars does not specify an out-of-memory case.

I don't understand our error-handling mechanisms and strategy really well, so I'm not sure how to proceed here. Does anyone have any ideas for a clean way to handle this issue?

Comment 4

[Brendan Eich [:brendan]]

Alan: failure handling is an induction on these basis cases:

* You call *malloc or an equivalent allocating "primitive" and it returns null (do not duplicate an error report).

* You call a JS API or internal API that takes a leading cx and is fallible, i.e., returns null (if pointer return type) or null (otherwise) and it fails.

Inductive step: propagate failure return without duplicate reporting. There's no exception by which you can ignore a return value for a function taking a leading cx (or, recently, whose ctor took a cx and stashed it in a member).

Yes, JSString::chars has been designed as infallible.

/be

Comment 5

[Luke Wagner [:luke]]

So I think the underlying question is: if JSString::chars does lazy concatenation and has an OOM, do we
 1. change 500 JSString::chars callsites to make them handle and propagate OOM, or
 2. return a valid string of chars, but not the correct concatenation, assuming that someone very soon will OOM as well.

(1) seems awfully painful and still there doesn't seem to be any good solution to JS_GetStringChars.  So, I am in favor of (2).

Comment 6

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

Some call sites might actually not need it to be flattened, and could thereby call something like JSString::iterateChars for some winning.

500 is a big number either way, mind.

Comment 7

[Igor Bukanov]

(In reply to comment #5)
>  2. return a valid string of chars, but not the correct concatenation, assuming
> that someone very soon will OOM as well.

Flattening of two big strings could trigger OOM when there would be a lot of memory so OOM would not happen soon in other parts of code. So code would continue to execute but with unexpected semantics. I cannot rule out that a rogue script would not be able to take advantage of that for XSS attacks etc.

On the other hand if we create a char iterator that looks sufficiently similar to jschar *, we may convert all those callsites in semi-automatic mode.

Such iterator would have another benefit. It would allow to track all non-JSString pointers to JSString.chars and we can use a compacting GC for string chars. Currently this is not possible since GC would not know if the char array is referenced from a native stack, for example.

Comment 8

[David Mandelin [:dmandelin]]

(In reply to comment #5)
> So I think the underlying question is: if JSString::chars does lazy
> concatenation and has an OOM, do we
>  1. change 500 JSString::chars callsites to make them handle and propagate OOM,
> or
>  2. return a valid string of chars, but not the correct concatenation, assuming
> that someone very soon will OOM as well.
> 
> (1) seems awfully painful and still there doesn't seem to be any good solution
> to JS_GetStringChars.  So, I am in favor of (2).

If (2) is out, dare I suggest setjmp/longjmp for this sort of thing?

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> If (2) is out, dare I suggest setjmp/longjmp for this sort of thing?

We'll leak memory and leave stuck locks without RAII uber alles and static analysis back-up.

We should look harder at the chars calls -- some may be better served by a new API as noted in comments here.

/be

Comment 10

[Brendan Eich [:brendan]]

We could also return the bogus string on OOM to keep things "working" as we look at chars callsites.

/be

Comment 11

[Alan Pierce]

Attachment: Sunspider comparison

For reference, here are the performance changes with SunSpider (this is on top of Leary's yarr patch). It seems like small changes (running on a different machine, making small and even non-functional changes to jsstr.h, etc.) are making certain string tests get dramatically worse (up to 10%); the attached numbers are with a "stable" run where that doesn't happen to any of the tests. So, they may be a little optimistic.

Comment 12

[Alan Pierce]

For the chars issue, it turns out that there are really only 70 or 80 call sites ("chars" is a common local variable name, it seems, so it messed up the grep). That of course doesn't include the propagation that will occur, which would probably be significant.

There are a few problems with the iterator idea. We don't have parent pointers in the tree (since a string could be part of multiple trees and thus have multiple parents), so the iterator would need some kind of worklist to traverse, and creating and growing that worklist can fail, so we would be back to the original problem. Also, even getting the first character in a string without flattening it could have a nontrivial cost that would be repeated over and over, so it could hurt performance.

Comment 13

[Nicholas Nethercote [inactive]]

(In reply to comment #9)
> (In reply to comment #8)
> > If (2) is out, dare I suggest setjmp/longjmp for this sort of thing?
> 
> We'll leak memory and leave stuck locks without RAII uber alles and static
> analysis back-up.

I don't want to derail this bug, but avoiding OOM-reporting-via-JSBool-return-values is at the top of my SM fantasy wishlist... it causes a huge amount of distributed complexity, there are just so many lines of code that have to deal with it.

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #13)
> (In reply to comment #9)
> > (In reply to comment #8)
> > > If (2) is out, dare I suggest setjmp/longjmp for this sort of thing?
> > 
> > We'll leak memory and leave stuck locks without RAII uber alles and static
> > analysis back-up.
> 
> I don't want to derail this bug, but avoiding
> OOM-reporting-via-JSBool-return-values is at the top of my SM fantasy
> wishlist... it causes a huge amount of distributed complexity, there are just
> so many lines of code that have to deal with it.

See bug 508140 comment 13 at least. OOM checking for variable sized allocations is hard to avoid without fine-grained actor-like failure handling -- even a content rendering process in chromium is heavy enough that getting bogus image dimensions from the web shouldn't trivially crash such a process. Developers can easily (i.e., accidentally) trigger OOM in JS using Array and string hacks. These should not crash.

For small-enough and fixed-sized allocations, the e10s plan alluded to by Chris Jones in that comment is to monitor OS memory pressure and shake enough space loose that the small-ish allocation can be infallible. At the limit, you might have to exit a rendering proc. This is in the future still.

/be

Comment 15

[Igor Bukanov]

We do not need a char iterator. Rather we can have a buffer that would be suffieciently large to hold all flattened strings. The size of the buffer can be ensured when allocating the composed strings.

With such buffer we can update all the code that uses the chars with some autoclass. The autoclass would first tries to flatten the string. If that fails, the class would use the buffer to copy all the chars and release the storage in the destructor.

Comment 16

[Brendan Eich [:brendan]]

Word is that ropes don't win enough on SS and lose slightly on V8 benchmarks. If we aren't doing ropes, then on to plan B: static analysis to determine linearity (no more than one ref to the string on the left of +, so the JSString header as well as the buffer can be reused).

/be

Comment 17

[Alan Pierce]

(In reply to comment #15)
> We do not need a char iterator. Rather we can have a buffer that would be
> suffieciently large to hold all flattened strings.

The simple way to count the required size of the buffer is to add the "length" fields of all lazily concatenated strings, which in some cases (such as in SunSpider) means that we're allocating O(n^2) space, where n is the amount of space we actually need. There isn't any obvious way to get the buffer size down that works in all pathological cases with the current situation where every string concat is lazy.


After some investigation, it looks like in the regexp-dna SunSpider test (before Leary's patch) we spend 1/3 or so of our time in the last 2 lines, most of which is spent copying a megabyte-long string 11 times because we are repeatedly doing a string replace. WebKit's solution (which they should be ashamed of) runs almost instantly: they have special-case code for when the first argument of replace is a single character (which is always true in this test). When replacing over a rope, they just iterate through the individual strings in the rope without flattening it, and they do some constant-time string splicing to create a new rope at each match. This is only clean in the single-character case because otherwise, the string being searched for could span multiple strings in the rope.
The point of this is that we could do a similar thing (although hopefully something more general) to get a big win on that test, but we need a rope-like implementation first. So a workaround to the chars() issue discussed above may be worth it.


Luke and I came up with an idea for a variant on general ropes with an infallible chars function that seems to work (although it's a relatively new idea, so there may be some subtle problem with it). The idea is that the root of a rope keeps an empty buffer that's big enough to hold all the chars when the rope is flattened, and nodes in the middle of a rope do not keep any buffer. Nodes in the middle instead know their parent, and when getting the chars from such a string, we go to the root, flatten the entire rope, make the non-root strings dependent strings, and return a pointer to the appropriate place in the buffer.

If we try to do a concatenation and one of the arguments is in the middle of a rope (which is likely a rare case) then we create the entire new string. That way, we enforce that the ropes have a nice and simple structure, and any exceptions to this invariant cause allocation when concatenating strings, which is already a fallible operation.

Traversing a general tree with a work list can sometimes require heap memory (since there's no bound on the worklist size), so we need to either enforce that the tree is never big enough that a worklist traversal never requires more than some constant amount of space, or we could use the parent pointers in the tree to do the traversal.

Comment 18

[Alan Pierce]

Attachment: Sunspider before/after ropes and string replace change

This is after implementing ropes in a somewhat final way, and hacking together a special case (the case that WebKit does) of the string replacement change. v8 seems to have gotten a little better (8678ms down to 8603ms), but that may just be within the noise.

The changes in regexp-dna and string-tagcloud are from the replace change, and string-base64, string-unpack-code, and string-validate-input are from ropes.

Comment 19

[Alan Pierce]

Attachment: Ropes change (without string replacement change), almost ready for review

I still need to run a few more tests and fix a few outdated comments before the patch is ready for review.

A few design decisions:


The "length" field of strings is now packed in mFlags instead of having its own field. This lets us keep left child, right child, and parent pointers inside rope nodes while still keeping their length, and without growing the size of a string header.


To avoid a regression where we get n^2 running time on the following microbenchmark:
var s = "";
for (var i = 0; i < n; i++) {
    s += "a";
    s[0];
}
I leave some extra space when flattening ropes (currently I leave 5/4 of the necessary amount of space), and set a "capacity" field appropriately. When concatenating to a string that has enough capacity, I just write to the end, as we did before in string concatenation, but without the need for malloc/realloc calls. JSC (and I believe V8, although I'm not 100% sure) has a recent performance regression on this microbenchmark.


Rope traversal is done in constant space by following parent pointers and modifying a mutable "rope traversal count" in string headers. There are a few other constant-space ways to do tree traversal, but they all perform about the same empirically, and the one in the patch is nearly the same as what will be done to optimize string replacement.

Comment 20

[Alan Pierce]

Attachment: Ropes patch

Comment 21

[Igor Bukanov]

Comment on attachment 455806 [details] [diff] [review]
Ropes patch

General observation - the word root in the source currently refers to a GC root. Lets not add another meaning to it.

>+++ b/js/src/jsgc.cpp
>       case JSTRACE_STRING: {
...
>+        else if (str->isRope()) {
>+            if (str->isRopeNode())
>+                JS_CALL_STRING_TRACER(trc, str->ropeNodeParent(), "parent");
>+            JS_CALL_STRING_TRACER(trc, str->ropeLeft(), "left child");
>+            JS_CALL_STRING_TRACER(trc, str->ropeRight(), "right child");
>+        }
> 
>@@ -2307,26 +2313,28 @@ js_CallGCMarker(JSTracer *trc, void *thi
>     /*
>      * Optimize for string and double as their size is known and their tracing
>-     * is not recursive.
>+     * is often not recursive.
>      */
>       case JSTRACE_STRING:
>         for (;;) {
>+            if (((JSString *)thing)->isRope())
>+                break;

This is wrong - the code should explicitly deal here with left and right ropes similar to the js_TraceChildren ideally with tail recursion elimination for either left or right.

Comment 22

[Alan Pierce]

Attachment: Ropes patch, version 2

Changes:
-Made GC marking of rope nodes traverse the entire tree iteratively.
-Changed the terminology from "rope node" and "rope root" to "mid node" and "top node", and a "rope" node is now either a mid node or a top node.
-Fixed a bug where js_ConcatStrings could potentially trigger a GC and cause a malloced buffer to be double-freed.

Comment 23

[Andreas Gal :gal]

Comment on attachment 456510 [details] [diff] [review]
Ropes patch, version 2

>diff --git a/js/src/jsapi.cpp b/js/src/jsapi.cpp
>--- a/js/src/jsapi.cpp
>+++ b/js/src/jsapi.cpp
>@@ -5088,16 +5088,20 @@ JS_GetStringBytes(JSString *str)
> }
> 
> JS_PUBLIC_API(jschar *)
> JS_GetStringChars(JSString *str)
> {
>     size_t n, size;
>     jschar *s;
> 
>+    if (str->isRope())
>+        js_FlattenRope(str);

js::FlattenRope(str) or even better str->flatten().

>         if (str->isDependent())
>             JS_CALL_STRING_TRACER(trc, str->dependentBase(), "base");

{
} else if .. {
}

>+        else if (str->isRope()) {
>+            if (str->isMidNode())

Horrible name. Any better ideas?

>+                JS_CALL_STRING_TRACER(trc, str->midNodeParent(), "parent");
>+            JS_CALL_STRING_TRACER(trc, str->ropeLeft(), "left child");
>+            JS_CALL_STRING_TRACER(trc, str->ropeRight(), "right child");
>+        }
>         break;
>       }
> 
>+        /*
>+         * Iterate through all nodes and leaves in the rope if this is part of a
>+         * rope; otherwise, we only iterate once: on the string itself.
>+         */
>+        JSSafeRopeNodeIterator iter((JSString *) thing);

SafeRopeNodeIterator? Is there an Unsafe one?

>+        JSString *currentStr = iter.init();

How about just *str?

>+        do {
>+            for (;;) {
>+                if (JSString::isStatic(currentStr))
>+                    break;
>+                JS_ASSERT(kind == GetFinalizableThingTraceKind(currentStr));
>+                if (!MarkIfUnmarkedGCThing(currentStr))
>+                    break;
>+                if (currentStr->isDependent())
>+                    currentStr = currentStr->dependentBase();
>+                else
>+                    break;

if (!str->isDependent())
    break;

to match the style right above it.

>-    } else {
>+    } else if (str->isFlat()) {
>         /*
>          * flatChars for stillborn string is null, but cx->free would checks
>          * for a null pointer on its own.
>          */
>         cx->free(str->flatChars());
>+    } else if (str->isTopNode()) {
>+        cx->free(str->topNodeBuffer());
>     }
>+    /* Nothing to be done for rope mid nodes. */
> }

The branchiness here is going to kill GC mark performance. File a bug to put this stuff in separate arenas.

>+void
>+js_FlattenRope(JSString *str)
>+{
>+    JSString *currentStr, *nextStr;

str, next

>+    jschar *chars;
>+    size_t bufferCapacity;

capacity

Newline before major comments.

>+    /*
>+     * This can be called from any string in the rope, so first traverse to the
>+     * top node.
>+     */
>+    JS_ASSERT(str->isRope());
>+    while (str->isMidNode())
>+        str = str->midNodeParent();
>+
>+    size_t length = str->length();
>+
>+    bufferCapacity = str->topNodeCapacity();
>+    chars = (jschar *) str->topNodeBuffer();
>+
>+    if (bufferCapacity > 256) {
>+        /*
>+         * At this point, we have a buffer big enough to use to flatten the
>+         * string. Use realloc to shrink the allocated amount to what we
>+         * actually need. Leave a little bit of extra space so that
>+         * concatenating and observing a string repeatedly does not take n^2
>+         * time.
>+         */
>+        size_t shrinkCapacity = length + (length / 4);
>+        if (shrinkCapacity > bufferCapacity);
>+            shrinkCapacity = bufferCapacity;
>+            
>+        jschar *newChars =
>+            (jschar *) js_realloc(chars, (shrinkCapacity + 1) * sizeof(jschar));

Check how the original buffer was allocated. If that was cx->malloc you should use cx->realloc here, too.

>+    /*
>+     * Traverse the tree, making each interior string dependent on the resulting
>+     * string.
>+     */
>+    while (currentStr) {

Shorter name.

>+        switch (currentStr->ropeTraversalCount()) {
>+          case 0:
>+            /* We have to be careful here: mLeft is replaced by mOffset here. */
>+            nextStr = currentStr->ropeLeft();

Newline.

>+            /*
>+             * We know the "offset" field for the new dependent string now, but
>+             * not later, so store it early.
>+             */
>+            currentStr->startTraversalConversion(pos);
>+            currentStr->ropeIncrementTraversalCount();
>+            if (nextStr->isMidNode())
>+                currentStr = nextStr;

{
}

>+            else {
>+                js_strncpy(chars + pos, nextStr->chars(), nextStr->length());
>+                pos += nextStr->length();
>+            }
>+            break;
>+          case 1:
>+            nextStr = currentStr->ropeRight();
>+            currentStr->ropeIncrementTraversalCount();
>+            if (nextStr->isMidNode())
>+                currentStr = nextStr;

{
}

>+            else {
>+                js_strncpy(chars + pos, nextStr->chars(), nextStr->length());
>+                pos += nextStr->length();
>+            }
>+            break;
>+          case 2:
>+            nextStr = currentStr->midNodeParent();
>+            /* Make the string a dependent string dependent with the right fields. */
>+            currentStr->finishTraversalConversion(str, pos);
>+            currentStr = nextStr;
>+            break;
>+          default:
>+            JS_NOT_REACHED("bad traversal count");
>+        }
>+    }
>+
>+    JS_ASSERT(pos == length);
>+    /* Set null terminator. */
>+    chars[pos] = 0;
>+    str->initFlatMutable(chars, pos, bufferCapacity);
>+} 
>+ 
>+
>+    if (left->isMutable() && !right->isRope() &&
>+        left->flatCapacity() >= length) {
>+        JS_ASSERT(left->isFlat());

Newline.

>-        /* We can realloc left's space and make it depend on our result. */
>-        JS_ASSERT(left->isFlat());
>-        s = (jschar *) cx->realloc(ls, (ln + rn + 1) * sizeof(jschar));
>-        if (!s)
>-            return NULL;

This is what I meant. Strings should use cx->realloc for proper memory pressure accounting.

>+
>+    /*
>+     * There are 4 cases, based on whether on whether the left or right is a
>+     * rope or non-rope string. This can be handled in a general way, but it's
>+     * empirically a little faster and arguably simpler to handle each of the 4
>+     * cases independently and directly.
>+     */
>+
>+    /* Allocation sizes should grow exponentially to avoid repeated mallocs. */
>+#define COMPUTE_ALLOC_SIZE(sizeVar)                                            \
>+    (sizeVar) =                                                                \
>+        1 << (JS_CeilingLog2((length + 1) * sizeof(jschar)) + 1);              \
>+    cap = ((sizeVar) / sizeof(jschar)) - 1;                                    \
>+    JS_ASSERT((sizeVar) >= sizeof(JSRopeBufferInfo))

make it a function

>+
>+    /*
>+     * Try to reuse sourceBuffer. If it's not suitable, free it and create a
>+     * suitable buffer. usingLeft and usingRight should be literal booleans, and
>+     * we assume that the compiler will optimize their if statements out.
>+     */
>+#define OBTAIN_BUFFER(usingLeft, usingRight, sourceBuffer)                     \
>+    /*                                                                         \
>+     * We need to survive a GC upon failure and in case creating a new         \
>+     * string header triggers a GC, but we've broken the invariant that        \
>+     * rope top nodes always point to freeable JSRopeBufferInfo                \
>+     * objects, so make them point to NULL.                                    \
>+     */                                                                        \
>+    if (usingLeft)                                                             \
>+        left->nullifyTopNodeBuffer();                                          \
>+    if (usingRight)                                                            \
>+        right->nullifyTopNodeBuffer();                                         \
>+    if (length <= (sourceBuffer)->capacity) {                                  \
>+        buf = (sourceBuffer);                                                  \
>+    } else {                                                                   \
>+        size_t allocSize;                                                      \
>+        COMPUTE_ALLOC_SIZE(allocSize);                                         \
>+        cx->free(sourceBuffer);                                                \
>+        buf = (JSRopeBufferInfo *) cx->malloc(allocSize);                      \
>+        if (!buf)                                                              \
>+            return NULL;                                                       \
>+        buf->capacity = cap;                                                   \
>+    }

function

>+
>+#define FINISH_CONCAT(usingLeft, usingRight)                                   \
>+    res = js_NewGCString(cx);                                                  \
>+    if (!res) {                                                                \
>+        cx->free(buf);                                                         \
>+        return NULL;                                                           \
>+    }                                                                          \
>+    res->initTopNode(left, right, length, buf);                                \
>+    if (usingLeft)                                                             \
>+        left->convertToMidNode(res);                                           \
>+    if (usingRight)                                                            \
>+        right->convertToMidNode(res);
>+
>+        if (JS_UNLIKELY(rightRopeTop)) {
>+            /* Steal buffer from right if it's big enough. */
>+            JSRopeBufferInfo *rightBuf = right->topNodeBuffer();
>+
>+            OBTAIN_BUFFER(false, true, rightBuf);
>+            FINISH_CONCAT(false, true);
>+        } else {
>+            /* Need to make a new buffer. */
>+            size_t allocSize;
>+            COMPUTE_ALLOC_SIZE(allocSize);
>+            buf = (JSRopeBufferInfo *) cx->malloc(allocSize);
>+            if (!buf)
>+                return NULL;
>+
>+            buf->capacity = cap;
>+            FINISH_CONCAT(false, false);
>         }
>     }
> 
>-    return str;
>+    return res;
>+#undef COMPUTE_ALLOC_SIZE
>+#undef OBTAIN_BUFFER
>+#undef FINISH_CONCAT

Only use macros if there is no other way to do it.

>+    if (str->isRope())
>+        js_FlattenRope(str);

How about str->flattenIfRope(); or something like that? ensureNotRope()? That could subsume the assert below as well.

>     if (str->isDependent() && !js_UndependString(cx, str)) {

Since we are in town, we should probably also move this into str.

>         cond = JSVAL_TO_STRING(v)->length() != 0;
>-        x = lir->insLoad(LIR_ldp, v_ins, offsetof(JSString, mLength), ACC_OTHER);
>+        x = lir->ins2ImmI(LIR_rshup, lir->insLoad(LIR_ldp, v_ins,
>+                    offsetof(JSString, mLengthAndFlags), ACC_OTHER),
>+                    JSString::FLAGS_LENGTH_SHIFT);

Align this with the LIR_rshup.

>+    set(&v, lir->insEqP_0(lir->ins2ImmI(LIR_rshup, lir->insLoad(LIR_ldp, get(&v),
>+                            offsetof(JSString, mLengthAndFlags), ACC_OTHER),
>+                            JSString::FLAGS_LENGTH_SHIFT)));

Alignment here too.

Comment 24

[Andreas Gal :gal]

I can do the final review if luke has no objects, otherwise hit him again after the fixes.

Comment 25

[Alan Pierce]

Attachment: Ropes patch, version 3

Among other things, I changed "mid node" to "interior node", which is hopefully more clear, and I made it so we don't realloc our buffers smaller when flattening strings and changed the buffer growth pattern to be more like we do with arrays.

Comment 26

[Mike Shaver (:shaver -- probably not reading bugmail closely)]

(In reply to comment #25)
> Among other things, I changed "mid node" to "interior node", which is hopefully
> more clear

I like it, which trumps whatever opinion Andreas may develop. :-P

Comment 27

[Andreas Gal :gal]

Comment on attachment 457206 [details] [diff] [review]
Ropes patch, version 3

> 
>+    str->ensureNotRope();
>+    JS_ASSERT(str->isDependent() || str->isFlat());
>+

ensureNotRope should subsume this assert.

>+        switch (str->ropeTraversalCount()) {
>+          case 0:
>+            next = str->ropeLeft();

Newline.

Very nice patch. Can't wait to see it land.

Comment 28

[Alan Pierce]

Bug 579173 will track the string replacement change mentioned in comment 17.

Comment 29

[Alan Pierce]

Attachment: Rebased patch

Comment 30

[Luke Wagner [:luke]]

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

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 458021 [details] [diff] [review]
Rebased patch

> JSString * JS_FASTCALL
> js_ConcatStrings(JSContext *cx, JSString *left, JSString *right)
> {
 . . .
>+    /*
>+     * There are 4 cases, based on whether on whether the left or right is a
>+     * rope or non-rope string. This can be handled in a general way, but it's
>+     * empirically a little faster and arguably simpler to handle each of the 4
>+     * cases independently and directly.
>+     */
>+    if (leftRopeTop) {
>+        if (JS_UNLIKELY(rightRopeTop)) {
>+            JSRopeBufferInfo *leftBuf = left->topNodeBuffer();
>+            JSRopeBufferInfo *rightBuf = right->topNodeBuffer();
>+
>+            /* Attempt to steal the larger buffer. WLOG, it's the left one. */
>+            if (leftBuf->capacity >= rightBuf->capacity) {
>+                cx->free(rightBuf);
>+            } else {
>+                cx->free(leftBuf);
>+                leftBuf = rightBuf;
>+            }
>+
>+            JSRopeBufferInfo *buf = ObtainRopeBuffer(cx, true, true, leftBuf,
>+                                                     length, left, right);
>+            return FinishConcat(cx, true, true, left, right, length, buf);
>         } else {
>+            /* Steal buffer from left if it's big enough. */
>+            JSRopeBufferInfo *leftBuf = left->topNodeBuffer();
>+
>+            JSRopeBufferInfo *buf = ObtainRopeBuffer(cx, true, false, leftBuf,
>+                                                     length, left, right);
>+            return FinishConcat(cx, true, false, left, right, length, buf);
>         }
>     } else {
>+        if (JS_UNLIKELY(rightRopeTop)) {
>+            /* Steal buffer from right if it's big enough. */
>+            JSRopeBufferInfo *rightBuf = right->topNodeBuffer();
>+
>+            JSRopeBufferInfo *buf = ObtainRopeBuffer(cx, false, true, rightBuf,
>+                                                     length, left, right);
>+            return FinishConcat(cx, false, true, left, right, length, buf);
>+        } else {
>+            /* Need to make a new buffer. */
>+            size_t capacity;
>+            size_t allocSize = RopeAllocSize(length, &capacity);
>+            JSRopeBufferInfo *buf = (JSRopeBufferInfo *) cx->malloc(allocSize);
>+            if (!buf)
>+                return NULL;
>+
>+            buf->capacity = capacity;
>+            return FinishConcat(cx, false, false, left, right, length, buf);
>         }
>     }

Did gal really review this? :-/

Nits: else after return and consequent overindentation.

Non-nit: failure to OOM-check ObtainRopeBuffer return value. I think sayrer just ran into this trying to fix an unrelated bug involving last-ditch GC suppression on trace.

This needs a followup bug on file.

/be

Comment 32

[Brendan Eich [:brendan]]

Filed bug 598695.

/be