Bug 701560 - template version of merge sort. r=luke
☠☠ backed out by db3258e6b552 ☠ ☠
authorIgor Bukanov <igor@mir2.org>
Wed, 16 Nov 2011 15:00:32 +0100
changeset 80472 e1587f23d2f043939d96ee3b75869dd6fa18ab76
parent 80471 cde201b0e581535ae5ae3160431eb31382593525
child 80473 db3258e6b552fb9858dccc3af8cd8c00030f2e4f
push id21500
push userbmo@edmorley.co.uk
push dateSat, 19 Nov 2011 13:04:35 +0000
treeherdermozilla-central@46c2bd7dbdd4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersluke
bugs701560
milestone11.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 701560 - template version of merge sort. r=luke
js/src/ds/Sort.h
js/src/jsarray.cpp
js/src/jsarray.h
js/src/jsopcode.cpp
new file mode 100644
--- /dev/null
+++ b/js/src/ds/Sort.h
@@ -0,0 +1,170 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=4 sw=4 et tw=99 ft=cpp:
+ *
+ * ***** BEGIN LICENSE BLOCK *****
+ * Version: MPL 1.1/GPL 2.0/LGPL 2.1
+ *
+ * The contents of this file are subject to the Mozilla Public License Version
+ * 1.1 (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ * http://www.mozilla.org/MPL/
+ *
+ * Software distributed under the License is distributed on an "AS IS" basis,
+ * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
+ * for the specific language governing rights and limitations under the
+ * License.
+ *
+ * The Original Code is SpiderMonkey JavaScript engine.
+ *
+ * The Initial Developer of the Original Code is
+ * Mozilla Corporation.
+ * Portions created by the Initial Developer are Copyright (C) 2011
+ * the Initial Developer. All Rights Reserved.
+ *
+ * Contributor(s):
+ *
+ * Alternatively, the contents of this file may be used under the terms of
+ * either the GNU General Public License Version 2 or later (the "GPL"), or
+ * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
+ * in which case the provisions of the GPL or the LGPL are applicable instead
+ * of those above. If you wish to allow use of your version of this file only
+ * under the terms of either the GPL or the LGPL, and not to allow others to
+ * use your version of this file under the terms of the MPL, indicate your
+ * decision by deleting the provisions above and replace them with the notice
+ * and other provisions required by the GPL or the LGPL. If you do not delete
+ * the provisions above, a recipient may use your version of this file under
+ * the terms of any one of the MPL, the GPL or the LGPL.
+ *
+ * ***** END LICENSE BLOCK ***** */
+
+#ifndef Sort_h__
+#define Sort_h__
+
+#include "jstypes.h"
+
+namespace js {
+
+namespace detail {
+
+template<typename T>
+JS_ALWAYS_INLINE void
+CopyNonEmptyArray(T *dst, const T *src, size_t nelems)
+{
+    JS_ASSERT(nelems != 0);
+    const T *end = src + nelems;
+    do {
+        *dst++ = *src++;
+    } while (src != end);
+}
+
+/* Helper function for MergeSort. */
+template<typename T, typename Comparator>
+JS_ALWAYS_INLINE bool
+MergeArrayRuns(T *dst, const T *src, size_t run1, size_t run2, Comparator c)
+{
+    JS_ASSERT(run1 >= 1);
+    JS_ASSERT(run2 >= 1);
+
+    /* Copy runs already in sorted order. */
+    const T *b = src + run1;
+    bool lessOrEqual;
+    if (!c(b[-1],  b[0], &lessOrEqual))
+        return false;
+
+    if (!lessOrEqual) {
+        /* Runs are not already sorted, merge them. */
+        for (const T *a = src;;) {
+            if (!c(*a, *b, &lessOrEqual))
+                return false;
+            if (lessOrEqual) {
+                *dst++ = *a++;
+                if (!--run1) {
+                    src = b;
+                    break;
+                }
+            } else {
+                *dst++ = *b++;
+                if (!--run2) {
+                    src = a;
+                    break;
+                }
+            }
+        }
+    }
+    CopyNonEmptyArray(dst, src, run1 + run2);
+    return true;
+}
+
+} /* namespace detail */
+
+/*
+ * Sort the array using the merge sort algorithm. The scratch should point to
+ * a temporary storage that can hold nelems elements.
+ *
+ * The comparator must provide the () operator with the following signature:
+ *
+ *     bool operator()(const T& a, const T& a, bool *lessOrEqualp);
+ *
+ * It should return true on success and sets lessOrEqualp to the result of
+ * a <= b operation. If it returns false, the sort terminates immediately with
+ * the false result. In this case the content of the array and scratch is
+ * arbitrary.
+ */
+template<typename T, typename Comparator>
+bool
+MergeSort(T *array, size_t nelems, T *scratch, Comparator c)
+{
+    const size_t INS_SORT_LIMIT = 3;
+
+    if (nelems <= 1)
+        return true;
+
+    /*
+     * Apply insertion sort to small chunks to reduce the number of merge
+     * passes needed.
+     */
+    for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
+        size_t hi = lo + INS_SORT_LIMIT;
+        if (hi >= nelems)
+            hi = nelems;
+        for (size_t i = lo + 1; i != hi; i++) {
+            for (size_t j = i; ;) {
+                bool lessOrEqual;
+                if (!c(array[j - 1], array[j], &lessOrEqual))
+                    return false;
+                if (lessOrEqual)
+                    break;
+                T tmp = array[j - 1];
+                array[j - 1] = array[j];
+                array[j] = tmp;
+                if (--j == lo)
+                    break;
+            }
+        }
+    }
+
+    T *vec1 = array;
+    T *vec2 = scratch;
+    for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
+        for (size_t lo = 0; lo < nelems; lo += 2 * run) {
+            size_t hi = lo + run;
+            if (hi >= nelems) {
+                detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
+                break;
+            }
+            size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
+            if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c))
+                return false;
+        }
+        T *swap = vec1;
+        vec1 = vec2;
+        vec2 = swap;
+    }
+    if (vec1 == scratch)
+        detail::CopyNonEmptyArray(array, scratch, nelems);
+    return true;
+}
+
+} /* namespace js */
+
+#endif
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -126,16 +126,18 @@
 #include "jstracer.h"
 #include "jswrapper.h"
 #include "methodjit/MethodJIT.h"
 #include "methodjit/StubCalls.h"
 #include "methodjit/StubCalls-inl.h"
 
 #include "vm/ArgumentsObject.h"
 
