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:

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

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index 96ed18f..eda2f47 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -2,6 +2,19 @@
 
         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.
+        
         - bump optimization flags up to -O3 for 1% JS iBench speed improvement 
 
         * Configurations/Base.xcconfig:

diff --git a/JavaScriptCore/kjs/array_object.cpp b/JavaScriptCore/kjs/array_object.cpp
index 2d32547..2bb7faf 100644 (file)
--- a/JavaScriptCore/kjs/array_object.cpp
+++ b/JavaScriptCore/kjs/array_object.cpp
@@ -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;
 }

diff --git a/JavaScriptCore/kjs/config.h b/JavaScriptCore/kjs/config.h
index 3e007fd..661b87a 100644 (file)
--- a/JavaScriptCore/kjs/config.h
+++ b/JavaScriptCore/kjs/config.h
@@ -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