Reviewed by Darin.
authormjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Apr 2007 22:20:15 +0000 (22:20 +0000)
committermjs <mjs@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Fri, 20 Apr 2007 22:20:15 +0000 (22:20 +0000)
        - <rdar://problem/5149915> use mergesort when possible, since it leads to fewer compares (2% JS iBench speedup)

        * kjs/array_object.cpp:
        (ArrayInstance::sort): Use mergesort(3) on platforms that have it, since it tends
        to do fewer compares than qsort; but avoid it very on large arrays since it uses extra
        memory. Also added comments identifying possibly even better sorting algorithms
        for sort by string value and sort by compare function.
        * kjs/config.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@20974 268f45cc-cd09-0410-ab3c-d52691b4dbfc

JavaScriptCore/ChangeLog
JavaScriptCore/kjs/array_object.cpp
JavaScriptCore/kjs/config.h

index 96ed18fc3b3631d0c69343b95242cffc050a00b7..eda2f4709a983d8800e47cbc6c3e3072ee8827a0 100644 (file)
@@ -1,3 +1,16 @@
+2007-04-20  Maciej Stachowiak  <mjs@apple.com>
+
+        Reviewed by Darin.
+        
+        - <rdar://problem/5149915> use mergesort when possible, since it leads to fewer compares (2% JS iBench speedup)
+
+        * kjs/array_object.cpp:
+        (ArrayInstance::sort): Use mergesort(3) on platforms that have it, since it tends
+        to do fewer compares than qsort; but avoid it very on large arrays since it uses extra
+        memory. Also added comments identifying possibly even better sorting algorithms
+        for sort by string value and sort by compare function.
+        * kjs/config.h:
+
 2007-04-20  Maciej Stachowiak  <mjs@apple.com>
 
         Reviewed by Darin.
index 2d32547a344487480f1e77ec3624d24e391c7a83..2bb7faf3f6bb7bfca90326fc563291791e9c878e 100644 (file)
@@ -302,10 +302,28 @@ static int compareByStringForQSort(const void *a, const void *b)
 
 void ArrayInstance::sort(ExecState* exec)
 {
-    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
-
+    size_t lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
+      
     ExecState* oldExec = execForCompareByStringForQSort;
     execForCompareByStringForQSort = exec;
+#if HAVE(MERGESORT)
+    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
+    // however, becuase it requires extra copies of the storage buffer, don't use it for very
+    // large arrays
+    // FIXME: for sorting by string value, the fastest thing would actually be to convert all the
+    // values to string once up front, and then use a radix sort. That would be O(N) rather than 
+    // O(N log N).
+    if (lengthNotIncludingUndefined < sparseArrayCutoff) {
+        JSValue** storageCopy = static_cast<JSValue**>(fastMalloc(capacity * sizeof(JSValue*)));
+        memcpy(storageCopy, storage, capacity * sizeof(JSValue*));
+        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareByStringForQSort);
+        storage = storageCopy;
+        fastFree(storage);
+        execForCompareByStringForQSort = oldExec;
+        return;
+    }
+#endif
+
     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
     execForCompareByStringForQSort = oldExec;
 }
@@ -351,11 +369,26 @@ static int compareWithCompareFunctionForQSort(const void *a, const void *b)
 
 void ArrayInstance::sort(ExecState* exec, JSObject* compareFunction)
 {
-    int lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
+    size_t lengthNotIncludingUndefined = pushUndefinedObjectsToEnd(exec);
 
     CompareWithCompareFunctionArguments* oldArgs = compareWithCompareFunctionArguments;
     CompareWithCompareFunctionArguments args(exec, compareFunction);
     compareWithCompareFunctionArguments = &args;
+#if HAVE(MERGESORT)
+    // mergesort usually does fewer compares, so it is actually faster than qsort for JS sorts.
+    // however, becuase it requires extra copies of the storage buffer, don't use it for very
+    // large arrays
+    // FIXME: a tree sort using a perfectly balanced tree (e.g. an AVL tree) could do an even
+    // better job of minimizing compares
+    if (lengthNotIncludingUndefined < sparseArrayCutoff) {
+        JSValue** storageCopy = static_cast<JSValue**>(fastMalloc(capacity * sizeof(JSValue*)));
+        memcpy(storageCopy, storage, capacity * sizeof(JSValue*));
+        mergesort(storageCopy, lengthNotIncludingUndefined, sizeof(JSValue *), compareWithCompareFunctionForQSort);
+        storage = storageCopy;
+        compareWithCompareFunctionArguments = oldArgs;
+        return;
+    }
+#endif
     qsort(storage, lengthNotIncludingUndefined, sizeof(JSValue*), compareWithCompareFunctionForQSort);
     compareWithCompareFunctionArguments = oldArgs;
 }
index 3e007fdc4fcfec5c87bfe04bcff89abbc5c395dc..661b87adca4288abbf4ee5db31b479333db02242 100644 (file)
@@ -31,6 +31,7 @@
 #define HAVE_FUNC_ISINF 1
 #define HAVE_FUNC_ISNAN 1
 #define HAVE_MMAP 1
+#define HAVE_MERGESORT 1
 #define HAVE_SBRK 1
 #define HAVE_STRINGS_H 1
 #define HAVE_SYS_PARAM_H 1