Bug 795165 - Rewrite ParallelArray toString from recursive to iterative (r=dvander)
authorShu-yu Guo <shu@rfrn.org>
Tue, 02 Oct 2012 11:33:45 -0700
changeset 115225 f1869aa32cba1c71b04827c8420c3b3423f65b0d
parent 115224 c15883431cbbae34eb80499a5c05ff30838d621d
child 115226 a6991bc0778d9cfe3a081f39627bd290fed71c49
push id1708
push userakeybl@mozilla.com
push dateMon, 19 Nov 2012 21:10:21 +0000
treeherdermozilla-beta@27b14fe50103 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdvander
bugs795165
milestone18.0a1
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 795165 - Rewrite ParallelArray toString from recursive to iterative (r=dvander)
js/src/builtin/ParallelArray-inl.h
js/src/builtin/ParallelArray.cpp
js/src/builtin/ParallelArray.h
js/src/jit-test/tests/parallelarray/toString-1.js
--- a/js/src/builtin/ParallelArray-inl.h
+++ b/js/src/builtin/ParallelArray-inl.h
@@ -23,16 +23,32 @@ ParallelArrayObject::IndexInfo::inBounds
     for (uint32_t d = 0; d < indices.length(); d++) {
         if (indices[d] >= dimensions[d])
             return false;
     }
 
     return true;
 }
 
+inline bool
+ParallelArrayObject::IndexInfo::bump()
+{
+    JS_ASSERT(isInitialized());
+    JS_ASSERT(indices.length() > 0);
+
+    uint32_t d = indices.length() - 1;
+    while (++indices[d] == dimensions[d]) {
+        if (d == 0)
+            return false;
+        indices[d--] = 0;
+    }
+
+    return true;
+}
+
 inline uint32_t
 ParallelArrayObject::IndexInfo::scalarLengthOfDimensions()
 {
     JS_ASSERT(isInitialized());
     return dimensions[0] * partialProducts[0];
 }
 
 inline uint32_t
