1779807 - Array.prototype.includes should be SIMD-optimized

Status: RESOLVED FIXED

(Core :: JavaScript: Standard Library, enhancement, P3)

Description

[Alex Thayer [:alexical] (she/her)]

See bug 1776013 - similar justification here.

Comment 1

[Alex Thayer [:alexical] (she/her)]

Attachment: Bug 1779807 - Support AVX2 for SIMD memchr r?iain

This showed a modest improvement in the geomean of my benchmarking, but
importantly it showed a consistent and relatively strong improvement across
all of the cases which I would guess are more realistic. Notably this change
makes it perform better at iteratively searching for the next occurrence of X
in the HTML of a large web page.

Comment 2

[Alex Thayer [:alexical] (she/her)]

Attachment: Bug 1779807 - Implement memchr64 in AVX2 r?iain

This only makes sense for AVX2, because widening it from a 64-bit comparison
to a 128-bit comparison is hardly worth it, and there are gaps in the SSE2
instruction set (missing _mm_cmpeq_epi64, which is introduced in SSE4.1) that
would require us to compensate and probably take a sizeable perf hit.

Depends on D152296

Comment 3

[Alex Thayer [:alexical] (she/her)]

Attachment: Bug 1779807 - Consume SIMD::memchr64 for array includes/indexof r?iain

This improved the time for a contrived benchmark. I don't know if we want
to invest more time into benchmarking - I feel pretty strongly that this will
be an improvement across most use cases, just judging from the more in-depth
benchmarking of the string functions. The benchmark I did was basically as
follows:

make N arrays
make N objects
for i,j in 0..N,0..N
if (hash(i,j) % K == 0)
arrays[i].push(objects[j])

start performance timer
for i,j in 0..N,0..N
if arrays[i].includes(objects[j])
matches++

report matches and performance timings

And our times were basically equal for small N, and up to 3 times faster
for large N - so, basically what we would hope for.

Depends on D152297

Comment 4

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/faa38e8360b1
Support AVX2 for SIMD memchr r=iain
https://hg.mozilla.org/integration/autoland/rev/f11ef6602f59
Implement memchr64 in AVX2 r=iain
https://hg.mozilla.org/integration/autoland/rev/68e92976dc0f
Consume SIMD::memchr64 for array includes/indexof r=iain

Comment 5

[Sandor Molnar[:smolnar]]

Backed out for causing SM build failures

Backout link: https://hg.mozilla.org/integration/autoland/rev/ab2e29952218c79fa539ac733583bd8c8d8bcfd9

Push with failures

Failure log

Comment 6

[Alex Thayer [:alexical] (she/her)]

Attachment: Bug 1779807 - Split AVX2 code into its own compilation unit r?iain

I split this out into its own commit because it's a bit awkward to go back and
shuffle the old code around. If you'd like me to apply it to the history
though, just let me know.

This patch just moves all of the AVX2 code out from SIMD.cpp into SIMD_avx2.cpp
and removes the -mavx2 flag when compiling SIMD.cpp. On try this removes the
failure on M1 hardware when running the x64 binary.

Depends on D152298

Comment 7

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a33eed5e3b07
Support AVX2 for SIMD memchr r=iain
https://hg.mozilla.org/integration/autoland/rev/1a6105fe6fad
Implement memchr64 in AVX2 r=iain
https://hg.mozilla.org/integration/autoland/rev/60cacdcfafa3
Consume SIMD::memchr64 for array includes/indexof r=iain
https://hg.mozilla.org/integration/autoland/rev/51823a43cd60
Split AVX2 code into its own compilation unit r=iain

Comment 8

[Atila Butkovits]

https://hg.mozilla.org/mozilla-central/rev/a33eed5e3b07
https://hg.mozilla.org/mozilla-central/rev/1a6105fe6fad
https://hg.mozilla.org/mozilla-central/rev/60cacdcfafa3
https://hg.mozilla.org/mozilla-central/rev/51823a43cd60

Comment 9

[Alex Thayer [:alexical] (she/her)]

I believe this won maybe 10% or so on the Jetstream 2 A* test on AWFY:

https://arewefastyet.com/win10/benchmarks/raptor-desktop-jetstream2?numDays=60

see ai-astar-Average and friends. Looks like the test has a reasonably hot usage of Array.prototype.indexOf?

Edit: It also seems like it may have improved things for the "ML" benchmark?

Comment 10

[Martin Stránský [:stransky] (ni? me)]

This causes a regression on i686 / GCC builds - Bug 1792158.