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 id17032
push userrsayre@mozilla.com
push dateWed, 17 Nov 2010 21:55:39 +0000
treeherdermozilla-central@78a42f77bb90 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgal
bugs609075
milestone2.0b8pre
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
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___ */