+#include "ds/Sort.h"
+
 #include "jsarrayinlines.h"
 #include "jsatominlines.h"
 #include "jscntxtinlines.h"
 #include "jsobjinlines.h"
 #include "jsscopeinlines.h"
 #include "jscntxtinlines.h"
 #include "jsstrinlines.h"
 
@@ -183,18 +185,18 @@ namespace js {
  *
  * An id is an array index according to ECMA by (15.4):
  *
  * "Array objects give special treatment to a certain class of property names.
  * A property name P (in the form of a string value) is an array index if and
  * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
  * to 2^32-1."
  *
- * This means the largest allowed index is actually 2^32-2 (4294967294).  
- * 
+ * This means the largest allowed index is actually 2^32-2 (4294967294).
+ *
  * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
  * except that by using signed 31-bit integers we miss the top half of the
  * valid range. This function checks the string representation itself; note
  * that calling a standard conversion routine might allow strings such as
  * "08" or "4.0" as array indices, which they are not.
  *
  */
 JS_FRIEND_API(bool)
@@ -202,40 +204,40 @@ StringIsArrayIndex(JSLinearString *str, 
 {
     const jschar *s = str->chars();
     uint32 length = str->length();
     const jschar *end = s + length;
 
     if (length == 0 || length > (sizeof("4294967294") - 1) || !JS7_ISDEC(*s))
         return false;
 
-    uint32 c = 0, previous = 0;    
+    uint32 c = 0, previous = 0;
     uint32 index = JS7_UNDEC(*s++);
 
     /* Don't allow leading zeros. */
     if (index == 0 && s != end)
         return false;
 
     for (; s < end; s++) {
         if (!JS7_ISDEC(*s))
             return false;
 
         previous = index;
         c = JS7_UNDEC(*s);
         index = 10 * index + c;
     }
 
     /* Make sure we didn't overflow. */
-    if (previous < (MAX_ARRAY_INDEX / 10) || (previous == (MAX_ARRAY_INDEX / 10) && 
+    if (previous < (MAX_ARRAY_INDEX / 10) || (previous == (MAX_ARRAY_INDEX / 10) &&
         c <= (MAX_ARRAY_INDEX % 10))) {
         JS_ASSERT(index <= MAX_ARRAY_INDEX);
         *indexp = index;
         return true;
     }
-    
+
     return false;
 }
 
 }
 
 static JSBool
 BigIndexToId(JSContext *cx, JSObject *obj, jsuint index, JSBool createAtom,
              jsid *idp)
@@ -1975,264 +1977,131 @@ array_reverse(JSContext *cx, uintN argc,
             !SetOrDeleteArrayElement(cx, obj, i, hole2, hival)) {
             return false;
         }
     }
     args.rval().setObject(*obj);
     return true;
 }
 
-typedef struct MSortArgs {
-    size_t       elsize;
-    JSComparator cmp;
-    void         *arg;
-    JSBool       isValue;
-} MSortArgs;
-
-/* Helper function for js_MergeSort. */
-static JSBool
-MergeArrays(MSortArgs *msa, void *src, void *dest, size_t run1, size_t run2)
-{
-    void *arg, *a, *b, *c;
-    size_t elsize, runtotal;
-    int cmp_result;
-    JSComparator cmp;
-    JSBool isValue;
-
-    runtotal = run1 + run2;
-
-    elsize = msa->elsize;
-    cmp = msa->cmp;
-    arg = msa->arg;
-    isValue = msa->isValue;
-
-#define CALL_CMP(a, b) \
-    if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
-
-    /* Copy runs already in sorted order. */
-    b = (char *)src + run1 * elsize;
-    a = (char *)b - elsize;
-    CALL_CMP(a, b);
-    if (cmp_result <= 0) {
-        memcpy(dest, src, runtotal * elsize);
-        return JS_TRUE;
-    }
-
-#define COPY_ONE(p,q,n) \
-    (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
-
-    a = src;
-    c = dest;
-    for (; runtotal != 0; runtotal--) {
-        JSBool from_a = run2 == 0;
-        if (!from_a && run1 != 0) {
-            CALL_CMP(a,b);
-            from_a = cmp_result <= 0;
-        }
-
-        if (from_a) {
-            COPY_ONE(c, a, elsize);
-            run1--;
-            a = (char *)a + elsize;
-        } else {
-            COPY_ONE(c, b, elsize);
-            run2--;
-            b = (char *)b + elsize;
-        }
-        c = (char *)c + elsize;
-    }
-#undef COPY_ONE
-#undef CALL_CMP
-
-    return JS_TRUE;
-}
-
-/*
- * This sort is stable, i.e. sequence of equal elements is preserved.
- * See also bug #224128.
- */
-bool
-js_MergeSort(void *src, size_t nel, size_t elsize,
-             JSComparator cmp, void *arg, void *tmp,
-             JSMergeSortElemType elemType)
+namespace {
+
+inline bool
+CompareStringValues(JSContext *cx, const Value &a, const Value &b, bool *lessOrEqualp)
 {
-    void *swap, *vec1, *vec2;
-    MSortArgs msa;
-    size_t i, j, lo, hi, run;
-    int cmp_result;
-
-    JS_ASSERT_IF(JS_SORTING_VALUES, elsize == sizeof(Value));
-    bool isValue = elemType == JS_SORTING_VALUES;
-
-    /* Avoid memcpy overhead for word-sized and word-aligned elements. */
-#define COPY_ONE(p,q,n) \
-    (isValue ? (void)(*(Value*)p = *(Value*)q) : (void)memcpy(p, q, n))
-#define CALL_CMP(a, b) \
-    if (!cmp(arg, (a), (b), &cmp_result)) return JS_FALSE;
-#define INS_SORT_INT 4
-
-    /*
-     * Apply insertion sort to small chunks to reduce the number of merge
-     * passes needed.
-     */
-    for (lo = 0; lo < nel; lo += INS_SORT_INT) {
-        hi = lo + INS_SORT_INT;
-        if (hi >= nel)
-            hi = nel;
-        for (i = lo + 1; i < hi; i++) {
-            vec1 = (char *)src + i * elsize;
-            vec2 = (char *)vec1 - elsize;
-            for (j = i; j > lo; j--) {
-                CALL_CMP(vec2, vec1);
-                /* "<=" instead of "<" insures the sort is stable */
-                if (cmp_result <= 0) {
-                    break;
-                }
-
-                /* Swap elements, using "tmp" as tmp storage */
-                COPY_ONE(tmp, vec2, elsize);
-                COPY_ONE(vec2, vec1, elsize);
-                COPY_ONE(vec1, tmp, elsize);
-                vec1 = vec2;
-                vec2 = (char *)vec1 - elsize;
-            }
-        }
+    if (!JS_CHECK_OPERATION_LIMIT(cx))
+        return false;
+
+    JSString *astr = a.toString();
+    JSString *bstr = b.toString();
+    int32 result;
+    if (!CompareStrings(cx, astr, bstr, &result))
+        return false;
+
+    *lessOrEqualp = (result <= 0);
+    return true;
+}
+
+struct SortComparatorStrings {
+    JSContext   *const cx;
+
+    SortComparatorStrings(JSContext *cx)
+      : cx(cx) {}
+
+    bool operator()(const Value &a, const Value &b, bool *lessOrEqualp) {
+        return CompareStringValues(cx, a, b, lessOrEqualp);
     }
-#undef CALL_CMP
-#undef COPY_ONE
-
-    msa.elsize = elsize;
-    msa.cmp = cmp;
-    msa.arg = arg;
-    msa.isValue = isValue;
-
-    vec1 = src;
-    vec2 = tmp;
-    for (run = INS_SORT_INT; run < nel; run *= 2) {
-        for (lo = 0; lo < nel; lo += 2 * run) {
-            hi = lo + run;
-            if (hi >= nel) {
-                memcpy((char *)vec2 + lo * elsize, (char *)vec1 + lo * elsize,
-                       (nel - lo) * elsize);
-                break;
-            }
-            if (!MergeArrays(&msa, (char *)vec1 + lo * elsize,
-                             (char *)vec2 + lo * elsize, run,
-                             hi + run > nel ? nel - hi : run)) {
-                return JS_FALSE;
-            }
-        }
-        swap = vec1;
-        vec1 = vec2;
-        vec2 = swap;
+};
+
+struct StringValuePair {
+    Value   str;
+    Value   v;
+};
+
+struct SortComparatorStringValuePairs {
+    JSContext   *const cx;
+
+    SortComparatorStringValuePairs(JSContext *cx)
+      : cx(cx) {}
+
+    bool operator()(const StringValuePair &a, const StringValuePair &b, bool *lessOrEqualp) {
+        return CompareStringValues(cx, a.str, b.str, lessOrEqualp);
     }
-    if (src != vec1)
-        memcpy(src, tmp, nel * elsize);
-
-    return JS_TRUE;
-}
-
-struct CompareArgs
+};
+
+struct SortComparatorFunction {
+    JSContext          *const cx;
+    const Value        &fval;
+    InvokeArgsGuard    &ag;
+
+    SortComparatorFunction(JSContext *cx, const Value &fval, InvokeArgsGuard &ag)
+      : cx(cx), fval(fval), ag(ag) { }
+
+    bool JS_REQUIRES_STACK operator()(const Value &a, const Value &b, bool *lessOrEqualp);
+};
+
+bool
+SortComparatorFunction::operator()(const Value &a, const Value &b, bool *lessOrEqualp)
 {
-    JSContext          *context;
-    InvokeArgsGuard    args;
-    Value              fval;
-
-    CompareArgs(JSContext *cx, Value fval)
-      : context(cx), fval(fval)
-    {}
-};
-
-static JS_REQUIRES_STACK JSBool
-sort_compare(void *arg, const void *a, const void *b, int *result)
-{
-    const Value *av = (const Value *)a, *bv = (const Value *)b;
-    CompareArgs *ca = (CompareArgs *) arg;
-    JSContext *cx = ca->context;
-
     /*
      * array_sort deals with holes and undefs on its own and they should not
      * come here.
      */
-    JS_ASSERT(!av->isMagic() && !av->isUndefined());
-    JS_ASSERT(!av->isMagic() && !bv->isUndefined());
+    JS_ASSERT(!a.isMagic() && !a.isUndefined());
+    JS_ASSERT(!a.isMagic() && !b.isUndefined());
 
     if (!JS_CHECK_OPERATION_LIMIT(cx))
-        return JS_FALSE;
-
-    InvokeArgsGuard &ag = ca->args;
+        return false;
+
     if (!ag.pushed() && !cx->stack.pushInvokeArgs(cx, 2, &ag))
-        return JS_FALSE;
+        return false;
         
-    ag.setCallee(ca->fval);
+    ag.setCallee(fval);
     ag.thisv() = UndefinedValue();
-    ag[0] = *av;
-    ag[1] = *bv;
+    ag[0] = a;
+    ag[1] = b;
 
     if (!Invoke(cx, ag))
-        return JS_FALSE;
+        return false;
 
     jsdouble cmp;
     if (!ToNumber(cx, ag.rval(), &cmp))
-        return JS_FALSE;
-
-    /* Clamp cmp to -1, 0, 1. */
-    *result = 0;
-    if (!JSDOUBLE_IS_NaN(cmp) && cmp != 0)
-        *result = cmp > 0 ? 1 : -1;
+        return false;
 
     /*
-     * XXX else report some kind of error here?  ECMA talks about 'consistent
-     * compare functions' that don't return NaN, but is silent about what the
-     * result should be.  So we currently ignore it.
+     * XXX eport some kind of error here if cmp is NaN? ECMA talks about
+     * 'consistent compare functions' that don't return NaN, but is silent
+     * about what the result should be. So we currently ignore it.
      */
-
-    return JS_TRUE;
+    *lessOrEqualp = (JSDOUBLE_IS_NaN(cmp) || cmp <= 0);
+    return true;
 }
 
-typedef JSBool (JS_REQUIRES_STACK *JSRedComparator)(void*, const void*,
-                                                    const void*, int *);
-
-static inline JS_IGNORE_STACK JSComparator
-comparator_stack_cast(JSRedComparator func)
-{
-    return func;
-}
-
-static int
-sort_compare_strings(void *arg, const void *a, const void *b, int *result)
-{
-    JSContext *cx = (JSContext *)arg;
-    JSString *astr = ((const Value *)a)->toString();
-    JSString *bstr = ((const Value *)b)->toString();
-    return JS_CHECK_OPERATION_LIMIT(cx) && CompareStrings(cx, astr, bstr, result);
-}
+} /* namespace anonymous */
 
 JSBool
 js::array_sort(JSContext *cx, uintN argc, Value *vp)
 {
-    jsuint len, newlen, i, undefs;
-    size_t elemsize;
-    JSString *str;
-    
     CallArgs args = CallArgsFromVp(argc, vp);
     Value fval;
     if (args.length() > 0 && !args[0].isUndefined()) {
         if (args[0].isPrimitive()) {
             JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_BAD_SORT_ARG);
             return false;
         }
         fval = args[0];     /* non-default compare function */
     } else {
         fval.setNull();
     }
 
     JSObject *obj = ToObject(cx, &args.thisv());
     if (!obj)
         return false;
+
+    jsuint len;
     if (!js_GetLengthProperty(cx, obj, &len))
         return false;
     if (len == 0) {
         args.rval().setObject(*obj);
         return true;
     }
 
     /*
@@ -2252,197 +2121,140 @@ js::array_sort(JSContext *cx, uintN argc
      * Initialize vec as a root. We will clear elements of vec one by
      * one while increasing the rooted amount of vec when we know that the
      * property at the corresponding index exists and its value must be rooted.
      *
      * In this way when sorting a huge mostly sparse array we will not
      * access the tail of vec corresponding to properties that do not
      * exist, allowing OS to avoiding committing RAM. See bug 330812.
      */
+    size_t n, undefs;
     {
-        Value *vec = (Value *) cx->malloc_(2 * size_t(len) * sizeof(Value));
-        if (!vec)
+        AutoValueVector vec(cx);
+        if (!vec.reserve(2 * size_t(len)))
             return false;
 
-        DEFINE_LOCAL_CLASS_OF_STATIC_FUNCTION(AutoFreeVector) {
-            JSContext *const cx;
-            Value *&vec;
-           public:
-            AutoFreeVector(JSContext *cx, Value *&vec) : cx(cx), vec(vec) { }
-            ~AutoFreeVector() {
-                cx->free_(vec);
-            }
-        } free_(cx, vec);
-
-        AutoArrayRooter tvr(cx, 0, vec);
-
         /*
          * By ECMA 262, 15.4.4.11, a property that does not exist (which we
          * call a "hole") is always greater than an existing property with
          * value undefined and that is always greater than any other property.
          * Thus to sort holes and undefs we simply count them, sort the rest
          * of elements, append undefs after them and then make holes after
          * undefs.
          */
         undefs = 0;
-        newlen = 0;
         bool allStrings = true;
-        for (i = 0; i < len; i++) {
+        for (size_t i = 0; i < len; i++) {
             if (!JS_CHECK_OPERATION_LIMIT(cx))
                 return false;
 
             /* Clear vec[newlen] before including it in the rooted set. */
             JSBool hole;
-            vec[newlen].setNull();
-            tvr.changeLength(newlen + 1);
-            if (!GetElement(cx, obj, i, &hole, &vec[newlen]))
+            Value v;
+            if (!GetElement(cx, obj, i, &hole, &v))
                 return false;
-
             if (hole)
                 continue;
-
-            if (vec[newlen].isUndefined()) {
+            if (v.isUndefined()) {
                 ++undefs;
                 continue;
             }
-
-            allStrings = allStrings && vec[newlen].isString();
-
-            ++newlen;
+            vec.infallibleAppend(v);
+            allStrings = allStrings && v.isString();
         }
 
-        if (newlen == 0) {
+        n = vec.length();
+        if (n == 0) {
             args.rval().setObject(*obj);
             return true; /* The array has only holes and undefs. */
         }
 
-        /*
-         * The first newlen elements of vec are copied from the array object
-         * (above). The remaining newlen positions are used as GC-rooted scratch
-         * space for mergesort. We must clear the space before including it to
-         * the root set covered by tvr.count.
-         */
-        Value *mergesort_tmp = vec + newlen;
-        MakeRangeGCSafe(mergesort_tmp, newlen);
-        tvr.changeLength(newlen * 2);
-
-        /* Here len == 2 * (newlen + undefs + number_of_holes). */
+        JS_ALWAYS_TRUE(vec.resize(n * 2));
+
+        /* Here len == 2 * (n + undefs + number_of_holes). */
         if (fval.isNull()) {
             /*
              * Sort using the default comparator converting all elements to
              * strings.
              */
             if (allStrings) {
-                elemsize = sizeof(Value);
+                if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorStrings(cx)))
+                    return false;
             } else {
                 /*
                  * To avoid string conversion on each compare we do it only once
                  * prior to sorting. But we also need the space for the original
-                 * values to recover the sorting result. To reuse
-                 * sort_compare_strings we move the original values to the odd
-                 * indexes in vec, put the string conversion results in the even
-                 * indexes and pass 2 * sizeof(Value) as an element size to the
-                 * sorting function. In this way sort_compare_strings will only
-                 * see the string values when it casts the compare arguments as
-                 * pointers to Value.
-                 *
-                 * This requires doubling the temporary storage including the
-                 * scratch space for the merge sort. Since vec already contains
-                 * the rooted scratch space for newlen elements at the tail, we
-                 * can use it to rearrange and convert to strings first and try
-                 * realloc only when we know that we successfully converted all
-                 * the elements.
+                 * values to recover the sorting result. For that we move the
+                 * original values to the odd indexes in vec, put the string
+                 * conversion results in the even indexes and do the merge sort
+                 * over resulting string-value pairs using an extra allocated
+                 * scratch space.
                  */
-#if JS_BITS_PER_WORD == 32
-                if (size_t(newlen) > size_t(-1) / (4 * sizeof(Value))) {
-                    js_ReportAllocationOverflow(cx);
-                    return false;
-                }
-#endif
-
-                /*
-                 * Rearrange and string-convert the elements of the vector from
-                 * the tail here and, after sorting, move the results back
-                 * starting from the start to prevent overwrite the existing
-                 * elements.
-                 */
-                i = newlen;
+                size_t i = n;
                 do {
                     --i;
                     if (!JS_CHECK_OPERATION_LIMIT(cx))
                         return false;
                     const Value &v = vec[i];
-                    str = js_ValueToString(cx, v);
+                    JSString *str = js_ValueToString(cx, v);
                     if (!str)
                         return false;
                     // Copying v must come first, because the following line overwrites v
                     // when i == 0.
                     vec[2 * i + 1] = v;
                     vec[2 * i].setString(str);
                 } while (i != 0);
 
-                JS_ASSERT(tvr.array == vec);
-                vec = (Value *) cx->realloc_(vec, 4 * size_t(newlen) * sizeof(Value));
-                if (!vec) {
-                    vec = tvr.array;  /* N.B. AutoFreeVector */
+                AutoValueVector extraScratch(cx);
+                if (!extraScratch.resize(n * 2))
+                    return false;
+                if (!MergeSort(reinterpret_cast<StringValuePair *>(vec.begin()), n,
+                               reinterpret_cast<StringValuePair *>(extraScratch.begin()),
+                               SortComparatorStringValuePairs(cx))) {
                     return false;
                 }
-                mergesort_tmp = vec + 2 * newlen;
-                MakeRangeGCSafe(mergesort_tmp, 2 * newlen);
-                tvr.changeArray(vec, newlen * 4);
-                elemsize = 2 * sizeof(Value);
-            }
-            if (!js_MergeSort(vec, size_t(newlen), elemsize,
-                              sort_compare_strings, cx, mergesort_tmp,
-                              JS_SORTING_GENERIC)) {
-                return false;
-            }
-            if (!allStrings) {
+
                 /*
-                 * We want to make the following loop fast and to unroot the
-                 * cached results of toString invocations before the operation
-                 * callback has a chance to run the GC. For this reason we do
-                 * not call JS_CHECK_OPERATION_LIMIT in the loop.
+                 * We want to unroot the cached results of toString calls
+                 * before the operation callback has a chance to run the GC.
+                 * So we do not call JS_CHECK_OPERATION_LIMIT in the loop.
                  */
                 i = 0;
                 do {
                     vec[i] = vec[2 * i + 1];
-                } while (++i != newlen);
+                } while (++i != n);
             }
         } else {
-            CompareArgs ca(cx, fval);
-            if (!js_MergeSort(vec, size_t(newlen), sizeof(Value),
-                              comparator_stack_cast(sort_compare),
-                              &ca, mergesort_tmp,
-                              JS_SORTING_VALUES)) {
+            InvokeArgsGuard args;
+            if (!MergeSort(vec.begin(), n, vec.begin() + n,
+                           SortComparatorFunction(cx, fval, args)))
+            {
                 return false;
             }
         }
 
         /*
          * We no longer need to root the scratch space for the merge sort, so
          * unroot it now to make the job of a potential GC under
          * InitArrayElements easier.
          */
-        tvr.changeLength(newlen);
-        if (!InitArrayElements(cx, obj, 0, newlen, vec, false))
+        vec.resize(n);
+        if (!InitArrayElements(cx, obj, 0, n, vec.begin(), false))
             return false;
     }
 
     /* Set undefs that sorted after the rest of elements. */
     while (undefs != 0) {
         --undefs;
-        if (!JS_CHECK_OPERATION_LIMIT(cx) ||
-            !SetArrayElement(cx, obj, newlen++, UndefinedValue())) {
+        if (!JS_CHECK_OPERATION_LIMIT(cx) || !SetArrayElement(cx, obj, n++, UndefinedValue()))
             return false;
-        }
     }
 
     /* Re-create any holes that sorted to the end of the array. */
-    while (len > newlen) {
+    while (len > n) {
         if (!JS_CHECK_OPERATION_LIMIT(cx) || DeleteArrayElement(cx, obj, --len, true) < 0)
             return false;
     }
     args.rval().setObject(*obj);
     return true;
 }
 
 /*
@@ -2581,17 +2393,17 @@ array_pop_dense(JSContext *cx, JSObject*
 {
     jsuint index = obj->getArrayLength();
     if (index == 0) {
         args.rval().setUndefined();
         return JS_TRUE;
     }
 
     index--;
-    
+
     JSBool hole;
     Value elt;
     if (!GetElement(cx, obj, index, &hole, &elt))
         return JS_FALSE;
 
     if (!hole && DeleteArrayElement(cx, obj, index, true) < 0)
         return JS_FALSE;
     if (cx->typeInferenceEnabled() && obj->getDenseArrayInitializedLength() > index)
@@ -3387,17 +3199,17 @@ array_readonlyCommon(JSContext *cx, Call
         /* Step d. */
         k++;
     }
 
     /* Step 8. */
     args.rval() = Behavior::lateExitValue();
     return true;
  }
- 
+
 /* ES5 15.4.4.16. */
 static JSBool
 array_every(JSContext *cx, uintN argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
     return array_readonlyCommon<ArrayEveryBehavior>(cx, args);
 }
 
@@ -3590,17 +3402,17 @@ class ArrayReduceBehavior
 
 class ArrayReduceRightBehavior
 {
   public:
     static void initialize(uint32 len, uint32 *start, uint32 *end, int32 *step)
     {
         *start = len - 1;
         *step = -1;
-        /* 
+        /*
          * We rely on (well defined) unsigned integer underflow to check our
          * end condition after visiting the full range (including 0).
          */
         *end = (uint32)-1;
     }
 };
 
 template<class Behavior>
--- a/js/src/jsarray.h
+++ b/js/src/jsarray.h
@@ -173,41 +173,16 @@ array_deleteElement(JSContext *cx, JSObj
  * This function assumes 'length' is effectively the result of calling
  * js_GetLengthProperty on aobj.
  */
 extern bool
 GetElements(JSContext *cx, JSObject *aobj, jsuint length, js::Value *vp);
 
 }
 
-/*
- * JS-specific merge sort function.
- */
-typedef JSBool (*JSComparator)(void *arg, const void *a, const void *b,
-                               int *result);
-
-enum JSMergeSortElemType {
-    JS_SORTING_VALUES,
-    JS_SORTING_GENERIC
-};
-
-/*
- * NB: vec is the array to be sorted, tmp is temporary space at least as big
- * as vec. Both should be GC-rooted if appropriate.
- *
- * isValue should true iff vec points to an array of js::Value
- *
- * The sorted result is in vec. vec may be in an inconsistent state if the
- * comparator function cmp returns an error inside a comparison, so remember
- * to check the return value of this function.
- */
-extern bool
-js_MergeSort(void *vec, size_t nel, size_t elsize, JSComparator cmp,
-             void *arg, void *tmp, JSMergeSortElemType elemType);
-
 /* Natives exposed for optimization by the interpreter and JITs. */
 namespace js {
 
 extern JSBool
 array_sort(JSContext *cx, uintN argc, js::Value *vp);
 
 extern JSBool
 array_push(JSContext *cx, uintN argc, js::Value *vp);
--- a/js/src/jsopcode.cpp
+++ b/js/src/jsopcode.cpp
@@ -64,16 +64,18 @@
 #include "jsiter.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsopcode.h"
 #include "jsscope.h"
 #include "jsscript.h"
 #include "jsstr.h"
 
+#include "ds/Sort.h"
+
 #include "frontend/BytecodeEmitter.h"
 #include "frontend/TokenStream.h"
 #include "vm/Debugger.h"
 
 #include "jscntxtinlines.h"
 #include "jsobjinlines.h"
 #include "jsopcodeinlines.h"
 #include "jsscriptinlines.h"
@@ -1334,36 +1336,29 @@ PopStr(SprintStack *ss, JSOp op)
 }
 
 static inline bool
 IsInitializerOp(unsigned char op)
 {
     return op == JSOP_NEWINIT || op == JSOP_NEWARRAY || op == JSOP_NEWOBJECT;
 }
 
-typedef struct TableEntry {
+struct TableEntry {
     jsval       key;
     ptrdiff_t   offset;
     JSAtom      *label;
     jsint       order;          /* source order for stable tableswitch sort */
-} TableEntry;
-
-static JSBool
-CompareOffsets(void *arg, const void *v1, const void *v2, int *result)
+};
+
+inline bool
+CompareTableEntries(const TableEntry &a, const TableEntry &b, bool *lessOrEqualp)
 {
-    ptrdiff_t offset_diff;
-    const TableEntry *te1 = (const TableEntry *) v1,
-                     *te2 = (const TableEntry *) v2;
-
-    offset_diff = te1->offset - te2->offset;
-    *result = (offset_diff == 0 ? te1->order - te2->order
-               : offset_diff < 0 ? -1
-               : 1);
-    return JS_TRUE;
-}
+    *lessOrEqualp = (a.offset != b.offset) ? a.offset <= b.offset : a.order <= b.order;
+    return true;
+};
 
 static ptrdiff_t
 SprintDoubleValue(Sprinter *sp, jsval v, JSOp *opp)
 {
     jsdouble d;
     ptrdiff_t todo;
     char *s;
 
@@ -4329,31 +4324,30 @@ Decompile(SprintStack *ss, jsbytecode *p
               {
                 ptrdiff_t jmplen, off, off2;
                 jsint j, n, low, high;
                 TableEntry *table, *tmp;
 
                 sn = js_GetSrcNote(jp->script, pc);
                 LOCAL_ASSERT(sn && SN_TYPE(sn) == SRC_SWITCH);
                 len = js_GetSrcNoteOffset(sn, 0);
-                jmplen = (op == JSOP_TABLESWITCH) ? JUMP_OFFSET_LEN
-                                                  : JUMPX_OFFSET_LEN;
+                jmplen = (op == JSOP_TABLESWITCH) ? JUMP_OFFSET_LEN : JUMPX_OFFSET_LEN;
                 pc2 = pc;
                 off = GetJumpOffset(pc, pc2);
                 pc2 += jmplen;
                 low = GET_JUMP_OFFSET(pc2);
                 pc2 += JUMP_OFFSET_LEN;
                 high = GET_JUMP_OFFSET(pc2);
                 pc2 += JUMP_OFFSET_LEN;
 
                 n = high - low + 1;
                 if (n == 0) {
                     table = NULL;
                     j = 0;
-                    ok = JS_TRUE;
+                    ok = true;
                 } else {
                     table = (TableEntry *)
                             cx->malloc_((size_t)n * sizeof *table);
                     if (!table)
                         return NULL;
                     for (i = j = 0; i < n; i++) {
                         table[j].label = NULL;
                         off2 = GetJumpOffset(pc, pc2);
@@ -4369,29 +4363,26 @@ Decompile(SprintStack *ss, jsbytecode *p
                             j++;
                         }
                         pc2 += jmplen;
                     }
                     tmp = (TableEntry *)
                           cx->malloc_((size_t)j * sizeof *table);
                     if (tmp) {
                         VOUCH_DOES_NOT_REQUIRE_STACK();
-                        ok = js_MergeSort(table, (size_t)j, sizeof(TableEntry),
-                                          CompareOffsets, NULL, tmp,
-                                          JS_SORTING_GENERIC);
-                        cx->free_(tmp);
+                        MergeSort(table, size_t(j), tmp, CompareTableEntries);
+                        Foreground::free_(tmp);
+                        ok = true;
                     } else {
-                        ok = JS_FALSE;
+                        ok = false;
                     }
                 }
 
-                if (ok) {
-                    ok = DecompileSwitch(ss, table, (uintN)j, pc, len, off,
-                                         JS_FALSE);
-                }
+                if (ok)
+                    ok = DecompileSwitch(ss, table, (uintN)j, pc, len, off, false);
                 cx->free_(table);
                 if (!ok)
                     return NULL;
                 todo = -2;
                 break;
               }
 
               case JSOP_LOOKUPSWITCH: