Bug 189507 – [JSC] Optimize Array#indexOf in C++ runtime

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Yusuke Suzuki]

web-tooling-benchmark babylon shows that C++ runtime of Array#indexOf takes so much time (According to Linux perf, it shows 6.9% of the main thread, lol).
Our C++ Array#indexOf is too naive. It repeatedly calls getProperty function, which is not so fast.

We can add a fast path for JSArray, which should be similar to the thing implemented in DFG / FTL.

[Yusuke Suzuki]

Created attachment 349410 [details]
Patch

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass mac-wk2-ews (mac-wk2):
Output: https://webkit-queues.webkit.org/results/9175067

New failing tests:
ietestcenter/Javascript/15.4.4.14-5-3.html
ietestcenter/Javascript/15.4.4.14-5-10.html
ietestcenter/Javascript/15.4.4.14-6-1.html
ietestcenter/Javascript/15.4.4.14-5-15.html
ietestcenter/Javascript/15.4.4.14-5-1.html
ietestcenter/Javascript/15.4.4.14-8-9.html
ietestcenter/Javascript/15.4.4.14-5-31.html
ietestcenter/Javascript/15.4.4.14-8-1.html
ietestcenter/Javascript/15.4.4.14-5-20.html
ietestcenter/Javascript/15.4.4.14-8-3.html
ietestcenter/Javascript/15.4.4.14-7-1.html
js/dom/array-indexof.html
ietestcenter/Javascript/15.4.4.14-5-11.html
ietestcenter/Javascript/15.4.4.14-5-2.html
ietestcenter/Javascript/15.4.4.14-5-18.html
ietestcenter/Javascript/15.4.4.14-5-32.html
ietestcenter/Javascript/15.4.4.14-5-19.html
ietestcenter/Javascript/15.4.4.14-7-4.html

[EWS Watchlist]

Created attachment 349421 [details]
Archive of layout-test-results from ews107 for mac-sierra-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: ews107  Port: mac-sierra-wk2  Platform: Mac OS X 10.12.6

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass jsc-ews (mac):
Output: https://webkit-queues.webkit.org/results/9175059

New failing tests:
stress/array-indexof-negative-index.js.dfg-maximal-flush-validate-no-cjit
stress/array-indexof-negative-index.js.default
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla
stress/array-indexof-index.js.ftl-no-cjit-no-inline-validate
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla-ftl-eager-no-cjit-validate-phases
stress/array-indexof-index.js.dfg-eager
stress/array-indexof-index.js.ftl-eager
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla-llint
stress/array-indexof-index.js.ftl-no-cjit-validate-sampling-profiler
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla-no-ftl
stress/array-indexof-negative-index.js.ftl-no-cjit-no-inline-validate
stress/array-indexof-index.js.ftl-no-cjit-small-pool
stress/array-indexof-index.js.default
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla-dfg-eager-no-cjit-validate-phases
stress/array-indexof-negative-index.js.ftl-eager-no-cjit-b3o1
ChakraCore.yaml/ChakraCore/test/Array/array_indexOf.js.default
stress/array-indexof-negative-index.js.no-cjit-validate-phases
stress/array-indexof-index.js.no-cjit-collect-continuously
mozilla-tests.yaml/js1_6/Array/regress-290592.js.mozilla-baseline
stress/array-indexof-negative-index.js.ftl-no-cjit-validate-sampling-profiler
stress/array-indexof-negative-index.js.no-llint
stress/array-indexof-index.js.ftl-eager-no-cjit-b3o1
stress/array-indexof-index.js.no-cjit-validate-phases
stress/array-indexof-index.js.dfg-eager-no-cjit-validate
stress/array-indexof-negative-index.js.ftl-no-cjit-b3o1
stress/array-indexof-negative-index.js.dfg-eager-no-cjit-validate
stress/array-indexof-negative-index.js.ftl-eager-no-cjit
stress/array-indexof-negative-index.js.no-ftl
stress/array-indexof-index.js.ftl-eager-no-cjit
stress/array-indexof-negative-index.js.ftl-eager
stress/array-indexof-index.js.dfg-maximal-flush-validate-no-cjit
stress/array-indexof-negative-index.js.no-cjit-collect-continuously
stress/array-indexof-negative-index.js.ftl-no-cjit-small-pool
stress/array-indexof-index.js.ftl-no-cjit-no-put-stack-validate
stress/array-indexof-index.js.no-llint
stress/array-indexof-index.js.no-ftl
stress/array-indexof-index.js.ftl-no-cjit-b3o1
stress/array-indexof-negative-index.js.dfg-eager
stress/array-indexof-negative-index.js.ftl-no-cjit-no-put-stack-validate
apiTests

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass mac-debug-ews (mac):
Output: https://webkit-queues.webkit.org/results/9175265

New failing tests:
ietestcenter/Javascript/15.4.4.14-5-3.html
ietestcenter/Javascript/15.4.4.14-5-10.html
ietestcenter/Javascript/15.4.4.14-8-3.html
ietestcenter/Javascript/15.4.4.14-5-15.html
ietestcenter/Javascript/15.4.4.14-5-1.html
ietestcenter/Javascript/15.4.4.14-8-9.html
ietestcenter/Javascript/15.4.4.14-5-31.html
ietestcenter/Javascript/15.4.4.14-8-1.html
ietestcenter/Javascript/15.4.4.14-5-20.html
ietestcenter/Javascript/15.4.4.14-6-1.html
ietestcenter/Javascript/15.4.4.14-7-1.html
js/dom/array-indexof.html
ietestcenter/Javascript/15.4.4.14-5-11.html
ietestcenter/Javascript/15.4.4.14-5-2.html
ietestcenter/Javascript/15.4.4.14-5-18.html
ietestcenter/Javascript/15.4.4.14-5-32.html
ietestcenter/Javascript/15.4.4.14-5-19.html
ietestcenter/Javascript/15.4.4.14-7-4.html

[EWS Watchlist]

Created attachment 349423 [details]
Archive of layout-test-results from ews112 for mac-sierra

The attached test failures were seen while running run-webkit-tests on the mac-debug-ews.
Bot: ews112  Port: mac-sierra  Platform: Mac OS X 10.12.6

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: https://webkit-queues.webkit.org/results/9175273

New failing tests:
ietestcenter/Javascript/15.4.4.14-5-3.html
ietestcenter/Javascript/15.4.4.14-5-10.html
ietestcenter/Javascript/15.4.4.14-6-1.html
ietestcenter/Javascript/15.4.4.14-5-15.html
ietestcenter/Javascript/15.4.4.14-5-1.html
ietestcenter/Javascript/15.4.4.14-8-9.html
ietestcenter/Javascript/15.4.4.14-5-31.html
ietestcenter/Javascript/15.4.4.14-8-1.html
ietestcenter/Javascript/15.4.4.14-5-20.html
ietestcenter/Javascript/15.4.4.14-8-3.html
ietestcenter/Javascript/15.4.4.14-7-1.html
js/dom/array-indexof.html
ietestcenter/Javascript/15.4.4.14-5-11.html
ietestcenter/Javascript/15.4.4.14-5-2.html
ietestcenter/Javascript/15.4.4.14-5-18.html
ietestcenter/Javascript/15.4.4.14-5-32.html
ietestcenter/Javascript/15.4.4.14-5-19.html
ietestcenter/Javascript/15.4.4.14-7-4.html

[EWS Watchlist]

Created attachment 349425 [details]
Archive of layout-test-results from ews126 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews126  Port: ios-simulator-wk2  Platform: Mac OS X 10.13.4

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass mac-ews (mac):
Output: https://webkit-queues.webkit.org/results/9176274

New failing tests:
ietestcenter/Javascript/15.4.4.14-5-3.html
ietestcenter/Javascript/15.4.4.14-5-10.html
ietestcenter/Javascript/15.4.4.14-6-1.html
ietestcenter/Javascript/15.4.4.14-5-15.html
ietestcenter/Javascript/15.4.4.14-5-1.html
ietestcenter/Javascript/15.4.4.14-8-9.html
ietestcenter/Javascript/15.4.4.14-5-31.html
ietestcenter/Javascript/15.4.4.14-8-1.html
ietestcenter/Javascript/15.4.4.14-5-20.html
ietestcenter/Javascript/15.4.4.14-8-3.html
ietestcenter/Javascript/15.4.4.14-7-1.html
js/dom/array-indexof.html
ietestcenter/Javascript/15.4.4.14-5-11.html
ietestcenter/Javascript/15.4.4.14-5-2.html
ietestcenter/Javascript/15.4.4.14-5-18.html
ietestcenter/Javascript/15.4.4.14-5-32.html
ietestcenter/Javascript/15.4.4.14-5-19.html
ietestcenter/Javascript/15.4.4.14-7-4.html

[EWS Watchlist]

Created attachment 349437 [details]
Archive of layout-test-results from ews103 for mac-sierra

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: ews103  Port: mac-sierra  Platform: Mac OS X 10.12.6

[EWS Watchlist]

Comment on attachment 349410 [details]
Patch

Attachment 349410 [details] did not pass ios-sim-ews (ios-simulator-wk2):
Output: https://webkit-queues.webkit.org/results/9177334

New failing tests:
ietestcenter/Javascript/15.4.4.14-5-3.html
ietestcenter/Javascript/15.4.4.14-5-10.html
ietestcenter/Javascript/15.4.4.14-6-1.html
ietestcenter/Javascript/15.4.4.14-5-15.html
ietestcenter/Javascript/15.4.4.14-5-1.html
ietestcenter/Javascript/15.4.4.14-8-9.html
ietestcenter/Javascript/15.4.4.14-5-31.html
ietestcenter/Javascript/15.4.4.14-8-1.html
ietestcenter/Javascript/15.4.4.14-5-20.html
ietestcenter/Javascript/15.4.4.14-8-3.html
ietestcenter/Javascript/15.4.4.14-7-1.html
js/dom/array-indexof.html
ietestcenter/Javascript/15.4.4.14-5-11.html
ietestcenter/Javascript/15.4.4.14-5-2.html
ietestcenter/Javascript/15.4.4.14-5-18.html
ietestcenter/Javascript/15.4.4.14-5-32.html
ietestcenter/Javascript/15.4.4.14-5-19.html
ietestcenter/Javascript/15.4.4.14-7-4.html

[EWS Watchlist]

Created attachment 349465 [details]
Archive of layout-test-results from ews124 for ios-simulator-wk2

The attached test failures were seen while running run-webkit-tests on the ios-sim-ews.
Bot: ews124  Port: ios-simulator-wk2  Platform: Mac OS X 10.13.4

[Yusuke Suzuki]

Created attachment 349546 [details]
Patch

[Yusuke Suzuki]

Created attachment 349550 [details]
Patch

[Yusuke Suzuki]

Created attachment 349553 [details]
Patch

[Yusuke Suzuki]

Created attachment 349581 [details]
Patch

[Saam Barati]

Comment on attachment 349581 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=349581&action=review

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1172
> +        if (array->canFastIndexedAccess(vm)) {

Does this guarantee our prototype chain is sane?

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1182
> +                    if (!canBeInt32(searchNumber))

Do you have tests for this? For NaN/Inf/-0, +0, etc

Does this in the spec use === semantics or the hashmap isEqual semantics?

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1216
> +                    // Hole never matches since it is NaN.

I guess my above quetion applies here? Will
array.indexOf(NaN)
always return -1?

> Source/JavaScriptCore/runtime/JSArrayInlines.h:74
> +inline bool JSArray::canFastIndexedAccess(VM& vm)

I think you're missing something between "can" and "fast" in this name. Maybe: "canDoFastIndexedAccess" or "canDoFastIndexedAccesses"

> Source/JavaScriptCore/runtime/JSGlobalObjectInlines.h:58
> +

style: No need for this newline IMO

> Source/JavaScriptCore/runtime/MathCommon.h:190
> +    // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.

I don't understand this comment. What subsequent statement?

[Saam Barati]

Comment on attachment 349581 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=349581&action=review

>> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1216
>> +                    // Hole never matches since it is NaN.
> 
> I guess my above quetion applies here? Will
> array.indexOf(NaN)
> always return -1?

I see from your tests that the answer is that [NaN].indexOf(NaN) === -1

Maybe it's worth stating in your comment that this uses === semantics instead of hashmap isEqual semantics

[Yusuke Suzuki]

Comment on attachment 349581 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=349581&action=review

>> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1172
>> +        if (array->canFastIndexedAccess(vm)) {
> 
> Does this guarantee our prototype chain is sane?

Yes. It is guaranteed. And it is tested in array-indexof-prototype-trap.js and array-indexof-array-prototype-trap.js.

>> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1182
>> +                    if (!canBeInt32(searchNumber))
> 
> Do you have tests for this? For NaN/Inf/-0, +0, etc
> 
> Does this in the spec use === semantics or the hashmap isEqual semantics?

Yes, it is tested in array-indexof-negative-zero.js and array-indexof-hole-nan.js. And tests are added for Inf case too.
Array#indexOf uses `===` semantics.

>>> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1216
>>> +                    // Hole never matches since it is NaN.
>> 
>> I guess my above quetion applies here? Will
>> array.indexOf(NaN)
>> always return -1?
> 
> I see from your tests that the answer is that [NaN].indexOf(NaN) === -1
> 
> Maybe it's worth stating in your comment that this uses === semantics instead of hashmap isEqual semantics

Added.

>> Source/JavaScriptCore/runtime/JSArrayInlines.h:74
>> +inline bool JSArray::canFastIndexedAccess(VM& vm)
> 
> I think you're missing something between "can" and "fast" in this name. Maybe: "canDoFastIndexedAccess" or "canDoFastIndexedAccesses"

I think `canDoFastIndexedAccess` sounds nice. Fixed.

>> Source/JavaScriptCore/runtime/JSGlobalObjectInlines.h:58
>> +
> 
> style: No need for this newline IMO

Fixed.

>> Source/JavaScriptCore/runtime/MathCommon.h:190
>> +    // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
> 
> I don't understand this comment. What subsequent statement?

`static_cast<int32_t>(value)` with `value` not in int32_t is an UB strictly speaking.
This comment is moved from `JSValue::JSValue(double d)`.

[Yusuke Suzuki]

Created attachment 350087 [details]
Patch

[Saam Barati]

Comment on attachment 350087 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=350087&action=review

> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1204
> +                    RETURN_IF_EXCEPTION(scope, encodedJSValue());

nit: I think you can just use "{ }" instead of "encodedJSValue()"

> Source/JavaScriptCore/runtime/MathCommon.h:190
> +    // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.

I'm still super confused about this comment. What "subsequent" statement are we talking about here? I only see one statement. How are we guaranteed we do the right thing in the NaN/inf cases in the DOUBLE array case?

[Yusuke Suzuki]

Comment on attachment 350087 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=350087&action=review

>> Source/JavaScriptCore/runtime/ArrayPrototype.cpp:1204
>> +                    RETURN_IF_EXCEPTION(scope, encodedJSValue());
> 
> nit: I think you can just use "{ }" instead of "encodedJSValue()"

Fixed.

>> Source/JavaScriptCore/runtime/MathCommon.h:190
>> +    // Note: while this behavior is undefined for NaN and inf, the subsequent statement will catch these cases.
> 
> I'm still super confused about this comment. What "subsequent" statement are we talking about here? I only see one statement. How are we guaranteed we do the right thing in the NaN/inf cases in the DOUBLE array case?

I've changed this comment to `Note: strictly speaking this is an undefined behavior.`

[Yusuke Suzuki]

Created attachment 350165 [details]
Patch

[Yusuke Suzuki]

Committed r236240: <https://trac.webkit.org/changeset/236240>

[Radar WebKit Bug Importer]

<rdar://problem/44629552>