Log Message
Array.prototype.sort should at least try to be PTIME even when the array is in some bizarre mode https://bugs.webkit.org/show_bug.cgi?id=112187 <rdar://problem/13393550>
Source/_javascript_Core:
Reviewed by Michael Saboff and Gavin Barraclough.
If we have an array-like object in crazy mode passed into Array.prototype.sort, and its length is large,
then first copy all elements into a separate, compact, un-holy array and sort that. Then copy back.
This means that sorting will be at works O(n^2) in the actual number of things in the array, rather than
O(n^2) in the array's length.
* runtime/ArrayPrototype.cpp:
(JSC::attemptFastSort):
(JSC::performSlowSort):
(JSC):
(JSC::arrayProtoFuncSort):
LayoutTests:
Reviewed by Michael Saboff and Gavin Barraclough.
If your Array.prototype.sort is not sufficiently smart, this test will never complete.
But if it is, it'll complete instantly.
* fast/js/array-sort-small-sparse-array-with-large-length-expected.txt: Added.
* fast/js/array-sort-small-sparse-array-with-large-length.html: Added.
* fast/js/jsc-test-list:
* fast/js/script-tests/array-sort-small-sparse-array-with-large-length.js: Added.
Modified Paths
- trunk/LayoutTests/ChangeLog
- trunk/LayoutTests/fast/js/jsc-test-list
- trunk/Source/_javascript_Core/ChangeLog
- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp
Added Paths
Diff
Modified: trunk/LayoutTests/ChangeLog (145627 => 145628)
--- trunk/LayoutTests/ChangeLog 2013-03-13 00:16:24 UTC (rev 145627)
+++ trunk/LayoutTests/ChangeLog 2013-03-13 00:17:38 UTC (rev 145628)
@@ -1,3 +1,19 @@
+2013-03-12 Filip Pizlo <[email protected]>
+
+ Array.prototype.sort should at least try to be PTIME even when the array is in some bizarre mode
+ https://bugs.webkit.org/show_bug.cgi?id=112187
+ <rdar://problem/13393550>
+
+ Reviewed by Michael Saboff and Gavin Barraclough.
+
+ If your Array.prototype.sort is not sufficiently smart, this test will never complete.
+ But if it is, it'll complete instantly.
+
+ * fast/js/array-sort-small-sparse-array-with-large-length-expected.txt: Added.
+ * fast/js/array-sort-small-sparse-array-with-large-length.html: Added.
+ * fast/js/jsc-test-list:
+ * fast/js/script-tests/array-sort-small-sparse-array-with-large-length.js: Added.
+
2013-03-12 James Robinson <[email protected]>
Update chromium pixel baselines for mesa blend fix in chromium r187688
Added: trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length-expected.txt (0 => 145628)
--- trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length-expected.txt (rev 0)
+++ trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length-expected.txt 2013-03-13 00:17:38 UTC (rev 145628)
@@ -0,0 +1,13 @@
+Tests that we can quickly sort a small sparse array that has a large length.
+
+On success, you will see a series of "PASS" messages, followed by "TEST COMPLETE".
+
+
+array[0] = 42
+PASS result is "42"
+PASS array.length is 10000001
+PASS array[0] is 42
+PASS successfullyParsed is true
+
+TEST COMPLETE
+
Added: trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length.html (0 => 145628)
--- trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length.html (rev 0)
+++ trunk/LayoutTests/fast/js/array-sort-small-sparse-array-with-large-length.html 2013-03-13 00:17:38 UTC (rev 145628)
@@ -0,0 +1,10 @@
+<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
+<html>
+<head>
+<script src=""
+</head>
+<body>
+<script src=""
+<script src=""
+</body>
+</html>
Modified: trunk/LayoutTests/fast/js/jsc-test-list (145627 => 145628)
--- trunk/LayoutTests/fast/js/jsc-test-list 2013-03-13 00:16:24 UTC (rev 145627)
+++ trunk/LayoutTests/fast/js/jsc-test-list 2013-03-13 00:17:38 UTC (rev 145628)
@@ -21,6 +21,7 @@
fast/js/array-reduceRight
fast/js/array-reset-large-index
fast/js/array-slow-put
+fast/js/array-sort-small-sparse-array-with-large-length
fast/js/array-sort-numericCompare
fast/js/array-sort-reentrance
fast/js/array-splice
Added: trunk/LayoutTests/fast/js/script-tests/array-sort-small-sparse-array-with-large-length.js (0 => 145628)
--- trunk/LayoutTests/fast/js/script-tests/array-sort-small-sparse-array-with-large-length.js (rev 0)
+++ trunk/LayoutTests/fast/js/script-tests/array-sort-small-sparse-array-with-large-length.js 2013-03-13 00:17:38 UTC (rev 145628)
@@ -0,0 +1,17 @@
+description(
+"Tests that we can quickly sort a small sparse array that has a large length."
+);
+
+var array = [];
+array[10000000] = 42;
+array.sort();
+var result = "";
+for (var s in array) {
+ debug("array[" + s + "] = " + array[s]);
+ if (result)
+ result += ",";
+ result += array[s];
+}
+shouldBe("result", "\"42\"");
+shouldBe("array.length", "10000001");
+shouldBe("array[0]", "42");
Modified: trunk/Source/_javascript_Core/ChangeLog (145627 => 145628)
--- trunk/Source/_javascript_Core/ChangeLog 2013-03-13 00:16:24 UTC (rev 145627)
+++ trunk/Source/_javascript_Core/ChangeLog 2013-03-13 00:17:38 UTC (rev 145628)
@@ -1,3 +1,22 @@
+2013-03-12 Filip Pizlo <[email protected]>
+
+ Array.prototype.sort should at least try to be PTIME even when the array is in some bizarre mode
+ https://bugs.webkit.org/show_bug.cgi?id=112187
+ <rdar://problem/13393550>
+
+ Reviewed by Michael Saboff and Gavin Barraclough.
+
+ If we have an array-like object in crazy mode passed into Array.prototype.sort, and its length is large,
+ then first copy all elements into a separate, compact, un-holy array and sort that. Then copy back.
+ This means that sorting will be at worst O(n^2) in the actual number of things in the array, rather than
+ O(n^2) in the array's length.
+
+ * runtime/ArrayPrototype.cpp:
+ (JSC::attemptFastSort):
+ (JSC::performSlowSort):
+ (JSC):
+ (JSC::arrayProtoFuncSort):
+
2013-03-12 Tim Horton <[email protected]>
Try to fix the Windows build.
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (145627 => 145628)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2013-03-13 00:16:24 UTC (rev 145627)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2013-03-13 00:17:38 UTC (rev 145628)
@@ -645,39 +645,36 @@
return JSValue();
}
-EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
+static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType)
{
- JSObject* thisObj = exec->hostThisValue().toObject(exec);
- unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
- if (!length || exec->hadException())
- return JSValue::encode(thisObj);
+ if (thisObj->classInfo() != &JSArray::s_info
+ || asArray(thisObj)->hasSparseMap()
+ || shouldUseSlowPut(thisObj->structure()->indexingType()))
+ return false;
+
+ if (isNumericCompareFunction(exec, 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);
+ return true;
+}
- JSValue function = exec->argument(0);
- CallData callData;
- CallType callType = getCallData(function, callData);
-
- if (thisObj->classInfo() == &JSArray::s_info && !asArray(thisObj)->hasSparseMap() && !shouldUseSlowPut(thisObj->structure()->indexingType())) {
- if (isNumericCompareFunction(exec, 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);
- return JSValue::encode(thisObj);
- }
-
+static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType)
+{
// "Min" sort. Not the fastest, but definitely less code than heapsort
// or quicksort, and much less swapping than bubblesort/insertionsort.
for (unsigned i = 0; i < length - 1; ++i) {
JSValue iObj = getOrHole(thisObj, exec, i);
if (exec->hadException())
- return JSValue::encode(jsUndefined());
+ return false;
unsigned themin = i;
JSValue minObj = iObj;
for (unsigned j = i + 1; j < length; ++j) {
JSValue jObj = getOrHole(thisObj, exec, j);
if (exec->hadException())
- return JSValue::encode(jsUndefined());
+ return false;
double compareResult;
if (!jObj)
compareResult = 1;
@@ -705,21 +702,95 @@
if (minObj) {
thisObj->methodTable()->putByIndex(thisObj, exec, i, minObj, true);
if (exec->hadException())
- return JSValue::encode(jsUndefined());
+ return false;
} else if (!thisObj->methodTable()->deletePropertyByIndex(thisObj, exec, i)) {
throwTypeError(exec, "Unable to delete property.");
- return JSValue::encode(jsUndefined());
+ return false;
}
if (iObj) {
thisObj->methodTable()->putByIndex(thisObj, exec, themin, iObj, true);
if (exec->hadException())
- return JSValue::encode(jsUndefined());
+ return false;
} else if (!thisObj->methodTable()->deletePropertyByIndex(thisObj, exec, themin)) {
throwTypeError(exec, "Unable to delete property.");
- return JSValue::encode(jsUndefined());
+ return false;
}
}
}
+ return true;
+}
+
+EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
+{
+ JSObject* thisObj = exec->hostThisValue().toObject(exec);
+ unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
+ if (!length || exec->hadException())
+ return JSValue::encode(thisObj);
+
+ JSValue function = exec->argument(0);
+ CallData callData;
+ CallType callType = getCallData(function, callData);
+
+ if (attemptFastSort(exec, thisObj, function, callData, callType))
+ return JSValue::encode(thisObj);
+
+ // Assume that for small-ish arrays, doing the slow sort directly is better.
+ if (length < 1000)
+ return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined());
+
+ Vector<uint32_t> keys;
+
+ JSGlobalObject* globalObject = JSGlobalObject::create(
+ exec->globalData(), JSGlobalObject::createStructure(exec->globalData(), jsNull()));
+ JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), 0);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ PropertyNameArray nameArray(exec);
+ thisObj->methodTable()->getPropertyNames(thisObj, exec, nameArray, IncludeDontEnumProperties);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+
+ for (size_t i = 0; i < nameArray.size(); ++i) {
+ PropertyName name = nameArray[i];
+ uint32_t index = name.asIndex();
+ if (index == PropertyName::NotAnIndex)
+ continue;
+
+ JSValue value = getOrHole(thisObj, exec, index);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ if (!value)
+ continue;
+ keys.append(index);
+ flatArray->push(exec, value);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
+ if (!attemptFastSort(exec, flatArray, function, callData, callType)
+ && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
+ return JSValue::encode(jsUndefined());
+
+ for (size_t i = 0; i < keys.size(); ++i) {
+ size_t index = keys[i];
+ if (index < flatArray->length())
+ continue;
+
+ if (!thisObj->methodTable()->deletePropertyByIndex(thisObj, exec, index)) {
+ throwTypeError(exec, "Unable to delete property.");
+ return JSValue::encode(jsUndefined());
+ }
+ }
+
+ for (size_t i = flatArray->length(); i--;) {
+ JSValue value = getOrHole(flatArray, exec, i);
+ RELEASE_ASSERT(value);
+ thisObj->methodTable()->putByIndex(thisObj, exec, i, value, true);
+ if (exec->hadException())
+ return JSValue::encode(jsUndefined());
+ }
+
return JSValue::encode(thisObj);
}
_______________________________________________ webkit-changes mailing list [email protected] https://lists.webkit.org/mailman/listinfo/webkit-changes
