Changeset 20974 in webkit

Timestamp:

Apr 20, 2007 3:20:15 PM (17 years ago)

Author:

mjs

Message:

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:

Location:

trunk/JavaScriptCore

Files:

• ChangeLog (modified) (1 diff)
• kjs/array_object.cpp (modified) (2 diffs)
• kjs/config.h (modified) (1 diff)

trunk/JavaScriptCore/ChangeLog

@@ +1 @@
+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>
 

trunk/JavaScriptCore/kjs/array_object.cpp

@@ -303 +303 @@
 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;
@@ -352 +370 @@
 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;

trunk/JavaScriptCore/kjs/config.h

@@ -32 +32 @@
 #define HAVE_FUNC_ISNAN 1
 #define HAVE_MMAP 1
+#define HAVE_MERGESORT 1
 #define HAVE_SBRK 1
 #define HAVE_STRINGS_H 1