Changeset 20974 in webkit for trunk/JavaScriptCore/kjs/array_object.cpp

Timestamp:

Apr 20, 2007, 3:20:15 PM (18 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:

File:

• trunk/JavaScriptCore/kjs/array_object.cpp (modified) (2 diffs)

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;