JavaScriptCore:

2009-02-13  Geoffrey Garen  <ggaren@apple.com>

        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  <ggaren@apple.com>

        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.

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

diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog
index 38a16b9..de00277 100644 (file)
--- a/JavaScriptCore/ChangeLog
+++ b/JavaScriptCore/ChangeLog
@@ -1,3 +1,52 @@
+2009-02-13  Geoffrey Garen  <ggaren@apple.com>
+
+        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.
+
 2009-02-13  Darin Adler  <darin@apple.com>
 
         * Configurations/JavaScriptCore.xcconfig: Undo accidental commit of this file.

diff --git a/JavaScriptCore/bytecode/CodeBlock.cpp b/JavaScriptCore/bytecode/CodeBlock.cpp
index 8810b58..be060d0 100644 (file)
--- a/JavaScriptCore/bytecode/CodeBlock.cpp
+++ b/JavaScriptCore/bytecode/CodeBlock.cpp
@@ -1231,6 +1231,7 @@ CodeBlock::CodeBlock(ScopeNode* ownerNode, CodeType codeType, PassRefPtr<SourceP
 #endif
     , m_needsFullScopeChain(ownerNode->needsActivation())
     , m_usesEval(ownerNode->usesEval())
+    , m_isNumericCompareFunction(false)
     , m_codeType(codeType)
     , m_source(sourceProvider)
     , m_sourceOffset(sourceOffset)

diff --git a/JavaScriptCore/bytecode/CodeBlock.h b/JavaScriptCore/bytecode/CodeBlock.h
index 8ebf73c..49d33c9 100644 (file)
--- a/JavaScriptCore/bytecode/CodeBlock.h
+++ b/JavaScriptCore/bytecode/CodeBlock.h
@@ -314,6 +314,9 @@ namespace JSC {
             reparseForExceptionInfoIfNecessary(callFrame);
             return binaryChop<CallReturnOffsetToBytecodeIndex, unsigned, getCallReturnOffset>(m_exceptionInfo->m_callReturnIndexVector.begin(), m_exceptionInfo->m_callReturnIndexVector.size(), m_jitCode.code.offsetOf(nativePC))->bytecodeIndex;
         }
+        
+        void setIsNumericCompareFunction(bool isNumericCompareFunction) { m_isNumericCompareFunction = isNumericCompareFunction; }
+        bool isNumericCompareFunction() { return m_isNumericCompareFunction; }
 
         bool functionRegisterForBytecodeOffset(unsigned bytecodeOffset, int& functionRegisterIndex);
 #endif
@@ -479,6 +482,7 @@ namespace JSC {
         bool m_needsFullScopeChain;
         bool m_usesEval;
         bool m_usesArguments;
+        bool m_isNumericCompareFunction;
 
         CodeType m_codeType;
 

diff --git a/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp b/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
index cba2901..c83cdc7 100644 (file)
--- a/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
+++ b/JavaScriptCore/bytecompiler/BytecodeGenerator.cpp
@@ -145,14 +145,14 @@ void BytecodeGenerator::generate()
 #ifndef NDEBUG
     m_codeBlock->setInstructionCount(m_codeBlock->instructions().size());
 
-    if (s_dumpsGeneratedCode) {
-        JSGlobalObject* globalObject = m_scopeChain->globalObject();
-        m_codeBlock->dump(globalObject->globalExec());
-    }
+    if (s_dumpsGeneratedCode)
+        m_codeBlock->dump(m_scopeChain->globalObject()->globalExec());
 #endif
 
     if ((m_codeType == FunctionCode && !m_codeBlock->needsFullScopeChain() && !m_codeBlock->usesArguments()) || m_codeType == EvalCode)
         symbolTable().clear();
+        
+    m_codeBlock->setIsNumericCompareFunction(instructions() == m_globalData->numericCompareFunction(m_scopeChain->globalObject()->globalExec()));
 
 #if !ENABLE(OPCODE_SAMPLING)
     if (!m_regeneratingForExceptionInfo && (m_codeType == FunctionCode || m_codeType == EvalCode))

diff --git a/JavaScriptCore/parser/Nodes.cpp b/JavaScriptCore/parser/Nodes.cpp
index 4768250..2aa516a 100644 (file)
--- a/JavaScriptCore/parser/Nodes.cpp
+++ b/JavaScriptCore/parser/Nodes.cpp
@@ -2648,11 +2648,15 @@ RegisterID* FunctionBodyNode::emitBytecode(BytecodeGenerator& generator, Registe
 {
     generator.emitDebugHook(DidEnterCallFrame, firstLine(), lastLine());
     statementListEmitCode(children(), generator, generator.ignoredResult());
-    if (!children().size() || !children().last()->isReturnNode()) {
-        RegisterID* r0 = generator.emitLoad(0, jsUndefined());
-        generator.emitDebugHook(WillLeaveCallFrame, firstLine(), lastLine());
-        generator.emitReturn(r0);
+    if (children().size() && children().last()->isBlock()) {
+        BlockNode* blockNode = static_cast<BlockNode*>(children().last().get());
+        if (blockNode->children().size() && blockNode->children().last()->isReturnNode())
+            return 0;
     }
+
+    RegisterID* r0 = generator.emitLoad(0, jsUndefined());
+    generator.emitDebugHook(WillLeaveCallFrame, firstLine(), lastLine());
+    generator.emitReturn(r0);
     return 0;
 }
 

diff --git a/JavaScriptCore/runtime/ArrayPrototype.cpp b/JavaScriptCore/runtime/ArrayPrototype.cpp
index 1413870..4cd229a 100644 (file)
--- a/JavaScriptCore/runtime/ArrayPrototype.cpp
+++ b/JavaScriptCore/runtime/ArrayPrototype.cpp
@@ -24,6 +24,7 @@
 #include "config.h"
 #include "ArrayPrototype.h"
 
+#include "CodeBlock.h"
 #include "Interpreter.h"
 #include "ObjectPrototype.h"
 #include "Lookup.h"
@@ -62,6 +63,14 @@ static JSValuePtr arrayProtoFuncLastIndexOf(ExecState*, JSObject*, JSValuePtr, c
 
 namespace JSC {
 
+static inline bool isNumericCompareFunction(CallType callType, const CallData& callData)
+{
+    if (callType != CallTypeJS)
+        return false;
+    
+    return callData.js.functionBody->bytecode(callData.js.scopeChain).isNumericCompareFunction();
+}
+
 // ------------------------------ ArrayPrototype ----------------------------
 
 const ClassInfo ArrayPrototype::info = {"Array", &JSArray::info, 0, ExecState::arrayTable};
@@ -426,7 +435,9 @@ JSValuePtr arrayProtoFuncSort(ExecState* exec, JSObject*, JSValuePtr thisValue,
     CallType callType = function.getCallData(callData);
 
     if (thisObj->classInfo() == &JSArray::info) {
-        if (callType != CallTypeNone)
+        if (isNumericCompareFunction(callType, callData))
+            asArray(thisObj)->sortNumeric(exec, function, callType, callData);
+        else if (callType != CallTypeNone)
             asArray(thisObj)->sort(exec, function, callType, callData);
         else
             asArray(thisObj)->sort(exec);

diff --git a/JavaScriptCore/runtime/FunctionConstructor.cpp b/JavaScriptCore/runtime/FunctionConstructor.cpp
index 4973bc1..d58334a 100644 (file)
--- a/JavaScriptCore/runtime/FunctionConstructor.cpp
+++ b/JavaScriptCore/runtime/FunctionConstructor.cpp
@@ -66,7 +66,7 @@ CallType FunctionConstructor::getCallData(CallData& callData)
     return CallTypeHost;
 }
 
-static FunctionBodyNode* functionBody(ProgramNode* program)
+FunctionBodyNode* extractFunctionBody(ProgramNode* program)
 {
     if (!program)
         return 0;
@@ -110,7 +110,7 @@ JSObject* constructFunction(ExecState* exec, const ArgList& args, const Identifi
     SourceCode source = makeSource(program, sourceURL, lineNumber);
     RefPtr<ProgramNode> programNode = exec->globalData().parser->parse<ProgramNode>(exec, exec->dynamicGlobalObject()->debugger(), source, &errLine, &errMsg);
 
-    FunctionBodyNode* body = functionBody(programNode.get());
+    FunctionBodyNode* body = extractFunctionBody(programNode.get());
     if (!body)
         return throwError(exec, SyntaxError, errMsg, errLine, source.provider()->asID(), source.provider()->url());
 

diff --git a/JavaScriptCore/runtime/FunctionConstructor.h b/JavaScriptCore/runtime/FunctionConstructor.h
index e8486dc..124b354 100644 (file)
--- a/JavaScriptCore/runtime/FunctionConstructor.h
+++ b/JavaScriptCore/runtime/FunctionConstructor.h
@@ -26,6 +26,8 @@
 namespace JSC {
 
     class FunctionPrototype;
+    class ProgramNode;
+    class FunctionBodyNode;
 
     class FunctionConstructor : public InternalFunction {
     public:
@@ -39,6 +41,8 @@ namespace JSC {
     JSObject* constructFunction(ExecState*, const ArgList&, const Identifier& functionName, const UString& sourceURL, int lineNumber);
     JSObject* constructFunction(ExecState*, const ArgList&);
 
+    FunctionBodyNode* extractFunctionBody(ProgramNode*);
+
 } // namespace JSC
 
 #endif // FunctionConstructor_h

diff --git a/JavaScriptCore/runtime/JSArray.cpp b/JavaScriptCore/runtime/JSArray.cpp
index 941fc9a..89a2b45 100644 (file)
--- a/JavaScriptCore/runtime/JSArray.cpp
+++ b/JavaScriptCore/runtime/JSArray.cpp
@@ -617,15 +617,53 @@ void JSArray::mark()
     }
 }
 
-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);
+}
+
 void JSArray::sort(ExecState* exec)
 {
     unsigned lengthNotIncludingUndefined = compactForSorting();
@@ -642,7 +680,7 @@ void JSArray::sort(ExecState* exec)
     // buffer. Besides, this protects us from crashing if some objects have custom toString methods that return
     // random or otherwise changing results, effectively making compare function inconsistent.
 
-    Vector<ArrayQSortPair> values(lengthNotIncludingUndefined);
+    Vector<ValueStringPair> values(lengthNotIncludingUndefined);
     if (!values.begin()) {
         throwOutOfMemoryError(exec);
         return;
@@ -670,11 +708,11 @@ void JSArray::sort(ExecState* exec)
     // than O(N log N).
 
 #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
 
     // FIXME: If the toString function changed the length of the array, this might be

diff --git a/JavaScriptCore/runtime/JSArray.h b/JavaScriptCore/runtime/JSArray.h
index e280022..7eecf33 100644 (file)
--- a/JavaScriptCore/runtime/JSArray.h
+++ b/JavaScriptCore/runtime/JSArray.h
@@ -56,6 +56,7 @@ namespace JSC {
 
         void sort(ExecState*);
         void sort(ExecState*, JSValuePtr compareFunction, CallType, const CallData&);
+        void sortNumeric(ExecState*, JSValuePtr compareFunction, CallType, const CallData&);
 
         void push(ExecState*, JSValuePtr);
         JSValuePtr pop();

diff --git a/JavaScriptCore/runtime/JSGlobalData.cpp b/JavaScriptCore/runtime/JSGlobalData.cpp
index 358ce8f..10b584d 100644 (file)
--- a/JavaScriptCore/runtime/JSGlobalData.cpp
+++ b/JavaScriptCore/runtime/JSGlobalData.cpp
@@ -32,6 +32,7 @@
 #include "ArgList.h"
 #include "Collector.h"
 #include "CommonIdentifiers.h"
+#include "FunctionConstructor.h"
 #include "Interpreter.h"
 #include "JSActivation.h"
 #include "JSClassRef.h"
@@ -64,7 +65,8 @@ extern const HashTable regExpConstructorTable;
 extern const HashTable stringTable;
 
 JSGlobalData::JSGlobalData(bool isShared)
-    : interpreter(new Interpreter)
+    : initializingLazyNumericCompareFunction(false)
+    , interpreter(new Interpreter)
     , exception(noValue())
     , arrayTable(new HashTable(JSC::arrayTable))
     , dateTable(new HashTable(JSC::dateTable))
@@ -184,8 +186,22 @@ JSGlobalData*& JSGlobalData::sharedInstanceInternal()
     return sharedInstance;
 }
 
-JSGlobalData::ClientData::~ClientData()
+// FIXME: We can also detect forms like v1 < v2 ? -1 : 0, reverse comparison, etc.
+const Vector<Instruction>& JSGlobalData::numericCompareFunction(ExecState* exec)
 {
+    if (!lazyNumericCompareFunction.size() && !initializingLazyNumericCompareFunction) {
+        initializingLazyNumericCompareFunction = true;
+        RefPtr<ProgramNode> programNode = parser->parse<ProgramNode>(exec, 0, makeSource(UString("(function (v1, v2) { return v1 - v2; })")), 0, 0);
+        RefPtr<FunctionBodyNode> functionBody = extractFunctionBody(programNode.get());
+        lazyNumericCompareFunction = functionBody->bytecode(exec->scopeChain()).instructions();
+        initializingLazyNumericCompareFunction = false;
+    }
+
+    return lazyNumericCompareFunction;
 }
 
+JSGlobalData::ClientData::~ClientData()
+{
 }
+
+} // namespace JSC

diff --git a/JavaScriptCore/runtime/JSGlobalData.h b/JavaScriptCore/runtime/JSGlobalData.h
index 32e3ff1..4223191 100644 (file)
--- a/JavaScriptCore/runtime/JSGlobalData.h
+++ b/JavaScriptCore/runtime/JSGlobalData.h
@@ -46,6 +46,7 @@ namespace JSC {
     class CommonIdentifiers;
     class Heap;
     class IdentifierTable;
+    class Instruction;
     class Interpreter;
     class JSGlobalObject;
     class JSObject;
@@ -71,6 +72,10 @@ namespace JSC {
         void makeUsableFromMultipleThreads() { heap.makeUsableFromMultipleThreads(); }
 #endif
 
+        const Vector<Instruction>& numericCompareFunction(ExecState*);
+        Vector<Instruction> lazyNumericCompareFunction;
+        bool initializingLazyNumericCompareFunction;
+
         Interpreter* interpreter;
 
         JSValuePtr exception;

diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog
index 6219610..faf0668 100644 (file)
--- a/LayoutTests/ChangeLog
+++ b/LayoutTests/ChangeLog
@@ -1,3 +1,13 @@
+2009-02-13  Geoffrey Garen  <ggaren@apple.com>
+
+        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.
+
 2009-02-13  Chris Marrin  <cmarrin@apple.com>
 
         Reviewed by Adam Roben.

diff --git a/LayoutTests/fast/js/resources/sort-non-numbers.js b/LayoutTests/fast/js/resources/sort-non-numbers.js
new file mode 100644 (file)
index 0000000..21cb5b9
--- /dev/null
+++ b/LayoutTests/fast/js/resources/sort-non-numbers.js
@@ -0,0 +1,10 @@
+description("This tests numerically sorting an array of non-numbers.");
+
+var test = [ "2", "1", "3" ];
+test.sort(function (v1, v2) {
+    return v1 - v2;
+});
+
+shouldBe("String(test)", "'1,2,3'");
+
+var successfullyParsed = true;

diff --git a/LayoutTests/fast/js/sort-non-numbers-expected.txt b/LayoutTests/fast/js/sort-non-numbers-expected.txt
new file mode 100644 (file)
index 0000000..7e63c5b
--- /dev/null
+++ b/LayoutTests/fast/js/sort-non-numbers-expected.txt
@@ -0,0 +1,10 @@
+This tests numerically sorting an array of non-numbers.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+PASS String(test) is '1,2,3'
+PASS successfullyParsed is true
+
+TEST COMPLETE
+

diff --git a/LayoutTests/fast/js/sort-non-numbers.html b/LayoutTests/fast/js/sort-non-numbers.html
new file mode 100644 (file)
index 0000000..340e50a
--- /dev/null
+++ b/LayoutTests/fast/js/sort-non-numbers.html
@@ -0,0 +1,13 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<link rel="stylesheet" href="resources/js-test-style.css">
+<script src="resources/js-test-pre.js"></script>
+</head>
+<body>
+<p id="description"></p>
+<div id="console"></div>
+<script src="resources/sort-non-numbers.js"></script>
+<script src="resources/js-test-post.js"></script>
+</body>
+</html>