From 7803989f505fead6deb0339b97e064af55c0b323 Mon Sep 17 00:00:00 2001 From: "ggaren@apple.com" Date: Fri, 13 Feb 2009 23:28:04 +0000 Subject: [PATCH] JavaScriptCore: 2009-02-13 Geoffrey Garen Reviewed by Darin Adler. Fixed 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 Reviewed by Sam Weinig. Added a test for an edge case in . * 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 --- JavaScriptCore/ChangeLog | 49 ++++++++++++++++++++++ JavaScriptCore/bytecode/CodeBlock.cpp | 1 + JavaScriptCore/bytecode/CodeBlock.h | 4 ++ JavaScriptCore/bytecompiler/BytecodeGenerator.cpp | 8 ++-- JavaScriptCore/parser/Nodes.cpp | 12 ++++-- JavaScriptCore/runtime/ArrayPrototype.cpp | 13 +++++- JavaScriptCore/runtime/FunctionConstructor.cpp | 4 +- JavaScriptCore/runtime/FunctionConstructor.h | 4 ++ JavaScriptCore/runtime/JSArray.cpp | 50 ++++++++++++++++++++--- JavaScriptCore/runtime/JSArray.h | 1 + JavaScriptCore/runtime/JSGlobalData.cpp | 20 ++++++++- JavaScriptCore/runtime/JSGlobalData.h | 5 +++ LayoutTests/ChangeLog | 10 +++++ LayoutTests/fast/js/resources/sort-non-numbers.js | 10 +++++ LayoutTests/fast/js/sort-non-numbers-expected.txt | 10 +++++ LayoutTests/fast/js/sort-non-numbers.html | 13 ++++++ 16 files changed, 195 insertions(+), 19 deletions(-) create mode 100644 LayoutTests/fast/js/resources/sort-non-numbers.js create mode 100644 LayoutTests/fast/js/sort-non-numbers-expected.txt create mode 100644 LayoutTests/fast/js/sort-non-numbers.html diff --git a/JavaScriptCore/ChangeLog b/JavaScriptCore/ChangeLog index 38a16b9..de00277 100644 --- a/JavaScriptCore/ChangeLog +++ b/JavaScriptCore/ChangeLog @@ -1,3 +1,52 @@ +2009-02-13 Geoffrey Garen + + Reviewed by Darin Adler. + + Fixed 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 * 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 --- a/JavaScriptCore/bytecode/CodeBlock.cpp +++ b/JavaScriptCore/bytecode/CodeBlock.cpp @@ -1231,6 +1231,7 @@ CodeBlock::CodeBlock(ScopeNode* ownerNode, CodeType codeType, PassRefPtrneedsActivation()) , 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 --- a/JavaScriptCore/bytecode/CodeBlock.h +++ b/JavaScriptCore/bytecode/CodeBlock.h @@ -314,6 +314,9 @@ namespace JSC { reparseForExceptionInfoIfNecessary(callFrame); return binaryChop(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 --- 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 --- 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(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 --- 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 --- 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 = exec->globalData().parser->parse(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 --- 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 --- a/JavaScriptCore/runtime/JSArray.cpp +++ b/JavaScriptCore/runtime/JSArray.cpp @@ -617,15 +617,53 @@ void JSArray::mark() } } -typedef std::pair ArrayQSortPair; +static int compareNumbersForQSort(const void* a, const void* b) +{ + double da = static_cast(a)->uncheckedGetNumber(); + double db = static_cast(b)->uncheckedGetNumber(); + return (da > db) - (da < db); +} + +typedef std::pair ValueStringPair; static int compareByStringPairForQSort(const void* a, const void* b) { - const ArrayQSortPair* va = static_cast(a); - const ArrayQSortPair* vb = static_cast(b); + const ValueStringPair* va = static_cast(a); + const ValueStringPair* vb = static_cast(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 values(lengthNotIncludingUndefined); + Vector 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 --- 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 --- 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& JSGlobalData::numericCompareFunction(ExecState* exec) { + if (!lazyNumericCompareFunction.size() && !initializingLazyNumericCompareFunction) { + initializingLazyNumericCompareFunction = true; + RefPtr programNode = parser->parse(exec, 0, makeSource(UString("(function (v1, v2) { return v1 - v2; })")), 0, 0); + RefPtr 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 --- 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& numericCompareFunction(ExecState*); + Vector lazyNumericCompareFunction; + bool initializingLazyNumericCompareFunction; + Interpreter* interpreter; JSValuePtr exception; diff --git a/LayoutTests/ChangeLog b/LayoutTests/ChangeLog index 6219610..faf0668 100644 --- a/LayoutTests/ChangeLog +++ b/LayoutTests/ChangeLog @@ -1,3 +1,13 @@ +2009-02-13 Geoffrey Garen + + Reviewed by Sam Weinig. + + Added a test for an edge case in . + + * 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 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 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 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 index 0000000..340e50a --- /dev/null +++ b/LayoutTests/fast/js/sort-non-numbers.html @@ -0,0 +1,13 @@ + + + + + + + +

+
+ + + + -- 1.8.3.1