Array.prototype.find should be inlined and should perform better than a for loop + break |
||||||
Issue descriptionUserAgent: Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/62.0.3202.94 Safari/537.36 Steps to reproduce the problem: example: https://github.com/Reactive-Extensions/RxJS/pull/1532/files What is the expected behavior? The performance of .find is faster than a for loop What went wrong? The for loop performs better. Did this work before? N/A Chrome version: 62.0.3202.94 Channel: stable OS Version: Flash Version:
,
Dec 1 2017
I'll check this next week and see that we get this fixed.
,
Dec 4 2017
FYI there's a CL in-flight to move find/findIndex to CSA: https://crrev.com/c/804704
,
Dec 5 2017
Ok, similar to https://bugs.chromium.org/p/v8/issues/detail?id=7165 the plan of action is: 1. Add performance test to js-perf-tests. 2. Port the Array.prototype.find builtin to CSA. 3. Inline the builtin into TurboFan.
,
Dec 5 2017
,
Dec 5 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/99b5f699abda3e470e0d22a8d48f6bd4a9976895 commit 99b5f699abda3e470e0d22a8d48f6bd4a9976895 Author: peterwmwong <peter.wm.wong@gmail.com> Date: Tue Dec 05 07:23:13 2017 [builtins] Port Array.p.{find,findIndex} to CSA - Removes JS implementation and InnerArrayFind/InnerArrayFindIndex - Adds TFJ, with TFS for slow continuation path Some quick benchmarks show ~2x improvement for unoptimized code and up to 16% improvement against optimized code (diminishes with larger arrays as iterating dominates). https://github.com/peterwmwong/v8-perf/blob/master/array-find-findIndex/README.md Bug: chromium:791045 , v8:1956, v8:5049, v8:7165 Change-Id: Ie16252ed495bbd91fe548b16d5ef6764de791a50 Reviewed-on: https://chromium-review.googlesource.com/804704 Reviewed-by: Jakob Gruber <jgruber@chromium.org> Commit-Queue: Jakob Gruber <jgruber@chromium.org> Cr-Commit-Position: refs/heads/master@{#49851} [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/src/bootstrapper.cc [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/src/builtins/builtins-array-gen.cc [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/src/builtins/builtins-definitions.h [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/src/debug/debug-evaluate.cc [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/src/js/array.js [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/test/mjsunit/array-iteration.js [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/test/mjsunit/es6/array-find.js [modify] https://crrev.com/99b5f699abda3e470e0d22a8d48f6bd4a9976895/test/mjsunit/es6/array-findindex.js
,
Dec 5 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/e0e1a5e56456682fa73f136267f2ff873218ef46 commit e0e1a5e56456682fa73f136267f2ff873218ef46 Author: peterwmwong <peter.wm.wong@gmail.com> Date: Tue Dec 05 13:43:51 2017 [js-perf-test] Add Array.p.find microbenchmarks Bug: chromium:791045 , v8:1956, v8:7165 Change-Id: I5c5cf74376f61f71591a8c67fbc9d1584a2b9128 Reviewed-on: https://chromium-review.googlesource.com/807748 Commit-Queue: Jakob Gruber <jgruber@chromium.org> Reviewed-by: Benedikt Meurer <bmeurer@chromium.org> Reviewed-by: Jakob Gruber <jgruber@chromium.org> Cr-Commit-Position: refs/heads/master@{#49864} [add] https://crrev.com/e0e1a5e56456682fa73f136267f2ff873218ef46/test/js-perf-test/Array/find.js [modify] https://crrev.com/e0e1a5e56456682fa73f136267f2ff873218ef46/test/js-perf-test/Array/run.js [modify] https://crrev.com/e0e1a5e56456682fa73f136267f2ff873218ef46/test/js-perf-test/JSTests.json
,
Dec 6 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/1d17438905a00cc89cbc64b8aacd4a68c92a826a commit 1d17438905a00cc89cbc64b8aacd4a68c92a826a Author: peterwmwong <peter.wm.wong@gmail.com> Date: Wed Dec 06 15:57:05 2017 [js-perf-test] Add Array.p.findIndex microbenchmarks Bug: chromium:791045 , v8:1956, v8:7165 Change-Id: I03f26bbbe65217cedf663af59ef5eb63a5dcf039 Reviewed-on: https://chromium-review.googlesource.com/810039 Commit-Queue: Jakob Gruber <jgruber@chromium.org> Reviewed-by: Jakob Gruber <jgruber@chromium.org> Cr-Commit-Position: refs/heads/master@{#49899} [add] https://crrev.com/1d17438905a00cc89cbc64b8aacd4a68c92a826a/test/js-perf-test/Array/find-index.js [modify] https://crrev.com/1d17438905a00cc89cbc64b8aacd4a68c92a826a/test/js-perf-test/Array/find.js [modify] https://crrev.com/1d17438905a00cc89cbc64b8aacd4a68c92a826a/test/js-perf-test/Array/run.js [modify] https://crrev.com/1d17438905a00cc89cbc64b8aacd4a68c92a826a/test/js-perf-test/JSTests.json
,
Dec 7 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/12afb22458663c64ef90179447b895fb00a59f92 commit 12afb22458663c64ef90179447b895fb00a59f92 Author: Sergiy Byelozyorov <sergiyb@chromium.org> Date: Thu Dec 07 13:49:46 2017 [test] Add find-index.js to the list of resources for the test R=jgruber@chromium.org Bug: chromium:791045 , v8:1956, v8:7165 Change-Id: I58ba09248824f0309a3d37afa3e59bdea7c5f1f1 Reviewed-on: https://chromium-review.googlesource.com/813914 Reviewed-by: Jakob Gruber <jgruber@chromium.org> Commit-Queue: Sergiy Byelozyorov <sergiyb@chromium.org> Cr-Commit-Position: refs/heads/master@{#49933} [modify] https://crrev.com/12afb22458663c64ef90179447b895fb00a59f92/test/js-perf-test/JSTests.json
,
Dec 11 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/a837ef8a9a43b9b2f05818e54c5cb929b4d20986 commit a837ef8a9a43b9b2f05818e54c5cb929b4d20986 Author: peterwmwong <peter.wm.wong@gmail.com> Date: Mon Dec 11 11:16:09 2017 [turbofan] Array.prototype.find inlining. Support inlining Array.prototype.find in Turbofan. Quick benchmarks show >2x improvement for Smi and Double packed arrays: https://github.com/peterwmwong/v8-perf/blob/master/array-find-tf/README.md Bug: chromium:791045 , v8:1956 Change-Id: I9a6882be9bc3e1e84df372a24bd0f85897cf92a0 Reviewed-on: https://chromium-review.googlesource.com/818193 Reviewed-by: Benedikt Meurer <bmeurer@chromium.org> Reviewed-by: Michael Stanton <mvstanton@chromium.org> Reviewed-by: Jakob Gruber <jgruber@chromium.org> Commit-Queue: Jakob Gruber <jgruber@chromium.org> Cr-Commit-Position: refs/heads/master@{#49987} [modify] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/src/builtins/builtins-array-gen.cc [modify] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/src/builtins/builtins-definitions.h [modify] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/src/builtins/builtins.cc [modify] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/src/compiler/js-call-reducer.cc [modify] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/src/compiler/js-call-reducer.h [add] https://crrev.com/a837ef8a9a43b9b2f05818e54c5cb929b4d20986/test/mjsunit/optimized-array-find.js
,
Dec 11 2017
Setting NextAction to verify perf impact of the CL series ending at #10. Peter, any idea how we do now on the example given in #0?
,
Dec 11 2017
Unfortunately, it seems there's still work to be done when handling arrays of objects. I'm not seeing the same improvement achieved with arrays of SMIs and Doubles. I'll dig into turbolizer/print-opt-code to see what's up. Currently, we see >2x improvement for arrays of SMIs and Doubles (depending on array size). The following shows results comparing before and after CSA/TF improvements: https://gist.github.com/peterwmwong/6898256bcb206fdde10108b054447d27
,
Dec 12 2017
Well, good news! Writing a benchmark that's a little closer the linked Reactive-Extensions issue shows a ~3x improvement. https://gist.github.com/peterwmwong/5876853a5f2432fb1688d9630c84c722 Compared against a manual loop, we're no longer 6x slower, but there's still a 2x gap to improve upon.
,
Dec 13 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/e2ce2e0aff862686379db8cf66eab45242d580d4 commit e2ce2e0aff862686379db8cf66eab45242d580d4 Author: peterwmwong <peter.wm.wong@gmail.com> Date: Wed Dec 13 05:38:17 2017 [turbofan] Fix Array.p.find handling of holes in double elements Bug: chromium:791045 , v8:1956 Change-Id: I1400fc95b78e0f4771867d136377b14aed5bd4f4 Reviewed-on: https://chromium-review.googlesource.com/819510 Reviewed-by: Michael Stanton <mvstanton@chromium.org> Reviewed-by: Jakob Gruber <jgruber@chromium.org> Reviewed-by: Benedikt Meurer <bmeurer@chromium.org> Commit-Queue: Benedikt Meurer <bmeurer@chromium.org> Cr-Commit-Position: refs/heads/master@{#50061} [modify] https://crrev.com/e2ce2e0aff862686379db8cf66eab45242d580d4/src/compiler/js-call-reducer.cc [modify] https://crrev.com/e2ce2e0aff862686379db8cf66eab45242d580d4/test/mjsunit/optimized-array-find.js
,
Dec 13 2017
I took a look at the generated code and it uses doubles for the internal array index, which causes it to be a lot slower than the hand-written loop, which uses integers. I.e. for
============================================================
function foo(a) {
return a.find(x => false);
}
============================================================
we generate the loop as
============================================================
0x281795e4b088 28 488b4510 REX.W movq rax,[rbp+0x10]
0x281795e4b08c 2c a801 test al,0x1
0x281795e4b08e 2e 0f84a3000000 jz 0x281795e4b137 <+0xd7>
0x281795e4b094 34 48bb512758a286320000 REX.W movq rbx,0x3286a2582751 ;; object: 0x3286a2582751 <Map(PACKED_SMI_ELEMENTS)>
0x281795e4b09e 3e 483958ff REX.W cmpq [rax-0x1],rbx
0x281795e4b0a2 42 0f8594000000 jnz 0x281795e4b13c <+0xdc>
0x281795e4b0a8 48 488b5017 REX.W movq rdx,[rax+0x17]
0x281795e4b0ac 4c 488bca REX.W movq rcx,rdx
0x281795e4b0af 4f 48c1e920 REX.W shrq rcx, 32
0x281795e4b0b3 53 c5f957c0 vxorpd xmm0,xmm0,xmm0
0x281795e4b0b7 57 c5fb2ac1 vcvtlsi2sd xmm0,xmm0,rcx
0x281795e4b0bb 5b c5f157c9 vxorpd xmm1,xmm1,xmm1
0x281795e4b0bf 5f 90 nop
-- B4 start (loop up to 6) --
0x281795e4b0c0 60 c5f92ec1 vucomisd xmm0,xmm1
0x281795e4b0c4 64 0f8661000000 jna 0x281795e4b12b <+0xcb>
-- B5 start (in loop 4) --
0x281795e4b0ca 6a 49ba000000000000f03f REX.W movq r10,0x3ff0000000000000
0x281795e4b0d4 74 c4c1f96ed2 vmovq xmm2,r10
0x281795e4b0d9 79 c5f358d2 vaddsd xmm2,xmm1,xmm2
0x281795e4b0dd 7d c5fb2cf1 vcvttsd2si rsi,xmm1
0x281795e4b0e1 81 c5e157db vxorpd xmm3,xmm3,xmm3
0x281795e4b0e5 85 c5e32ade vcvtlsi2sd xmm3,xmm3,rsi
0x281795e4b0e9 89 483958ff REX.W cmpq [rax-0x1],rbx
0x281795e4b0ed 8d 0f854e000000 jnz 0x281795e4b141 <+0xe1>
0x281795e4b0f3 93 c5f92ed9 vucomisd xmm3,xmm1
0x281795e4b0f7 97 0f8a49000000 jpe 0x281795e4b146 <+0xe6>
0x281795e4b0fd 9d 0f8543000000 jnz 0x281795e4b146 <+0xe6>
0x281795e4b103 a3 3bf1 cmpl rsi,rcx
0x281795e4b105 a5 0f8340000000 jnc 0x281795e4b14b <+0xeb>
0x281795e4b10b ab c5f928ca vmovapd xmm1,xmm2
0x281795e4b10f af ebaf jmp 0x281795e4b0c0 <+0x60>
-- B1 start (deferred) --
-- <not inlined:476> --
0x281795e4b111 b1 48bb20da0655db7f0000 REX.W movq rbx,0x7fdb5506da20
0x281795e4b11b bb 33c0 xorl rax,rax
0x281795e4b11d bd 488b75f8 REX.W movq rsi,[rbp-0x8]
0x281795e4b121 c1 e8fa91ebff call 0x281795d04320 ;; code: STUB, CEntryStub, minor: 8
0x281795e4b126 c6 e95dffffff jmp 0x281795e4b088 <+0x28>
-- B6 start (deferred) (deconstruct frame) --
-- <not inlined:510> --
0x281795e4b12b cb 498b45a0 REX.W movq rax,[r13-0x60]
0x281795e4b12f cf 488be5 REX.W movq rsp,rbp
0x281795e4b132 d2 5d pop rbp
0x281795e4b133 d3 c21000 ret 0x10
============================================================
so you can see we unnecessarily use doubles here. I'm currently checking the JSCallReducer code to fix this.
,
Dec 13 2017
The NextAction date has arrived: 2017-12-13
,
Dec 13 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/0b9036dcc96f38635cd9bcad63682d8ee7b61f3d commit 0b9036dcc96f38635cd9bcad63682d8ee7b61f3d Author: Benedikt Meurer <bmeurer@chromium.org> Date: Wed Dec 13 17:29:25 2017 [turbofan] Make Array#find use integers for the index. The k value passed to NumberAdd was outside the integer range, which meant it had to choose Double as the only valid representation. The other array builtins pass the result of CheckBounds here to specifically force the types into integer range, which allows the representation selection to pick Word32 instead of Float64 representation. Drive-by-fix: Pass kind to AccessBuilder::ForJSArrayLength() as well. Bug: chromium:791045 , v8:1956 Change-Id: I357e1ba0dc52be544e631e4d554ab772b9b4c9bb Reviewed-on: https://chromium-review.googlesource.com/823968 Reviewed-by: Jakob Gruber <jgruber@chromium.org> Commit-Queue: Benedikt Meurer <bmeurer@chromium.org> Cr-Commit-Position: refs/heads/master@{#50084} [modify] https://crrev.com/0b9036dcc96f38635cd9bcad63682d8ee7b61f3d/src/compiler/js-call-reducer.cc
,
Dec 14 2017
This is done on our side. Performance is within 10-25% of the for loop.
,
Dec 15 2017
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22 commit 61e2f270d84f53a9a65bbf1de45f98e7a05c9d22 Author: peterwmwong <peter.wm.wong@gmail.com> Date: Fri Dec 15 16:32:26 2017 [turbofan] Array.prototype.findIndex inlining. Support inlining Array.prototype.findIndex in Turbofan. Depending on array size, quick benchmarks show a >2x improvement: https://github.com/peterwmwong/v8-perf/blob/master/array-find-findIndex-tf/README.md Bug: chromium:791045 , v8:1956, v8:7165 Change-Id: I250554885f924c97b0072e09ee289713df5cbe63 Reviewed-on: https://chromium-review.googlesource.com/824382 Commit-Queue: Peter Wong <peter.wm.wong@gmail.com> Reviewed-by: Jakob Gruber <jgruber@chromium.org> Reviewed-by: Michael Stanton <mvstanton@chromium.org> Reviewed-by: Benedikt Meurer <bmeurer@chromium.org> Cr-Commit-Position: refs/heads/master@{#50133} [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/src/builtins/builtins-array-gen.cc [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/src/builtins/builtins-definitions.h [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/src/builtins/builtins.cc [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/src/compiler/js-call-reducer.cc [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/src/compiler/js-call-reducer.h [modify] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/test/mjsunit/optimized-array-find.js [add] https://crrev.com/61e2f270d84f53a9a65bbf1de45f98e7a05c9d22/test/mjsunit/optimized-array-findindex.js
,
Aug 22
The following revision refers to this bug: https://chromium.googlesource.com/v8/v8.git/+/11261f42064a28db59034335ad192ce5cc22ed7e commit 11261f42064a28db59034335ad192ce5cc22ed7e Author: Benedikt Meurer <bmeurer@chromium.org> Date: Wed Aug 22 19:23:31 2018 [turbofan] Support HOLEY_DOUBLE_ELEMENTS for Array#find() and findIndex(). This adds the missing support for HOLEY_DOUBLE_ELEMENTS to both `Array#find()` and `Array#findIndex()`. The implementation just deopts whenever it hits a double hole. In order to prevent deoptimization loops we add feedback to the CheckFloat64Hole operator, which also addresses the TODO in the `%ArrayIteratorPrototype%.next()` lowering. This provides a speed-up of up to 8x in microbenchmarks when using `Array#find()` or `Array#findIndex()` on HOLEY_DOUBLE_ELEMENTS arrays. Bug: chromium:791045 , v8:1956, v8:6587, v8:7165 , v8:8015 Change-Id: I1be22d3fcba56c676a81dc31a9042f8123ef3a55 Reviewed-on: https://chromium-review.googlesource.com/1183906 Reviewed-by: Sigurd Schneider <sigurds@chromium.org> Commit-Queue: Benedikt Meurer <bmeurer@chromium.org> Cr-Commit-Position: refs/heads/master@{#55321} [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/effect-control-linearizer.cc [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/js-call-reducer.cc [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/js-native-context-specialization.cc [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/simplified-lowering.cc [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/simplified-operator.cc [modify] https://crrev.com/11261f42064a28db59034335ad192ce5cc22ed7e/src/compiler/simplified-operator.h |
||||||
►
Sign in to add a comment |
||||||
Comment 1 by bmeu...@chromium.org
, Dec 1 2017Labels: Performance Arch-All OS-Android OS-Chrome OS-Fuchsia OS-iOS OS-Mac OS-Windows
Owner: bmeu...@chromium.org
Status: Assigned (was: Unconfirmed)