Changeset 40993 in webkit for trunk/JavaScriptCore/runtime/JSArray.cpp

Timestamp:

Feb 13, 2009, 3:28:04 PM (16 years ago)

Author:

[email protected]

Message:

JavaScriptCore:

2009-02-13 Geoffrey Garen <​[email protected]>

Reviewed by Darin Adler.

Fixed <rdar://problem/6584057> Optimize sort by JS numeric comparison
function not to run the comparison function

• bytecode/CodeBlock.cpp: (JSC::CodeBlock::CodeBlock):
• bytecode/CodeBlock.h: (JSC::CodeBlock::setIsNumericCompareFunction): (JSC::CodeBlock::isNumericCompareFunction): Added the ability to track whether a CodeBlock performs a sort-like numeric comparison.

• bytecompiler/BytecodeGenerator.cpp: (JSC::BytecodeGenerator::generate): Set the isNumericCompareFunction bit after compiling.

• parser/Nodes.cpp: (JSC::FunctionBodyNode::emitBytecode): Fixed a bug that caused us to codegen an extra return at the end of all functions (eek!), since this made it harder / weirder to detect the numeric comparison pattern in bytecode.

• runtime/ArrayPrototype.cpp: (JSC::arrayProtoFuncSort): Use the isNumericCompareFunction bit to do a faster sort if we can.

• runtime/FunctionConstructor.cpp: (JSC::extractFunctionBody): (JSC::constructFunction):
• runtime/FunctionConstructor.h: Renamed and exported extractFunctionBody for use in initializing lazyNumericCompareFunction.

• runtime/JSArray.cpp: (JSC::compareNumbersForQSort): (JSC::compareByStringPairForQSort): (JSC::JSArray::sortNumeric): (JSC::JSArray::sort):
• runtime/JSArray.h: Added a fast numeric sort. Renamed ArrayQSortPair to be more specific since we do different kinds of qsort now.

• runtime/JSGlobalData.cpp: (JSC::JSGlobalData::JSGlobalData): (JSC::JSGlobalData::numericCompareFunction): (JSC::JSGlobalData::ClientData::~ClientData):
• runtime/JSGlobalData.h: Added helper data for computing the isNumericCompareFunction bit.

LayoutTests:

2009-02-13 Geoffrey Garen <​[email protected]>

Reviewed by Sam Weinig.

Added a test for an edge case in <rdar://problem/6584057>.

• fast/js/resources/sort-non-numbers.js: Added.
• fast/js/sort-non-numbers.html: Added.
• fast/js/sort-non-numbers-expected.txt: Added.

File:

• trunk/JavaScriptCore/runtime/JSArray.cpp (modified) (3 diffs)

trunk/JavaScriptCore/runtime/JSArray.cpp

@@ -618 +618 @@
 }
 
-typedef std::pair<JSValuePtr, UString> ArrayQSortPair;
+static int compareNumbersForQSort(const void* a, const void* b)
+{
+    double da = static_cast<const JSValuePtr*>(a)->uncheckedGetNumber();
+    double db = static_cast<const JSValuePtr*>(b)->uncheckedGetNumber();
+    return (da > db) - (da < db);
+}
+
+typedef std::pair<JSValuePtr, UString> ValueStringPair;
 
 static int compareByStringPairForQSort(const void* a, const void* b)
 {
-    const ArrayQSortPair* va = static_cast<const ArrayQSortPair*>(a);
-    const ArrayQSortPair* vb = static_cast<const ArrayQSortPair*>(b);
+    const ValueStringPair* va = static_cast<const ValueStringPair*>(a);
+    const ValueStringPair* vb = static_cast<const ValueStringPair*>(b);
     return compare(va->second, vb->second);
+}
+
+void JSArray::sortNumeric(ExecState* exec, JSValuePtr compareFunction, CallType callType, const CallData& callData)
+{
+    unsigned lengthNotIncludingUndefined = compactForSorting();
+    if (m_storage->m_sparseValueMap) {
+        throwOutOfMemoryError(exec);
+        return;
+    }
+
+    if (!lengthNotIncludingUndefined)
+        return;
+        
+    bool allValuesAreNumbers = true;
+    size_t size = m_storage->m_numValuesInVector;
+    for (size_t i = 0; i < size; ++i) {
+        if (!m_storage->m_vector[i].isNumber()) {
+            allValuesAreNumbers = false;
+            break;
+        }
+    }
+
+    if (!allValuesAreNumbers)
+        return sort(exec, compareFunction, callType, callData);
+
+    // For numeric comparison, which is fast, qsort is faster than mergesort. We
+    // also don't require mergesort's stability, since there's no user visible
+    // side-effect from swapping the order of equal primitive values.
+    qsort(m_storage->m_vector, size, sizeof(JSValuePtr), compareNumbersForQSort);
+
+    checkConsistency(SortConsistencyCheck);
 }
 
@@ -643 +681 @@
     // random or otherwise changing results, effectively making compare function inconsistent.
 
-    Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
+    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
     if (!values.begin()) {
         throwOutOfMemoryError(exec);
@@ -671 +709 @@
 
 #if HAVE(MERGESORT)
-    mergesort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
+    mergesort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #else
     // FIXME: The qsort library function is likely to not be a stable sort.
     // ECMAScript-262 does not specify a stable sort, but in practice, browsers perform a stable sort.
-    qsort(values.begin(), values.size(), sizeof(ArrayQSortPair), compareByStringPairForQSort);
+    qsort(values.begin(), values.size(), sizeof(ValueStringPair), compareByStringPairForQSort);
 #endif