⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 236240 in webkit


Ignore:
Timestamp:
Sep 19, 2018, 10:54:27 PM (8 years ago)
Author:
yusukesuzuki@slowstart.org
Message:

[JSC] Optimize Array#indexOf in C++ runtime
​https://bugs.webkit.org/show_bug.cgi?id=189507

Reviewed by Saam Barati.

JSTests:

  • 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):

Source/JavaScriptCore:

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):

Location:
trunk
Files:
7 added
9 edited

Legend:

Unmodified
Added
Removed

  • trunk/JSTests/ChangeLog

    r236223 r236240  
     12018-09-19  Yusuke Suzuki  <yusukesuzuki@slowstart.org>
     2
     3        [JSC] Optimize Array#indexOf in C++ runtime
     4        https://bugs.webkit.org/show_bug.cgi?id=189507
     5
     6        Reviewed by Saam Barati.
     7
     8        * stress/array-indexof-array-prototype-trap.js: Added.
     9        (shouldBe):
     10        (AncestorArray.prototype.get 2):
     11        (AncestorArray):
     12        * stress/array-indexof-have-a-bad-time-c-runtime.js: Added.
     13        (shouldBe):
     14        * stress/array-indexof-hole-nan.js: Added.
     15        (shouldBe):
     16        (throw.new.Error):
     17        * stress/array-indexof-infinity.js: Added.
     18        (shouldBe):
     19        (throw.new.Error):
     20        * stress/array-indexof-negative-zero.js: Added.
     21        (shouldBe):
     22        (throw.new.Error):
     23        * stress/array-indexof-own-getter.js: Added.
     24        (shouldBe):
     25        (throw.new.Error.get array):
     26        (get array):
     27        * stress/array-indexof-prototype-trap.js: Added.
     28        (shouldBe):
     29        (DerivedArray.prototype.get 2):
     30        (DerivedArray):
     31
    1322018-09-19  Saam barati  <sbarati@apple.com>
    233

  • trunk/Source/JavaScriptCore/ChangeLog

    r236235 r236240  
     12018-09-19  Yusuke Suzuki  <yusukesuzuki@slowstart.org>
     2
     3        [JSC] Optimize Array#indexOf in C++ runtime
     4        https://bugs.webkit.org/show_bug.cgi?id=189507
     5
     6        Reviewed by Saam Barati.
     7
     8        C++ Array#indexOf runtime function takes so much time in babylon benchmark in
     9        web-tooling-benchmark. While our DFG and FTL has Array#indexOf optimization
     10        and actually it is working well, C++ Array#indexOf is called significant amount
     11        of time before tiering up, and it takes 6.74% of jsc main thread samples according
     12        to perf command in Linux. This is because C++ Array#indexOf is too generic and
     13        misses the chance to optimize JSArray cases.
     14
     15        This patch adds JSArray fast path for Array#indexOf. If we know that indexed
     16        access to the given JSArray is non-observable and indexing type is good for the fast
     17        path, we go to the fast path. This makes sampling of Array#indexOf 3.83% in
     18        babylon web-tooling-benchmark.
     19
     20        * runtime/ArrayPrototype.cpp:
     21        (JSC::arrayProtoFuncIndexOf):
     22        * runtime/JSArray.h:
     23        * runtime/JSArrayInlines.h:
     24        (JSC::JSArray::canDoFastIndexedAccess):
     25        (JSC::toLength):
     26        * runtime/JSCJSValueInlines.h:
     27        (JSC::JSValue::JSValue):
     28        * runtime/JSGlobalObject.h:
     29        * runtime/JSGlobalObjectInlines.h:
     30        (JSC::JSGlobalObject::isArrayPrototypeIndexedAccessFastAndNonObservable):
     31        (JSC::JSGlobalObject::isArrayPrototypeIteratorProtocolFastAndNonObservable):
     32        * runtime/MathCommon.h:
     33        (JSC::canBeStrictInt32):
     34        (JSC::canBeInt32):
     35
    1362018-09-19  Michael Saboff  <msaboff@apple.com>
    237

  • trunk/Source/JavaScriptCore/runtime/ArrayPrototype.cpp

    r235540 r236240  
    11571157
    11581158    // 15.4.4.14
    1159     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
    1160     EXCEPTION_ASSERT(!!scope.exception() == !thisObj);
    1161     if (UNLIKELY(!thisObj))
    1162         return encodedJSValue();
    1163     unsigned length = toLength(exec, thisObj);
    1164     RETURN_IF_EXCEPTION(scope, encodedJSValue());
     1159    JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
     1160    EXCEPTION_ASSERT(!!scope.exception() == !thisObject);
     1161    if (UNLIKELY(!thisObject))
     1162        return { };
     1163    unsigned length = toLength(exec, thisObject);
     1164    RETURN_IF_EXCEPTION(scope, { });
    11651165
    11661166    unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
    1167     RETURN_IF_EXCEPTION(scope, encodedJSValue());
     1167    RETURN_IF_EXCEPTION(scope, { });
    11681168    JSValue searchElement = exec->argument(0);
     1169
     1170    if (isJSArray(thisObject)) {
     1171        JSArray* array = asArray(thisObject);
     1172        if (array->canDoFastIndexedAccess(vm)) {
     1173            switch (array->indexingType()) {
     1174            case ALL_INT32_INDEXING_TYPES: {
     1175                if (!searchElement.isNumber())
     1176                    return JSValue::encode(jsNumber(-1));
     1177                JSValue searchInt32;
     1178                if (searchElement.isInt32())
     1179                    searchInt32 = searchElement;
     1180                else {
     1181                    double searchNumber = searchElement.asNumber();
     1182                    if (!canBeInt32(searchNumber))
     1183                        return JSValue::encode(jsNumber(-1));
     1184                    searchInt32 = jsNumber(static_cast<int32_t>(searchNumber));
     1185                }
     1186                auto& butterfly = *array->butterfly();
     1187                auto data = butterfly.contiguous().data();
     1188                for (; index < length; ++index) {
     1189                    // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
     1190                    // And the hole never matches against Int32 value.
     1191                    if (searchInt32 == data[index].get())
     1192                        return JSValue::encode(jsNumber(index));
     1193                }
     1194                return JSValue::encode(jsNumber(-1));
     1195            }
     1196            case ALL_CONTIGUOUS_INDEXING_TYPES: {
     1197                auto& butterfly = *array->butterfly();
     1198                auto data = butterfly.contiguous().data();
     1199                for (; index < length; ++index) {
     1200                    JSValue value = data[index].get();
     1201                    if (!value)
     1202                        continue;
     1203                    bool isEqual = JSValue::strictEqual(exec, searchElement, value);
     1204                    RETURN_IF_EXCEPTION(scope, { });
     1205                    if (isEqual)
     1206                        return JSValue::encode(jsNumber(index));
     1207                }
     1208                return JSValue::encode(jsNumber(-1));
     1209            }
     1210            case ALL_DOUBLE_INDEXING_TYPES: {
     1211                if (!searchElement.isNumber())
     1212                    return JSValue::encode(jsNumber(-1));
     1213                double searchNumber = searchElement.asNumber();
     1214                auto& butterfly = *array->butterfly();
     1215                auto data = butterfly.contiguousDouble().data();
     1216                for (; index < length; ++index) {
     1217                    // Array#indexOf uses `===` semantics (not HashMap isEqual semantics).
     1218                    // And the hole never matches since it is NaN.
     1219                    if (data[index] == searchNumber)
     1220                        return JSValue::encode(jsNumber(index));
     1221                }
     1222                return JSValue::encode(jsNumber(-1));
     1223            }
     1224            default:
     1225                break;
     1226            }
     1227        }
     1228    }
     1229
    11691230    for (; index < length; ++index) {
    1170         JSValue e = getProperty(exec, thisObj, index);
    1171         RETURN_IF_EXCEPTION(scope, encodedJSValue());
     1231        JSValue e = getProperty(exec, thisObject, index);
     1232        RETURN_IF_EXCEPTION(scope, { });
    11721233        if (!e)
    11731234            continue;
    11741235        bool isEqual = JSValue::strictEqual(exec, searchElement, e);
    1175         RETURN_IF_EXCEPTION(scope, encodedJSValue());
     1236        RETURN_IF_EXCEPTION(scope, { });
    11761237        if (isEqual)
    11771238            return JSValue::encode(jsNumber(index));

  • trunk/Source/JavaScriptCore/runtime/JSArray.h

    r233722 r236240  
    102102
    103103    bool canFastCopy(VM&, JSArray* otherArray);
     104    bool canDoFastIndexedAccess(VM&);
    104105    // This function returns NonArray if the indexing types are not compatable for copying.
    105106    IndexingType mergeIndexingTypeForCopying(IndexingType other);

  • trunk/Source/JavaScriptCore/runtime/JSArrayInlines.h

    r235356 r236240  
    2020#pragma once
    2121
     22#include "ArrayPrototype.h"
    2223#include "Error.h"
    2324#include "JSArray.h"
    … …  
    7172}
    7273
     74inline bool JSArray::canDoFastIndexedAccess(VM& vm)
     75{
     76    JSGlobalObject* globalObject = this->globalObject();
     77    if (!globalObject->isArrayPrototypeIndexedAccessFastAndNonObservable())
     78        return false;
     79
     80    Structure* structure = this->structure(vm);
     81    // This is the fast case. Many arrays will be an original array.
     82    if (globalObject->isOriginalArrayStructure(structure))
     83        return true;
     84
     85    if (structure->mayInterceptIndexedAccesses())
     86        return false;
     87
     88    if (getPrototypeDirect(vm) != globalObject->arrayPrototype())
     89        return false;
     90
     91    return true;
     92}
     93
    7394ALWAYS_INLINE double toLength(ExecState* exec, JSObject* obj)
    7495{
    7596    VM& vm = exec->vm();
    7697    auto scope = DECLARE_THROW_SCOPE(vm);
    77     if (isJSArray(obj))
     98    if (LIKELY(isJSArray(obj)))
    7899        return jsCast<JSArray*>(obj)->length();
    79100

  • trunk/Source/JavaScriptCore/runtime/JSCJSValueInlines.h

    r235491 r236240  
    168168inline JSValue::JSValue(double d)
    169169{
    170     // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
    171     const int32_t asInt32 = static_cast<int32_t>(d);
    172     if (asInt32 != d || (!asInt32 && std::signbit(d))) { // true for -0.0
    173         *this = JSValue(EncodeAsDouble, d);
     170    if (canBeStrictInt32(d)) {
     171        *this = JSValue(static_cast<int32_t>(d));
    174172        return;
    175173    }
    176     *this = JSValue(static_cast<int32_t>(d));
     174    *this = JSValue(EncodeAsDouble, d);
    177175}
    178176

  • trunk/Source/JavaScriptCore/runtime/JSGlobalObject.h

    r235419 r236240  
    477477    PoisonedUniquePtr<ObjectPropertyChangeAdaptiveWatchpoint<InlineWatchpointSet>> m_numberPrototypeToStringWatchpoint;
    478478
     479    bool isArrayPrototypeIndexedAccessFastAndNonObservable();
    479480    bool isArrayPrototypeIteratorProtocolFastAndNonObservable();
    480481    bool isMapPrototypeIteratorProtocolFastAndNonObservable();

  • trunk/Source/JavaScriptCore/runtime/JSGlobalObjectInlines.h

    r223746 r236240  
    5353}
    5454
     55ALWAYS_INLINE bool JSGlobalObject::isArrayPrototypeIndexedAccessFastAndNonObservable()
     56{
     57    // We're fast if we don't have any indexed properties on the prototype.
     58    return !isHavingABadTime() && arrayPrototypeChainIsSane();
     59}
    5560
    5661ALWAYS_INLINE bool JSGlobalObject::isArrayPrototypeIteratorProtocolFastAndNonObservable()
    … …  
    6469    // executing concurrently.
    6570
    66     return arrayIteratorProtocolWatchpoint().isStillValid() && !isHavingABadTime() && arrayPrototypeChainIsSane();
     71    return arrayIteratorProtocolWatchpoint().isStillValid() && isArrayPrototypeIndexedAccessFastAndNonObservable();
    6772}
    6873

  • trunk/Source/JavaScriptCore/runtime/MathCommon.h

    r232244 r236240  
    179179}
    180180
     181ALWAYS_INLINE bool canBeStrictInt32(double value)
     182{
     183    // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
     184    const int32_t asInt32 = static_cast<int32_t>(value);
     185    return !(asInt32 != value || (!asInt32 && std::signbit(value))); // true for -0.0
     186}
     187
     188ALWAYS_INLINE bool canBeInt32(double value)
     189{
     190    // Note: Strictly speaking this is an undefined behavior.
     191    return static_cast<int32_t>(value) == value;
     192}
     193
    181194extern "C" {
    182195double JIT_OPERATION jsRound(double value) REFERENCED_FROM_ASM WTF_INTERNAL;
Note: See TracChangeset for help on using the changeset viewer.