Diff
Modified: trunk/JSTests/ChangeLog (236239 => 236240)
--- trunk/JSTests/ChangeLog 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/JSTests/ChangeLog 2018-09-20 05:54:27 UTC (rev 236240)
@@ -1,3 +1,34 @@
+2018-09-19 Yusuke Suzuki <[email protected]>
+
+ [JSC] Optimize Array#indexOf in C++ runtime
+ https://bugs.webkit.org/show_bug.cgi?id=189507
+
+ Reviewed by Saam Barati.
+
+ * stress/array-indexof-array-prototype-trap.js: Added.
+ (shouldBe):
+ (AncestorArray.prototype.get 2):
+ (AncestorArray):
+ * stress/array-indexof-have-a-bad-time-c-runtime.js: Added.
+ (shouldBe):
+ * stress/array-indexof-hole-nan.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-indexof-infinity.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-indexof-negative-zero.js: Added.
+ (shouldBe):
+ (throw.new.Error):
+ * stress/array-indexof-own-getter.js: Added.
+ (shouldBe):
+ (throw.new.Error.get array):
+ (get array):
+ * stress/array-indexof-prototype-trap.js: Added.
+ (shouldBe):
+ (DerivedArray.prototype.get 2):
+ (DerivedArray):
+
2018-09-19 Saam barati <[email protected]>
AI rule for MultiPutByOffset executes its effects in the wrong order
Added: trunk/JSTests/stress/array-indexof-array-prototype-trap.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-array-prototype-trap.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-array-prototype-trap.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -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.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-indexof-have-a-bad-time-c-runtime.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-have-a-bad-time-c-runtime.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-have-a-bad-time-c-runtime.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -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.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-indexof-hole-nan.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-hole-nan.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-hole-nan.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -0,0 +1,19 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+
+{
+ let array = [42, , , 0];
+ shouldBe(array.indexOf(Number.NaN), -1);
+ shouldBe(array.indexOf(0), 3);
+}
+{
+ let array = [42.195, , , 0];
+ shouldBe(array.indexOf(Number.NaN), -1);
+}
+{
+ let array = [42.195, Number.NaN, , 0];
+ shouldBe(array.indexOf(Number.NaN), -1);
+}
Added: trunk/JSTests/stress/array-indexof-infinity.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-infinity.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-infinity.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -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.indexOf(Infinity), -1);
+ shouldBe(array.indexOf(-Infinity), 2);
+ shouldBe(array.indexOf(42), -1);
+}
+{
+ let array = [1, 2, 3, 0];
+ shouldBe(array.indexOf(Infinity), -1);
+ shouldBe(array.indexOf(-Infinity), -1);
+}
+{
+ let array = ["String", 42.5, Infinity, 33];
+ shouldBe(array.indexOf(Infinity), 2);
+ shouldBe(array.indexOf(-Infinity), -1);
+}
Added: trunk/JSTests/stress/array-indexof-negative-zero.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-negative-zero.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-negative-zero.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -0,0 +1,20 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+{
+ let array = [42.195, -0.0];
+ shouldBe(array.indexOf(0), 1);
+ shouldBe(array.indexOf(-0), 1);
+}
+{
+ let array = [42.195, 0, -0.0];
+ shouldBe(array.indexOf(0), 1);
+ shouldBe(array.indexOf(-0), 1);
+}
+{
+ let array = [42, 0];
+ shouldBe(array.indexOf(0), 1);
+ shouldBe(array.indexOf(-0), 1);
+}
Added: trunk/JSTests/stress/array-indexof-own-getter.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-own-getter.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-own-getter.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -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.indexOf(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.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ Object.defineProperty(array, 2, {
+ get() {
+ this.called = true;
+ return 42;
+ }
+ });
+ array.length = 42;
+ shouldBe(array.indexOf(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.indexOf(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.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
Added: trunk/JSTests/stress/array-indexof-prototype-trap.js (0 => 236240)
--- trunk/JSTests/stress/array-indexof-prototype-trap.js (rev 0)
+++ trunk/JSTests/stress/array-indexof-prototype-trap.js 2018-09-20 05:54:27 UTC (rev 236240)
@@ -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.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [20, 20];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = [42.195];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
+{
+ let array = ["Hello"];
+ array.__proto__ = DerivedArray.prototype;
+ array.length = 42;
+ ensureArrayStorage(array);
+ shouldBe(array.indexOf(42), 2);
+ shouldBe(array.called, true);
+}
Modified: trunk/Source/_javascript_Core/ChangeLog (236239 => 236240)
--- trunk/Source/_javascript_Core/ChangeLog 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/ChangeLog 2018-09-20 05:54:27 UTC (rev 236240)
@@ -1,3 +1,38 @@
+2018-09-19 Yusuke Suzuki <[email protected]>
+
+ [JSC] Optimize Array#indexOf in C++ runtime
+ https://bugs.webkit.org/show_bug.cgi?id=189507
+
+ Reviewed by Saam Barati.
+
+ C++ Array#indexOf runtime function takes so much time in babylon benchmark in
+ web-tooling-benchmark. While our DFG and FTL has Array#indexOf optimization
+ and actually it is working well, C++ Array#indexOf is called significant amount
+ of time before tiering up, and it takes 6.74% of jsc main thread samples according
+ to perf command in Linux. This is because C++ Array#indexOf is too generic and
+ misses the chance to optimize JSArray cases.
+
+ This patch adds JSArray fast path for Array#indexOf. If we know that indexed
+ access to the given JSArray is non-observable and indexing type is good for the fast
+ path, we go to the fast path. This makes sampling of Array#indexOf 3.83% in
+ babylon web-tooling-benchmark.
+
+ * runtime/ArrayPrototype.cpp:
+ (JSC::arrayProtoFuncIndexOf):
+ * runtime/JSArray.h:
+ * runtime/JSArrayInlines.h:
+ (JSC::JSArray::canDoFastIndexedAccess):
+ (JSC::toLength):
+ * runtime/JSCJSValueInlines.h:
+ (JSC::JSValue::JSValue):
+ * runtime/JSGlobalObject.h:
+ * runtime/JSGlobalObjectInlines.h:
+ (JSC::JSGlobalObject::isArrayPrototypeIndexedAccessFastAndNonObservable):
+ (JSC::JSGlobalObject::isArrayPrototypeIteratorProtocolFastAndNonObservable):
+ * runtime/MathCommon.h:
+ (JSC::canBeStrictInt32):
+ (JSC::canBeInt32):
+
2018-09-19 Michael Saboff <[email protected]>
Add functions to measure memory footprint to JSC
Modified: trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/ArrayPrototype.cpp 2018-09-20 05:54:27 UTC (rev 236240)
@@ -1156,23 +1156,84 @@
auto scope = DECLARE_THROW_SCOPE(vm);
// 15.4.4.14
- JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
- EXCEPTION_ASSERT(!!scope.exception() == !thisObj);
- if (UNLIKELY(!thisObj))
- return encodedJSValue();
- unsigned length = toLength(exec, thisObj);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
+ EXCEPTION_ASSERT(!!scope.exception() == !thisObject);
+ if (UNLIKELY(!thisObject))
+ return { };
+ unsigned length = toLength(exec, thisObject);
+ RETURN_IF_EXCEPTION(scope, { });
unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ RETURN_IF_EXCEPTION(scope, { });
JSValue searchElement = exec->argument(0);
+
+ if (isJSArray(thisObject)) {
+ JSArray* array = asArray(thisObject);
+ if (array->canDoFastIndexedAccess(vm)) {
+ 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;
+ }
+ }
+ }
+
for (; index < length; ++index) {
- JSValue e = getProperty(exec, thisObj, index);
- RETURN_IF_EXCEPTION(scope, encodedJSValue());
+ 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));
}
Modified: trunk/Source/_javascript_Core/runtime/JSArray.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/JSArray.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/JSArray.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -101,6 +101,7 @@
JSArray* fastSlice(ExecState&, unsigned startIndex, unsigned count);
bool canFastCopy(VM&, JSArray* otherArray);
+ bool canDoFastIndexedAccess(VM&);
// This function returns NonArray if the indexing types are not compatable for copying.
IndexingType mergeIndexingTypeForCopying(IndexingType other);
bool appendMemcpy(ExecState*, VM&, unsigned startIndex, JSArray* otherArray);
Modified: trunk/Source/_javascript_Core/runtime/JSArrayInlines.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/JSArrayInlines.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/JSArrayInlines.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -19,6 +19,7 @@
#pragma once
+#include "ArrayPrototype.h"
#include "Error.h"
#include "JSArray.h"
#include "JSCellInlines.h"
@@ -70,11 +71,31 @@
return true;
}
+inline bool JSArray::canDoFastIndexedAccess(VM& vm)
+{
+ JSGlobalObject* globalObject = this->globalObject();
+ if (!globalObject->isArrayPrototypeIndexedAccessFastAndNonObservable())
+ return false;
+
+ Structure* structure = this->structure(vm);
+ // This is the fast case. Many arrays will be an original array.
+ if (globalObject->isOriginalArrayStructure(structure))
+ return true;
+
+ if (structure->mayInterceptIndexedAccesses())
+ return false;
+
+ if (getPrototypeDirect(vm) != globalObject->arrayPrototype())
+ return false;
+
+ return true;
+}
+
ALWAYS_INLINE double toLength(ExecState* exec, JSObject* obj)
{
VM& vm = exec->vm();
auto scope = DECLARE_THROW_SCOPE(vm);
- if (isJSArray(obj))
+ if (LIKELY(isJSArray(obj)))
return jsCast<JSArray*>(obj)->length();
JSValue lengthValue = obj->get(exec, vm.propertyNames->length);
Modified: trunk/Source/_javascript_Core/runtime/JSCJSValueInlines.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/JSCJSValueInlines.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/JSCJSValueInlines.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -167,13 +167,11 @@
inline JSValue::JSValue(double d)
{
- // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
- const int32_t asInt32 = static_cast<int32_t>(d);
- if (asInt32 != d || (!asInt32 && std::signbit(d))) { // true for -0.0
- *this = JSValue(EncodeAsDouble, d);
+ if (canBeStrictInt32(d)) {
+ *this = JSValue(static_cast<int32_t>(d));
return;
}
- *this = JSValue(static_cast<int32_t>(d));
+ *this = JSValue(EncodeAsDouble, d);
}
inline EncodedJSValue JSValue::encode(JSValue value)
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalObject.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/JSGlobalObject.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalObject.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -476,6 +476,7 @@
PoisonedUniquePtr<ObjectPropertyChangeAdaptiveWatchpoint<InlineWatchpointSet>> m_setPrototypeAddWatchpoint;
PoisonedUniquePtr<ObjectPropertyChangeAdaptiveWatchpoint<InlineWatchpointSet>> m_numberPrototypeToStringWatchpoint;
+ bool isArrayPrototypeIndexedAccessFastAndNonObservable();
bool isArrayPrototypeIteratorProtocolFastAndNonObservable();
bool isMapPrototypeIteratorProtocolFastAndNonObservable();
bool isSetPrototypeIteratorProtocolFastAndNonObservable();
Modified: trunk/Source/_javascript_Core/runtime/JSGlobalObjectInlines.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/JSGlobalObjectInlines.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/JSGlobalObjectInlines.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -52,6 +52,11 @@
&& objectPrototypeIsSane();
}
+ALWAYS_INLINE bool JSGlobalObject::isArrayPrototypeIndexedAccessFastAndNonObservable()
+{
+ // We're fast if we don't have any indexed properties on the prototype.
+ return !isHavingABadTime() && arrayPrototypeChainIsSane();
+}
ALWAYS_INLINE bool JSGlobalObject::isArrayPrototypeIteratorProtocolFastAndNonObservable()
{
@@ -63,7 +68,7 @@
// carefully set up watchpoints to have correct ordering while JS code is
// executing concurrently.
- return arrayIteratorProtocolWatchpoint().isStillValid() && !isHavingABadTime() && arrayPrototypeChainIsSane();
+ return arrayIteratorProtocolWatchpoint().isStillValid() && isArrayPrototypeIndexedAccessFastAndNonObservable();
}
// We're non-observable if the iteration protocol hasn't changed.
Modified: trunk/Source/_javascript_Core/runtime/MathCommon.h (236239 => 236240)
--- trunk/Source/_javascript_Core/runtime/MathCommon.h 2018-09-20 03:41:38 UTC (rev 236239)
+++ trunk/Source/_javascript_Core/runtime/MathCommon.h 2018-09-20 05:54:27 UTC (rev 236240)
@@ -178,6 +178,19 @@
return reciprocal;
}
+ALWAYS_INLINE bool canBeStrictInt32(double value)
+{
+ // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
+ const int32_t asInt32 = static_cast<int32_t>(value);
+ return !(asInt32 != value || (!asInt32 && std::signbit(value))); // true for -0.0
+}
+
+ALWAYS_INLINE bool canBeInt32(double value)
+{
+ // Note: Strictly speaking this is an undefined behavior.
+ return static_cast<int32_t>(value) == value;
+}
+
extern "C" {
double JIT_OPERATION jsRound(double value) REFERENCED_FROM_ASM WTF_INTERNAL;