--- a/js/src/builtin/ParallelArray.cpp
+++ b/js/src/builtin/ParallelArray.cpp
@@ -48,16 +48,52 @@ ReportBadArg(JSContext *cx, const char *
 bool
 ParallelArrayObject::IndexInfo::isInitialized() const
 {
     return (dimensions.length() > 0 &&
             indices.capacity() >= dimensions.length() &&
             partialProducts.length() == dimensions.length());
 }
 
+static inline bool
+OpenDelimiters(const IndexInfo &iv, StringBuffer &sb)
+{
+    JS_ASSERT(iv.isInitialized());
+
+    uint32_t d = iv.dimensions.length() - 1;
+    do {
+        if (iv.indices[d] != 0)
+            break;
+        if (!sb.append('<'))
+            return false;
+    } while (d-- > 0);
+
+    return true;
+}
+
+static inline bool
+CloseDelimiters(const IndexInfo &iv, StringBuffer &sb)
+{
+    JS_ASSERT(iv.isInitialized());
+
+    uint32_t d = iv.dimensions.length() - 1;
+    do {
+        if (iv.indices[d] != iv.dimensions[d] - 1) {
+            if (!sb.append(','))
+                return false;
+            break;
+        }
+
+        if (!sb.append('>'))
+            return false;
+    } while (d-- > 0);
+
+    return true;
+}
+
 // Check if obj is a parallel array, and if so, cast to pa and initialize
 // the IndexInfo accordingly.
 //
 // This function is designed to be used in conjunction with
 // GetElementFromArrayLikeObject; see below.
 static bool
 MaybeGetParallelArrayObjectAndLength(JSContext *cx, HandleObject obj,
                                      MutableHandle<ParallelArrayObject *> pa,
@@ -328,22 +364,21 @@ ParallelArrayObject::SequentialMode::bui
     JS_ASSERT(iv.isInitialized());
 
     uint32_t length = iv.scalarLengthOfDimensions();
 
     InvokeArgsGuard args;
     if (!cx->stack.pushInvokeArgs(cx, iv.dimensions.length(), &args))
         return ExecutionFailed;
 
-    for (uint32_t i = 0; i < length; i++) {
+    for (uint32_t i = 0; i < length; i++, iv.bump()) {
         args.setCallee(ObjectValue(*elementalFun));
         args.setThis(UndefinedValue());
 
         // Compute and set indices.
-        iv.fromScalar(i);
         for (size_t j = 0; j < iv.indices.length(); j++)
             args[j].setNumber(iv.indices[j]);
 
         if (!Invoke(cx, args))
             return ExecutionFailed;
 
         JSObject::setDenseArrayElementWithType(cx, buffer, i, args.rval());
     }
@@ -1102,17 +1137,18 @@ ParallelArrayObject::construct(JSContext
             return false;
     }
 
     // If the first argument wasn't a array-like or had no length, assume
     // empty parallel array, i.e. with shape being [0].
     if (iv.dimensions.length() == 0 && !iv.dimensions.append(0))
         return false;
 
-    if (!iv.initialize(0))
+    // Initialize with every dimension packed.
+    if (!iv.initialize(iv.dimensions.length()))
         return false;
 
     // Extract second argument, the elemental function.
     RootedObject elementalFun(cx, ValueToCallable(cx, &args[1]));
     if (!elementalFun)
         return false;
 
     // How long the flattened array will be.
@@ -1460,76 +1496,42 @@ ParallelArrayObject::dimensionsGetter(JS
 bool
 ParallelArrayObject::lengthGetter(JSContext *cx, CallArgs args)
 {
     args.rval().setNumber(as(&args.thisv().toObject())->outermostDimension());
     return true;
 }
 
 bool
-ParallelArrayObject::toStringBufferImpl(JSContext *cx, IndexInfo &iv, bool useLocale,
-                                        HandleObject buffer, StringBuffer &sb)
+ParallelArrayObject::toStringBuffer(JSContext *cx, bool useLocale, StringBuffer &sb)
 {
-    JS_ASSERT(iv.isInitialized());
-
-    // The dimension we're printing out.
-    uint32_t d = iv.indices.length() + 1;
-
-    // If we still have more dimensions to go.
-    if (d < iv.dimensions.length()) {
-        if (!sb.append('<'))
-            return false;
-
-        iv.indices.infallibleAppend(0);
-        uint32_t length = iv.dimensions[d - 1];
-        for (size_t i = 0; i < length; i++) {
-            iv.indices[d - 1] = i;
-            if (!toStringBufferImpl(cx, iv, useLocale, buffer, sb) ||
-                (i + 1 != length && !sb.append(',')))
-            {
-                return false;
-            }
-        }
-        iv.indices.shrinkBy(1);
-
-        if (!sb.append('>'))
-            return false;
-
-        return true;
-    }
-
-    // We're on the last dimension.
-    if (!sb.append('<'))
+    if (!JS_CHECK_OPERATION_LIMIT(cx))
         return false;
 
-    uint32_t offset;
-    uint32_t length;
+    RootedParallelArrayObject self(cx, this);
+    IndexInfo iv(cx);
 
-    // If the array is flat, we can just use the entire extent.
-    if (d == 1) {
-        offset = bufferOffset();
-        length = iv.dimensions[0];
-    } else {
-        offset = bufferOffset() + iv.toScalar();
-        length = iv.partialProducts[d - 2];
-    }
+    if (!self->getDimensions(cx, iv.dimensions) || !iv.initialize(iv.dimensions.length()))
+        return false;
+
+    uint32_t length = iv.scalarLengthOfDimensions();
 
     RootedValue tmp(cx);
     RootedValue localeElem(cx);
     RootedId id(cx);
 
-    const Value *start = buffer->getDenseArrayElements() + offset;
+    const Value *start = buffer()->getDenseArrayElements() + bufferOffset();
     const Value *end = start + length;
     const Value *elem;
 
-    for (elem = start; elem < end; elem++) {
+    for (elem = start; elem < end; elem++, iv.bump()) {
         // All holes in parallel arrays are eagerly filled with undefined.
         JS_ASSERT(!elem->isMagic(JS_ARRAY_HOLE));
 
-        if (!JS_CHECK_OPERATION_LIMIT(cx))
+        if (!OpenDelimiters(iv, sb))
             return false;
 
         if (!elem->isNullOrUndefined()) {
             if (useLocale) {
                 tmp = *elem;
                 RootedObject robj(cx, ToObject(cx, tmp));
                 if (!robj)
                     return false;
@@ -1541,38 +1543,24 @@ ParallelArrayObject::toStringBufferImpl(
                     return false;
                 }
             } else {
                 if (!ValueToStringBuffer(cx, *elem, sb))
                     return false;
             }
         }
 
-        if (elem + 1 != end && !sb.append(','))
+        if (!CloseDelimiters(iv, sb))
             return false;
     }
 
-    if (!sb.append('>'))
-        return false;
-
     return true;
 }
 
 bool
-ParallelArrayObject::toStringBuffer(JSContext *cx, bool useLocale, StringBuffer &sb)
-{
-    RootedParallelArrayObject self(cx, this);
-    IndexInfo iv(cx);
-    if (!iv.initialize(cx, self, 0))
-        return false;
-    RootedObject buffer(cx, this->buffer());
-    return toStringBufferImpl(cx, iv, useLocale, buffer, sb);
-}
-
-bool
 ParallelArrayObject::toString(JSContext *cx, CallArgs args)
 {
     StringBuffer sb(cx);
     if (!as(&args.thisv().toObject())->toStringBuffer(cx, false, sb))
         return false;
 
     if (JSString *str = sb.finishString()) {
         args.rval().setString(str);
--- a/js/src/builtin/ParallelArray.h
+++ b/js/src/builtin/ParallelArray.h
@@ -114,16 +114,20 @@ class ParallelArrayObject : public JSObj
         // The dimensions vector must be filled already, and space must be <=
         // dimensions.length().
         inline bool initialize(uint32_t space);
 
         // Load dimensions from a source, then initialize as above.
         inline bool initialize(JSContext *cx, HandleParallelArrayObject source,
                                uint32_t space);
 
+        // Bump the index by 1, wrapping over if necessary. Returns false when
+        // the increment would go out of bounds.
+        inline bool bump();
+
         // Get the scalar length according to the dimensions vector, i.e. the
         // product of the dimensions vector.
         inline uint32_t scalarLengthOfDimensions();
 
         // Compute the scalar index from the current index vector.
         inline uint32_t toScalar();
 
         // Set the index vector according to a scalar index.
@@ -317,19 +321,16 @@ class ParallelArrayObject : public JSObj
 #endif
 
     static JSFunctionSpec methods[];
     static Class protoClass;
 
     static inline bool DenseArrayToIndexVector(JSContext *cx, HandleObject obj,
                                                IndexVector &indices);
 
-    bool toStringBufferImpl(JSContext *cx, IndexInfo &iv, bool useLocale,
-                            HandleObject buffer, StringBuffer &sb);
-
     static bool create(JSContext *cx, MutableHandleValue vp);
     static bool create(JSContext *cx, HandleObject buffer, MutableHandleValue vp);
     static bool create(JSContext *cx, HandleObject buffer, uint32_t offset,
                        const IndexVector &dims, MutableHandleValue vp);
     static JSBool construct(JSContext *cx, unsigned argc, Value *vp);
 
     static bool map(JSContext *cx, CallArgs args);
     static bool reduce(JSContext *cx, CallArgs args);
--- a/js/src/jit-test/tests/parallelarray/toString-1.js
+++ b/js/src/jit-test/tests/parallelarray/toString-1.js
@@ -1,6 +1,6 @@
 function testToString() {
   var p = new ParallelArray();
-  assertEq(p.toString(), "<>");
+  assertEq(p.toString(), "");
 }
 
 testToString();