Changeset 28782 in webkit for trunk/JavaScriptCore/kjs

Timestamp:

Dec 16, 2007, 5:14:36 PM (17 years ago)

Author:

[email protected]

Message:

Fix ​http://bugs.webkit.org/show_bug.cgi?id=16448 ([GTK] Celtic Kane JavaScript performance on Array test is slow relative to Mac).

Reviewed by Maciej Stachowiak.

• kjs/array_instance.cpp:

(KJS::compareByStringPairForQSort):
(KJS::ArrayInstance::sort): Convert JSValue's to strings once up front and then sort the
results. This avoids calling toString twice per comparison, but requires a temporary buffer
so we only use this approach in cases where the array being sorted is not too large.

File:

• trunk/JavaScriptCore/kjs/array_instance.cpp (modified) (4 diffs)

trunk/JavaScriptCore/kjs/array_instance.cpp

@@ -50 +50 @@
 static const unsigned minDensityMultiplier = 8;
 
-static const unsigned mergeSortCutoff = 10000;
+static const unsigned copyingSortCutoff = 50000;
 
 const ClassInfo ArrayInstance::info = {"Array", 0, 0};
@@ -430 +430 @@
 }
 
+static int compareByStringPairForQSort(const void* a, const void* b)
+{
+    const std::pair<JSValue*, UString>* va = static_cast<const std::pair<JSValue*, UString>*>(a);
+    const std::pair<JSValue*, UString>* vb = static_cast<const std::pair<JSValue*, UString>*>(b);
+    return compare(va->second, vb->second);
+}
+
 static ExecState* execForCompareByStringForQSort = 0;
-
 static int compareByStringForQSort(const void* a, const void* b)
 {
@@ -448 +454 @@
     unsigned lengthNotIncludingUndefined = compactForSorting();
 
+    if (lengthNotIncludingUndefined < copyingSortCutoff) {
+        // Converting JavaScript values to strings can be expensive, so we do it once up front and sort based on that.
+        // This is a considerable improvement over doing it twice per comparison, though it requires a large temporary
+        // buffer.  For large arrays, we fall back to a qsort on the JavaScriptValues to avoid creating copies.
+
+        Vector<std::pair<JSValue*, UString> > values(lengthNotIncludingUndefined);
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++) {
+            JSValue* value = m_storage->m_vector[i];
+            ASSERT(!value->isUndefined());
+            values[i].first = value;
+            values[i].second = value->toString(exec);
+        }
+
+        // FIXME: Since we sort by string value, a fast algorithm might be to use a radix sort. That would be O(N) rather
+        // than O(N log N).
+
+#if HAVE(MERGESORT)
+        mergesort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
+#else
+        qsort(values.begin(), values.size(), sizeof(std::pair<JSValue*, UString>), compareByStringPairForQSort);
+#endif
+        for (size_t i = 0; i < lengthNotIncludingUndefined; i++)
+            m_storage->m_vector[i] = values[i].first;
+        return;
+    }
+
     ExecState* oldExec = execForCompareByStringForQSort;
     execForCompareByStringForQSort = exec;
-
-#if HAVE(MERGESORT)
-    // Because mergesort usually does fewer compares, it is faster than qsort here.
-    // However, because it requires extra copies of the storage buffer, don't use it for very
-    // large arrays.
-
-    // FIXME: Since we sort by string value, a fast algorithm might 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 < mergeSortCutoff) {
-        // During the sort, we could do a garbage collect, and it's important to still
-        // have references to every object in the array for ArrayInstance::mark.
-        // The mergesort algorithm does not guarantee this, so we sort a copy rather
-        // than the original.
-        size_t size = storageSize(m_vectorLength);
-        ArrayStorage* copy = static_cast<ArrayStorage*>(fastMalloc(size));
-        memcpy(copy, m_storage, size);
-        mergesort(copy->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
-        fastFree(m_storage);
-        m_storage = copy;
-        execForCompareByStringForQSort = oldExec;
-        return;
-    }
-#endif
-
     qsort(m_storage->m_vector, lengthNotIncludingUndefined, sizeof(JSValue*), compareByStringForQSort);
     execForCompareByStringForQSort = oldExec;
@@ -529 +535 @@
     // better job of minimizing compares.
 
-    if (lengthNotIncludingUndefined < mergeSortCutoff) {
+    if (lengthNotIncludingUndefined < copyingSortCutoff) {
         // During the sort, we could do a garbage collect, and it's important to still
         // have references to every object in the array for ArrayInstance::mark.