Closed Bug 1779807 Opened 2 months ago Closed 2 months ago

Array.prototype.includes should be SIMD-optimized

Categories

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

enhancement

Tracking

()

RESOLVED FIXED
105 Branch
Tracking Status
firefox105 --- fixed

People

(Reporter: dthayer, Assigned: dthayer)

References

(Blocks 1 open bug, Regressed 1 open bug)

Details

Attachments

(4 files)

See bug 1776013 - similar justification here.

Blocks: jsperf
Severity: -- → N/A
Priority: -- → P3
Assignee: nobody → dothayer
Status: NEW → ASSIGNED

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.

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

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

Pushed by dothayer@mozilla.com:
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
Flags: needinfo?(dothayer)

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

Pushed by dothayer@mozilla.com:
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

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?

Flags: needinfo?(dothayer)

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

You need to log in before you can comment on or make changes to this bug.