Bug 609075 - speed up JSString::flatten a bit, part 2 (r=gal)
authorLuke Wagner <lw@mozilla.com>
Mon, 08 Nov 2010 14:35:30 -0800
changeset 57737 30cabba0038843063f057da722b032b1f9207df3
parent 57736 0ba07bd00178e01fea5d381e4dd7c1eb0be1bc04
child 57738 4b4dce1f1756d223d4028a5897cf5335d9851e85
push id1
push usershaver@mozilla.com
push dateTue, 04 Jan 2011 17:58:04 +0000
reviewersgal
bugs609075
milestone2.0b8pre
Bug 609075 - speed up JSString::flatten a bit, part 2 (r=gal)
js/src/jsstr.cpp
js/src/jsstr.h
js/src/jsutil.h
--- a/js/src/jsstr.cpp
+++ b/js/src/jsstr.cpp
@@ -100,93 +100,98 @@ js_GetStringChars(JSContext *cx, JSStrin
     if (!js_MakeStringImmutable(cx, str))
         return NULL;
     return str->flatChars();
 }
 
 void
 JSString::flatten()
 {
-    JSString *topNode;
-    jschar *chars;
-    size_t capacity;
     JS_ASSERT(isRope());
 
     /*
      * This can be called from any string in the rope, so first traverse to the
      * top node.
      */
-    topNode = this;
+    JSString *topNode = this;
     while (topNode->isInteriorNode())
         topNode = topNode->interiorNodeParent();
 
-#ifdef DEBUG
-    size_t length = topNode->length();
-#endif
-
-    capacity = topNode->topNodeCapacity();
-    chars = (jschar *) topNode->topNodeBuffer();
+    const size_t length = topNode->length();
+    const size_t capacity = topNode->topNodeCapacity();
+    jschar *const chars = (jschar *) topNode->topNodeBuffer();
 
     /*
-     * To make the traversal simpler, convert the top node to be marked as an
-     * interior node with a NULL parent, so that we end up at NULL when we are
-     * done processing it.
+     * To allow a homogeneous tree traversal, transform the top node into an
+     * internal node with null parent (which will be the stop condition).
      */
-    topNode->convertToInteriorNode(NULL);
-    JSString *str = topNode, *next;
-    size_t pos = 0;
+    topNode->e.mParent = NULL;
+#ifdef DEBUG
+    topNode->mLengthAndFlags = JSString::INTERIOR_NODE;
+#endif
 
     /*
-     * Traverse the tree, making each interior string dependent on the resulting
-     * string.
+     * Perform a depth-first tree traversal, splatting each node's characters
+     * into a contiguous buffer. Visit each node three times:
+     *  - the first time, record the position in the linear buffer, and recurse
+     *    into the left child.
+     *  - the second time, recurse into the right child.
+     *  - the third time, transform the node into a dependent string.
+     * To avoid maintaining a stack, tree nodes are mutated to indicate how
+     * many times they have been visited.
      */
-    while (str) {
-        switch (str->ropeTraversalCount()) {
-          case 0:
-            next = str->ropeLeft();
-
-            /*
-             * We know the "offset" field for the new dependent string now, but
-             * not later, so store it early. We have to be careful with this:
-             * mLeft is replaced by mOffset.
-             */
-            str->startTraversalConversion(chars, pos);
-            str->ropeIncrementTraversalCount();
+    JSString *str = topNode;
+    jschar *pos = chars;
+    while (true) {
+        /* Visiting the node for the first time. */
+        JS_ASSERT(str->isInteriorNode());
+        {
+            JSString *next = str->mLeft;
+            str->mChars = pos;  /* N.B. aliases mLeft */
             if (next->isInteriorNode()) {
+                str->mLengthAndFlags = 0x200;  /* N.B. flags invalidated */
                 str = next;
+                continue;  /* Visit node for the first time. */
             } else {
-                js_strncpy(chars + pos, next->chars(), next->length());
-                pos += next->length();
+                size_t len = next->length();
+                PodCopy(pos, next->mChars, len);
+                pos += len;
+                goto visit_right_child;
             }
-            break;
-          case 1:
-            next = str->ropeRight();
-            str->ropeIncrementTraversalCount();
+        }
+
+      revisit_parent:
+        if (str->mLengthAndFlags == 0x200) {
+          visit_right_child:
+            JSString *next = str->e.mRight;
             if (next->isInteriorNode()) {
+                str->mLengthAndFlags = 0x300;
                 str = next;
+                continue;  /* Visit 'str' for the first time. */
             } else {
-                js_strncpy(chars + pos, next->chars(), next->length());
-                pos += next->length();
+                size_t len = next->length();
+                PodCopy(pos, next->mChars, len);
+                pos += len;
+                goto finish_node;
             }
-            break;
-          case 2:
-            next = str->interiorNodeParent();
-            /* Make the string a dependent string dependent with the right fields. */
-            str->finishTraversalConversion(topNode, chars, pos);
+        } else {
+            JS_ASSERT(str->mLengthAndFlags == 0x300);
+          finish_node:
+            JSString *next = str->e.mParent;
+            str->finishTraversalConversion(topNode, pos);
+            if (!next) {
+                JS_ASSERT(pos == chars + length);
+                *pos = 0;
+                topNode->initFlatExtensible(chars, length, capacity);
+                return;
+            }
             str = next;
-            break;
-          default:
-            JS_NOT_REACHED("bad traversal count");
+            goto revisit_parent;  /* Visit 'str' for the second or third time */
         }
     }
-
-    JS_ASSERT(pos == length);
-    /* Set null terminator. */
-    chars[pos] = 0;
-    topNode->initFlatExtensible(chars, pos, capacity);
 }
 
 #ifdef JS_TRACER
 
 int32 JS_FASTCALL
 js_Flatten(JSString* str)
 {
     str->flatten();
@@ -348,18 +353,18 @@ js_ConcatStrings(JSContext *cx, JSString
     /*
      * To make traversal more manageable, we enforce that, unless the children
      * are leaves, the two children of a rope node must be distinct.
      */
     if (left == right && leftRopeTop) {
         left->flatten();
         leftRopeTop = false;
         rightRopeTop = false;
-        JS_ASSERT(leftLen = left->length());
-        JS_ASSERT(rightLen = right->length());
+        JS_ASSERT(leftLen == left->length());
+        JS_ASSERT(rightLen == right->length());
         JS_ASSERT(!left->isTopNode());
         JS_ASSERT(!right->isTopNode());
     }
 
     /*
      * There are 4 cases, based on whether on whether the left or right is a
      * rope or non-rope string.
      */
--- a/js/src/jsstr.h
+++ b/js/src/jsstr.h
@@ -185,22 +185,16 @@ struct JSString {
     /* Rope/non-rope can be checked by checking one bit. */
     static const size_t ROPE_BIT = JSSTRING_BIT(1);
 
     static const size_t ATOMIZED = JSSTRING_BIT(2);
     static const size_t EXTENSIBLE = JSSTRING_BIT(3);
 
     static const size_t FLAGS_LENGTH_SHIFT = 4;
 
-    static const size_t ROPE_TRAVERSAL_COUNT_SHIFT = 2;
-    static const size_t ROPE_TRAVERSAL_COUNT_MASK = JSSTRING_BITMASK(4) -
-                                                    JSSTRING_BITMASK(2);
-    static const size_t ROPE_TRAVERSAL_COUNT_UNIT =
-                                (1 << ROPE_TRAVERSAL_COUNT_SHIFT);
-
     static const size_t TYPE_MASK = JSSTRING_BITMASK(2);
     static const size_t TYPE_FLAGS_MASK = JSSTRING_BITMASK(4);
 
     inline bool hasFlag(size_t flag) const {
         return (mLengthAndFlags & flag) != 0;
     }
 
     inline js::gc::Cell *asCell() {
@@ -437,50 +431,22 @@ struct JSString {
         return e.mBufferWithInfo;
     }
 
     inline void nullifyTopNodeBuffer() {
         JS_ASSERT(isTopNode());
         e.mBufferWithInfo = NULL;
     }
 
-    /*
-     * When flattening a rope, we need to convert a rope node to a dependent
-     * string in two separate parts instead of calling initDependent.
-     */
-    inline void startTraversalConversion(jschar *chars, size_t offset) {
-        JS_ASSERT(isInteriorNode());
-        mChars = chars + offset;
-    }    
-
-    inline void finishTraversalConversion(JSString *base, jschar *chars,
-                                          size_t end) {
-        JS_ASSERT(isInteriorNode());
-        /* Note that setting flags also clears the traversal count. */
+    inline void finishTraversalConversion(JSString *base, jschar *end) {
         mLengthAndFlags = JSString::DEPENDENT |
-            ((chars + end - mChars) << JSString::FLAGS_LENGTH_SHIFT);
+                          ((end - mChars) << JSString::FLAGS_LENGTH_SHIFT);
         e.mBase = base;
     }
 
-    inline void ropeClearTraversalCount() {
-        JS_ASSERT(isRope());
-        mLengthAndFlags &= ~ROPE_TRAVERSAL_COUNT_MASK;
-    }
-
-    inline size_t ropeTraversalCount() const {
-        JS_ASSERT(isRope());
-        return (mLengthAndFlags & ROPE_TRAVERSAL_COUNT_MASK) >>
-                ROPE_TRAVERSAL_COUNT_SHIFT;
-    }
-
-    inline void ropeIncrementTraversalCount() {
-        JS_ASSERT(isRope());
-        mLengthAndFlags += ROPE_TRAVERSAL_COUNT_UNIT;
-    }
-
     inline bool ensureNotDependent(JSContext *cx) {
         return !isDependent() || undepend(cx);
     }
 
     inline void ensureNotRope() {
         if (isRope())
             flatten();
     }
--- a/js/src/jsutil.h
+++ b/js/src/jsutil.h
@@ -339,13 +339,25 @@ template <class T, size_t N> static void
 
 template <class T, size_t N>
 JS_ALWAYS_INLINE static void
 PodArrayZero(T (&t)[N])
 {
     memset(t, 0, N * sizeof(T));
 }
 
+template <class T>
+JS_ALWAYS_INLINE static void
+PodCopy(T *dst, T *src, size_t nelem)
+{
+    if (nelem < 128) {
+        for (T *srcend = src + nelem; src != srcend; ++src, ++dst)
+            *dst = *src;
+    } else {
+        memcpy(dst, src, nelem * sizeof(T));
+    }
+}
+
 } /* namespace js */
 
 #endif /* defined(__cplusplus) */
 
 #endif /* jsutil_h___ */