New issue
Advanced search Search tips
Starred by 1 user

Issue metadata

Status: Verified
Owner:
Closed: Jan 2018
Cc:
Components:
HW: All
NextAction: ----
OS: All
Priority: 3
Type: Bug

Blocked on:
issue 7127



Sign in to add a comment

JSBuiltinReducer::ReduceStringIndexOf: String type unknown if indexOf call is wrapped in function

Project Member Reported by jgruber@chromium.org, Apr 18 2017

Issue description

Version: ToT

I came across this while looking at a String.p.indexOf microbenchmark (attached).

JSBuiltinReducer::ReduceStringIndexOf [0] bails out on the 

if (search_string_type->Is(Type::String()) &&
        position_type->Is(Type::SignedSmall()))

check when the indexOf loop is wrapped in a function, causing at least a 5x increase in runtime (less is better):

out/release/d8 ~/bench-string-p-indexof-in-function.js -- aaaaaaaaaaaaaaaaaaaab a  // 1158.757
out/release/d8 ~/bench-string-p-indexof.js -- aaaaaaaaaaaaaaaaaaaab a  // 226.996

The difference can become much worse with other args:

out/release/d8 ~/bench-string-p-indexof-in-function.js -- aaaaaaaaaaaaaaaaaaaab ab  // 14226.949
out/release/d8 ~/bench-string-p-indexof.js -- aaaaaaaaaaaaaaaaaaaab ab  // 213.938

Looks to me like this happens because search_string_type cannot be inferred anymore. Is this expected behavior?

[0] https://cs.chromium.org/chromium/src/v8/src/compiler/js-builtin-reducer.cc?type=cs&q=js-builtin-+package:%5Echromium$&l=1882
 
bench-string-p-indexof.js
270 bytes View Download
bench-string-p-indexof-in-function.js
296 bytes View Download

Comment 1 by jarin@chromium.org, Apr 18 2017

Cc: jarin@chromium.org
Owner: bmeu...@chromium.org

Comment 2 by cbruni@chromium.org, Apr 18 2017

Cc: cbruni@chromium.org
Cc: mvstan...@chromium.org
Components: Runtime Compiler
Labels: Performance TurboFan
Status: Available (was: Assigned)
We currently don't have feedback on CallIC inputs. We just discussed a more complex CallIC today, that would be able to collect different feedback, i.e. String feedback on the searchString input.
In this example, lowering also results in omission of the (pure) StringIndexOf operator after the first ~10k loop iterations, while the non-lowered version performs 10^8 calls to the StringIndexOf builtin. That explains the huge runtime difference.
Blockedon: 7127
Cc: sigurds@chromium.org
Once we have the optimization guards we could speculatively assume that the inputs to String.prototype.indexOf are both strings (by inserting CheckString) and then learn via the deoptimization guard. This seems like a reasonable approach. We should also move the lowering to JSCallReducer in that case maybe.
Cc: -sigurds@chromium.org bmeu...@chromium.org
Labels: -Priority-2 Priority-3
Owner: sigurds@chromium.org
Sigurd, I'm assigning this to you, as it's follow-up work from the builtin optimization guards. It's not high priority and should be fairly straight-forward.
Project Member

Comment 8 by bugdroid1@chromium.org, Dec 19 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/5e18f849535b920da1f2194ea1b56e5ecaa3f3ea

commit 5e18f849535b920da1f2194ea1b56e5ecaa3f3ea
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Tue Dec 19 10:54:37 2017

[turbofan] Add benchmarks for String.indexOf

Bug:  v8:7127 ,  v8:6270 
Change-Id: Ic35a9b7a5145115736934b0c7de6ace26e9c0e51
Reviewed-on: https://chromium-review.googlesource.com/832966
Commit-Queue: Sigurd Schneider <sigurds@chromium.org>
Reviewed-by: Jakob Gruber <jgruber@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50191}
[modify] https://crrev.com/5e18f849535b920da1f2194ea1b56e5ecaa3f3ea/test/js-perf-test/JSTests.json
[modify] https://crrev.com/5e18f849535b920da1f2194ea1b56e5ecaa3f3ea/test/js-perf-test/Strings/run.js
[add] https://crrev.com/5e18f849535b920da1f2194ea1b56e5ecaa3f3ea/test/js-perf-test/Strings/string-indexof.js

Project Member

Comment 9 by bugdroid1@chromium.org, Dec 22 2017

The following revision refers to this bug:
  https://chromium.googlesource.com/v8/v8.git/+/b44f820559d6f691d68fc07165ceae3201ad0509

commit b44f820559d6f691d68fc07165ceae3201ad0509
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Fri Dec 22 08:13:47 2017

[turbofan] Move String.indexOf inlining to call reducer

This also adds speculative checks asserting that all arguments
are of the right types; each check disables speculation if it
fails.

Bug:  v8:7127 ,  v8:6270 
Change-Id: Ifcb8bc509b86c712f0fab50ef1caee0c3a289e86
Reviewed-on: https://chromium-review.googlesource.com/832449
Commit-Queue: Sigurd Schneider <sigurds@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50289}
[modify] https://crrev.com/b44f820559d6f691d68fc07165ceae3201ad0509/src/compiler/js-builtin-reducer.cc
[modify] https://crrev.com/b44f820559d6f691d68fc07165ceae3201ad0509/src/compiler/js-builtin-reducer.h
[modify] https://crrev.com/b44f820559d6f691d68fc07165ceae3201ad0509/src/compiler/js-call-reducer.cc
[modify] https://crrev.com/b44f820559d6f691d68fc07165ceae3201ad0509/src/compiler/js-call-reducer.h
[modify] https://crrev.com/b44f820559d6f691d68fc07165ceae3201ad0509/src/compiler/typer.cc

Status: Fixed (was: Available)
I just verified, this has been fixed. ToT shows:

out.gn/x64.release/d8 bench-string-p-indexof-in-function.js -- aaaaaaaaaaaaaaaaaaaab ab // 122.34799999999998
out.gn/x64.release/d8 bench-string-p-indexof.js -- aaaaaaaaaaaaaaaaaaaab ab // 304.869

Status: Verified (was: Fixed)
Very nice!

Sign in to add a comment