Diff
Modified: trunk/JSTests/ChangeLog (236495 => 236496)
--- trunk/JSTests/ChangeLog 2018-09-26 03:14:09 UTC (rev 236495)
+++ trunk/JSTests/ChangeLog 2018-09-26 05:16:22 UTC (rev 236496)
@@ -1,3 +1,34 @@
+2018-09-20 Yusuke Suzuki <yusukesuz...@slowstart.org>
+
+ [JSC] Optimize Array#lastIndexOf
+ https://bugs.webkit.org/show_bug.cgi?id=189780
+
+ Reviewed by Saam Barati.
+
+ * stress/array-lastindexof-array-prototype-trap.js: Added.
+ (shouldBe):
+ (AncestorArray.prototype.get 2):
+ (AncestorArray):
+ * stress/array-lastindexof-have-a-bad-time-c-runtime.js: Added.
+ (shouldBe):
+ * stress/array-lastindexof-hole-nan.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-lastindexof-infinity.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-lastindexof-negative-zero.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-lastindexof-own-getter.js: Added.
+ (shouldBe):
+ (throw.new.Error.get array):
+ (get array):
+ * stress/array-lastindexof-prototype-trap.js: Added.
+ (shouldBe):
+ (DerivedArray.prototype.get 2):
+ (DerivedArray):
+
2018-09-25 Saam Barati <sbar...@apple.com>
Calls to baselineCodeBlockForOriginAndBaselineCodeBlock in operationMaterializeObjectInOSR should actually pass in the baseline CodeBlock
Added: trunk/JSTests/stress/array-lastindexof-array-prototype-trap.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-array-prototype-trap.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-array-prototype-trap.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,45 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+class AncestorArray extends Object {
+ get 2() {
+ this.called = true;
+ return 42;
+ }
+}
+
+Array.prototype.__proto__ = AncestorArray.prototype;
+
+{
+ let array = [];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-lastindexof-cached-length.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-cached-length.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-cached-length.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,24 @@
+function assert(b) {
+ if (!b)
+ throw new Error;
+
+}
+
+const originalLength = 10000;
+let arr = new Proxy([], {
+ has(...args) {
+ assert(parseInt(args[1]) < originalLength);
+ assert(args[0].length - 10 === originalLength);
+ return Reflect.has(...args);
+ }
+});
+
+for (var i = 0; i < originalLength; i++)
+ arr[i] = [];
+
+arr.lastIndexOf(new Object(), {
+ valueOf: function () {
+ arr.length += 10;
+ return 0;
+ }
+});
Added: trunk/JSTests/stress/array-lastindexof-fast-path-effects.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-fast-path-effects.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-fast-path-effects.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,11 @@
+// This shouldn't crash when running with ASAN.
+let arr = [];
+for (var i = 0; i < 1000000; i++)
+ arr[i] = [];
+
+arr.lastIndexOf(new Object(), {
+ valueOf: function () {
+ arr.length = 0;
+ return 0;
+ }
+});
Added: trunk/JSTests/stress/array-lastindexof-have-a-bad-time-c-runtime.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-have-a-bad-time-c-runtime.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-have-a-bad-time-c-runtime.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,43 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+Object.defineProperty(Array.prototype, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+});
+
+{
+ let array = [];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-lastindexof-hole-nan.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-hole-nan.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-hole-nan.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,19 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+
+{
+ let array = [42, , , 0];
+ shouldBe(array.lastIndexOf(Number.NaN), -1);
+ shouldBe(array.lastIndexOf(0), 3);
+}
+{
+ let array = [42.195, , , 0];
+ shouldBe(array.lastIndexOf(Number.NaN), -1);
+}
+{
+ let array = [42.195, Number.NaN, , 0];
+ shouldBe(array.lastIndexOf(Number.NaN), -1);
+}
Added: trunk/JSTests/stress/array-lastindexof-infinity.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-infinity.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-infinity.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,21 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+{
+ let array = [42.195, -0.0, -Infinity];
+ shouldBe(array.lastIndexOf(Infinity), -1);
+ shouldBe(array.lastIndexOf(-Infinity), 2);
+ shouldBe(array.lastIndexOf(42), -1);
+}
+{
+ let array = [1, 2, 3, 0];
+ shouldBe(array.lastIndexOf(Infinity), -1);
+ shouldBe(array.lastIndexOf(-Infinity), -1);
+}
+{
+ let array = ["String", 42.5, Infinity, 33];
+ shouldBe(array.lastIndexOf(Infinity), 2);
+ shouldBe(array.lastIndexOf(-Infinity), -1);
+}
Added: trunk/JSTests/stress/array-lastindexof-negative-zero.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-negative-zero.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-negative-zero.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,25 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+{
+ let array = [42.195, -0.0];
+ shouldBe(array.lastIndexOf(0), 1);
+ shouldBe(array.lastIndexOf(-0), 1);
+}
+{
+ let array = [42.195, 0, -0.0];
+ shouldBe(array.lastIndexOf(0), 2);
+ shouldBe(array.lastIndexOf(-0), 2);
+}
+{
+ let array = [42, 0];
+ shouldBe(array.lastIndexOf(0), 1);
+ shouldBe(array.lastIndexOf(-0), 1);
+}
+{
+ let array = [42, 0, 44];
+ shouldBe(array.lastIndexOf(0), 1);
+ shouldBe(array.lastIndexOf(-0), 1);
+}
Added: trunk/JSTests/stress/array-lastindexof-own-getter.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-own-getter.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-own-getter.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,66 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+{
+ let array = [];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-lastindexof-prototype-trap.js (0 => 236496)
--- trunk/JSTests/stress/array-lastindexof-prototype-trap.js (rev 0)
+++ trunk/JSTests/stress/array-lastindexof-prototype-trap.js 2018-09-26 05:16:22 UTC (rev 236496)
@@ -0,0 +1,48 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+class DerivedArray extends Array {
+ get 2() {
+ this.called = true;
+ return 42;
+ }
+}
+
+{
+ let array = [];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.lastIndexOf(42), 2);
+ shouldBe(array.called, true);
+}
Modified: trunk/Source/_javascript_Core/ChangeLog (236495 => 236496)
--- trunk/Source/_javascript_Core/ChangeLog 2018-09-26 03:14:09 UTC (rev 236495)
+++ trunk/Source/_javascript_Core/ChangeLog 2018-09-26 05:16:22 UTC (rev 236496)
@@ -1,3 +1,16 @@
+2018-09-20 Yusuke Suzuki <yusukesuz...@slowstart.org>
+
+ [JSC] Optimize Array#lastIndexOf
+ https://bugs.webkit.org/show_bug.cgi?id=189780
+
+ Reviewed by Saam Barati.
+
+ Optimize Array#lastIndexOf as the same to Array#indexOf. We add a fast path
+ for JSArray with contiguous storage.
+
+ * runtime/ArrayPrototype.cpp:
+ (JSC::arrayProtoFuncLastIndexOf):
+
2018-09-25 Saam Barati <sbar...@apple.com>
Calls to baselineCodeBlockForOriginAndBaselineCodeBlock in operationMaterializeObjectInOSR should actually pass in the baseline CodeBlock
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (236495 => 236496)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2018-09-26 03:14:09 UTC (rev 236495)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2018-09-26 05:16:22 UTC (rev 236496)
@@ -1150,6 +1150,107 @@
return JSValue::encode(result);
}
+enum class IndexOfDirection { Forward, Backward };
+template<IndexOfDirection direction>
+ALWAYS_INLINE JSValue fastIndexOf(ExecState* exec, VM& vm, JSArray* array, unsigned length, JSValue searchElement, unsigned index)
+{
+ auto scope = DECLARE_THROW_SCOPE(vm);
+
+ bool canDoFastPath = array->canDoFastIndexedAccess(vm)
+ && array->getArrayLength() == length; // The effects in getting `index` could have changed the length of this array.
+ if (!canDoFastPath)
+ return JSValue();
+
+ switch (array->indexingType()) {
+ case ALL_INT32_INDEXING_TYPES: {
+ if (!searchElement.isNumber())
+ return jsNumber(-1);
+ JSValue searchInt32;
+ if (searchElement.isInt32())
+ searchInt32 = searchElement;
+ else {
+ double searchNumber = searchElement.asNumber();
+ if (!canBeInt32(searchNumber))
+ return jsNumber(-1);
+ searchInt32 = jsNumber(static_cast<int32_t>(searchNumber));
+ }
+ auto& butterfly = *array->butterfly();
+ auto data = ""
+ if (direction == IndexOfDirection::Forward) {
+ for (; index < length; ++index) {
+ // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
+ // And the hole never matches against Int32 value.
+ if (searchInt32 == data[index].get())
+ return jsNumber(index);
+ }
+ } else {
+ do {
+ ASSERT(index < length);
+ // Array#lastIndexOf uses `===` semantics (not HashMap isEqual semantics).
+ // And the hole never matches against Int32 value.
+ if (searchInt32 == data[index].get())
+ return jsNumber(index);
+ } while (index--);
+ }
+ return jsNumber(-1);
+ }
+ case ALL_CONTIGUOUS_INDEXING_TYPES: {
+ auto& butterfly = *array->butterfly();
+ auto data = ""
+
+ if (direction == IndexOfDirection::Forward) {
+ for (; index < length; ++index) {
+ JSValue value = data[index].get();
+ if (!value)
+ continue;
+ bool isEqual = JSValue::strictEqual(exec, searchElement, value);
+ RETURN_IF_EXCEPTION(scope, { });
+ if (isEqual)
+ return jsNumber(index);
+ }
+ } else {
+ do {
+ ASSERT(index < length);
+ JSValue value = data[index].get();
+ if (!value)
+ continue;
+ bool isEqual = JSValue::strictEqual(exec, searchElement, value);
+ RETURN_IF_EXCEPTION(scope, { });
+ if (isEqual)
+ return jsNumber(index);
+ } while (index--);
+ }
+ return jsNumber(-1);
+ }
+ case ALL_DOUBLE_INDEXING_TYPES: {
+ if (!searchElement.isNumber())
+ return jsNumber(-1);
+ double searchNumber = searchElement.asNumber();
+ auto& butterfly = *array->butterfly();
+ auto data = ""
+ if (direction == IndexOfDirection::Forward) {
+ for (; index < length; ++index) {
+ // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
+ // And the hole never matches since it is NaN.
+ if (data[index] == searchNumber)
+ return jsNumber(index);
+ }
+ } else {
+ do {
+ ASSERT(index < length);
+ // Array#lastIndexOf uses `===` semantics (not HashMap isEqual semantics).
+ // And the hole never matches since it is NaN.
+ if (data[index] == searchNumber)
+ return jsNumber(index);
+ } while (index--);
+ }
+ return jsNumber(-1);
+ }
+ default:
+ return JSValue();
+ }
+}
+
EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
{
VM& vm = exec->vm();
@@ -1168,65 +1269,8 @@
JSValue searchElement = exec->argument(0);
if (isJSArray(thisObject)) {
- JSArray* array = asArray(thisObject);
- bool canDoFastPath = array->canDoFastIndexedAccess(vm)
- && array->getArrayLength() == length; // The effects in getting `index` could have changed the length of this array.
- if (canDoFastPath) {
- switch (array->indexingType()) {
- case ALL_INT32_INDEXING_TYPES: {
- if (!searchElement.isNumber())
- return JSValue::encode(jsNumber(-1));
- JSValue searchInt32;
- if (searchElement.isInt32())
- searchInt32 = searchElement;
- else {
- double searchNumber = searchElement.asNumber();
- if (!canBeInt32(searchNumber))
- return JSValue::encode(jsNumber(-1));
- searchInt32 = jsNumber(static_cast<int32_t>(searchNumber));
- }
- auto& butterfly = *array->butterfly();
- auto data = ""
- for (; index < length; ++index) {
- // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
- // And the hole never matches against Int32 value.
- if (searchInt32 == data[index].get())
- return JSValue::encode(jsNumber(index));
- }
- return JSValue::encode(jsNumber(-1));
- }
- case ALL_CONTIGUOUS_INDEXING_TYPES: {
- auto& butterfly = *array->butterfly();
- auto data = ""
- for (; index < length; ++index) {
- JSValue value = data[index].get();
- if (!value)
- continue;
- bool isEqual = JSValue::strictEqual(exec, searchElement, value);
- RETURN_IF_EXCEPTION(scope, { });
- if (isEqual)
- return JSValue::encode(jsNumber(index));
- }
- return JSValue::encode(jsNumber(-1));
- }
- case ALL_DOUBLE_INDEXING_TYPES: {
- if (!searchElement.isNumber())
- return JSValue::encode(jsNumber(-1));
- double searchNumber = searchElement.asNumber();
- auto& butterfly = *array->butterfly();
- auto data = ""
- for (; index < length; ++index) {
- // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
- // And the hole never matches since it is NaN.
- if (data[index] == searchNumber)
- return JSValue::encode(jsNumber(index));
- }
- return JSValue::encode(jsNumber(-1));
- }
- default:
- break;
- }
- }
+ if (JSValue result = fastIndexOf<IndexOfDirection::Forward>(exec, vm, asArray(thisObject), length, searchElement, index))
+ return JSValue::encode(result);
}
for (; index < length; ++index) {
@@ -1249,11 +1293,11 @@
auto scope = DECLARE_THROW_SCOPE(vm);
// 15.4.4.15
- JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
- EXCEPTION_ASSERT(!!scope.exception() == !thisObj);
- if (UNLIKELY(!thisObj))
- return encodedJSValue();
- unsigned length = toLength(exec, thisObj);
+ JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
+ EXCEPTION_ASSERT(!!scope.exception() == !thisObject);
+ if (UNLIKELY(!thisObject))
+ return { };
+ unsigned length = toLength(exec, thisObject);
if (UNLIKELY(scope.exception()) || !length)
return JSValue::encode(jsNumber(-1));
@@ -1261,7 +1305,7 @@
if (exec->argumentCount() >= 2) {
JSValue fromValue = exec->uncheckedArgument(1);
double fromDouble = fromValue.toInteger(exec);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ RETURN_IF_EXCEPTION(scope, { });
if (fromDouble < 0) {
fromDouble += length;
if (fromDouble < 0)
@@ -1272,14 +1316,20 @@
}
JSValue searchElement = exec->argument(0);
+
+ if (isJSArray(thisObject)) {
+ if (JSValue result = fastIndexOf<IndexOfDirection::Backward>(exec, vm, asArray(thisObject), length, searchElement, index))
+ return JSValue::encode(result);
+ }
+
do {
- RELEASE_ASSERT(index < length);
- JSValue e = getProperty(exec, thisObj, index);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ ASSERT(index < length);
+ JSValue e = getProperty(exec, thisObject, index);
+ RETURN_IF_EXCEPTION(scope, { });
if (!e)
continue;
bool isEqual = JSValue::strictEqual(exec, searchElement, e);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ RETURN_IF_EXCEPTION(scope, { });
if (isEqual)
return JSValue::encode(jsNumber(index));
} while (index--);
