New issue
Advanced search Search tips
Note: Color blocks (like or ) mean that a user may not be available. Tooltip shows the reason.

Issue 7092 link

Starred by 1 user

Issue metadata

Status: Available
Owner:
Vacation until after Christmas
Cc:
Components:
HW: All
NextAction: ----
OS: All
Priority: 2
Type: FeatureRequest

Blocking:
issue 6936



Sign in to add a comment

High overhead of String.prototype.charCodeAt in typescript test

Project Member Reported by bmeu...@chromium.org, Nov 17 2017

Issue description

In the typescript test of the web-tooling-benchmark we spend like 4% of the time in the general String.prototype.charCodeAt builtin. This doesn't look right, especially since the majority of these calls come from optimized code, where we should instead call to the more efficient StringCharCodeAt builtin directly. The majority of the calls come from the scan and the computeLineStarts function. Let's consider scan:

===========================================================================
function scan() {
    startPos = pos;
    hasExtendedUnicodeEscape = false;
    precedingLineBreak = false;
    tokenIsUnterminated = false;
    numericLiteralFlags = 0;
    while (true) {
        tokenPos = pos;
        if (pos >= end) {
            return token = 1 /* EndOfFileToken */ ;
        }
        var ch = text.charCodeAt(pos);
    ....
}
============================================================================

For the JSBuiltinReducer to be effective we need to know that text is a String and pos is a Signed32 value. Unfortunately TurboFan doesn't know anything about pos, since it's on the function context and not constant. So the inlining fails. Nevertheless we could speculatively assume that the pos is an integer (Crankshaft used to do this, but without a safety net). We could introduce a global proctector cell that get's invalidated if someone passes a non-string receiver to String.prototype.charCodeAt or the position parameter is not an integer in the valid range for the operation. Assuming the protector is intact, then the JSCallReducer could replace 

  result = JSCall[String.prototype.charCodeAt](receiver, position)

nodes with

  receiver = CheckString(receiver)
  length = LoadField[String::length](receiver)
  position = CheckBounds(position, length)
  result = StringCharCodeAt(receiver, position)

which has the additional advantage that we don't pollute the propagated type (in the Typer phase that runs afterwards) with NaN. That's why this early optimization should be inside the JSCallReducer.

We should probably do the same for String.prototype.charAt, probably using the same protector cell.

In addition the general implementation of CSA::StringCharCodeAt doesn't seem to be ideal. We perform a couple of checks before we get to the common case. I think this would benefit from having a single loop, which dispatches on the instance type, such that for sequential strings there are max. of two checks before we get to the character instead of checking for all other kinds of strings first.

Besides the concrete typescript case we also see this quite high in the profile in other parsing workloads, and also often in various Node.js frontends.

So action items here:

 1. Prototype the TurboFan lowerings with the protector cell.

 2. Improve the general performance of StringCharCodeAt in the CSA.

 3. Experiment with inlining StringCharCodeAt inside of TurboFan in the EffectControlLinearizer, like Crankshaft used to do.
 
typescript-charCodeAt.png
301 KB View Download
typescript.json
9.7 MB View Download
wtb-typescript.js
8.2 MB View Download
"We perform a couple of checks before we get to the common case. I think this would benefit from having a single loop, which dispatches on the instance type, such that for sequential strings there are max. of two checks before we get to the character instead of checking for all other kinds of strings first."

For sequential one-byte input strings, I see three ops we could save in CSA::StringCharCodeAt:

* IntPtrAdd(index, to_direct.offset()), offset is always 0 in this case.
* The branch on is_external, since we know it's not.
* The one-byte instance type check + corresponding branch.

I assume seq/one-byte is what you meant by common case?
Project Member

Comment 2 by bugdroid1@chromium.org, Dec 29 2017

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

commit 807fc14485a8449a18ca165650336bcdaf7725f4
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Fri Dec 29 10:23:56 2017

[Turbofan] Add benchmark for String.prototype.charCodeAt

This also fixes benchmark scores for String.prototype.indexOf

Bug:  v8:7127 , v8:7092
Change-Id: Iee0f9689feb5923b300e253c267a6f32ffd4da20
Reviewed-on: https://chromium-review.googlesource.com/846739
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Sigurd Schneider <sigurds@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50316}
[modify] https://crrev.com/807fc14485a8449a18ca165650336bcdaf7725f4/test/js-perf-test/Strings/string-indexof.js

Project Member

Comment 3 by bugdroid1@chromium.org, Dec 29 2017

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

commit f22287b1f3e54b6036ad08b82fa5511dea73ae22
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Fri Dec 29 15:26:51 2017

[turbofan] Add benchmarks for String.prototype.charCodeAt to JSTests.json

Bug:  v8:7127 , v8:7092
Change-Id: Ib79c1cf5e65632b8701528799fe7df1d5407ad59
Reviewed-on: https://chromium-review.googlesource.com/846766
Commit-Queue: Michael Stanton <mvstanton@chromium.org>
Reviewed-by: Michael Stanton <mvstanton@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50322}
[modify] https://crrev.com/f22287b1f3e54b6036ad08b82fa5511dea73ae22/test/js-perf-test/JSTests.json

Project Member

Comment 4 by bugdroid1@chromium.org, Jan 3 2018

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

commit e683f33db1ee840b7a0310cff80bb1897d532119
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Wed Jan 03 14:15:02 2018

[turbofan] Move String.prototype.{charAt,CharCodeAt} to call reducer

This should improve performance in cases where receiver or argument types
are unknown.

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

Project Member

Comment 5 by bugdroid1@chromium.org, Jan 22 2018

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

commit efc3f5ff5abe095bd86643f9493ca9a91b16ebff
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Mon Jan 22 14:49:42 2018

[turbofan] Refactor fast-path of String.p.charAt/charCodeAt/codePointAt

Bug:  chromium:800594 , v8:7092,  v8:7270 ,  v8:7270 
Change-Id: I30b69b51f793030c6f8a031a88d2dbb26a79d2bf
Reviewed-on: https://chromium-review.googlesource.com/859780
Commit-Queue: Sigurd Schneider <sigurds@chromium.org>
Reviewed-by: Jaroslav Sevcik <jarin@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50762}
[modify] https://crrev.com/efc3f5ff5abe095bd86643f9493ca9a91b16ebff/src/compiler/js-call-reducer.cc
[modify] https://crrev.com/efc3f5ff5abe095bd86643f9493ca9a91b16ebff/src/compiler/js-call-reducer.h
[modify] https://crrev.com/efc3f5ff5abe095bd86643f9493ca9a91b16ebff/test/mjsunit/constant-folding-2.js

Project Member

Comment 6 by bugdroid1@chromium.org, Jan 30 2018

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

commit 6d36bae42c7c866e8bc6de936ee4979c1a2afb2d
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Tue Jan 30 05:10:53 2018

[js-perf-tests] Improve string benchmarks

Add inbounds benchmark for String.p.charCodeAt
and add in and out of bounds benchmarks for
String.p.codePointAt.

Bug: v8:7092,  v8:7326 , chromium:806758
Change-Id: I48065627bd79d8fb24e55b2f6dce590e7adbbd6e
Reviewed-on: https://chromium-review.googlesource.com/891858
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#50942}
[modify] https://crrev.com/6d36bae42c7c866e8bc6de936ee4979c1a2afb2d/test/js-perf-test/Strings/string-indexof.js

Project Member

Comment 7 by bugdroid1@chromium.org, Jan 31 2018

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

commit 51c631563895ff9e2b2e73c1f09116f92256a4c6
Author: Sigurd Schneider <sigurds@chromium.org>
Date: Wed Jan 31 17:34:06 2018

[js-perf-tests] Hook up new benchmarks for String.p.charCodeAt

Bug: v8:7092,  v8:7326 , chromium:806758
Change-Id: Id8a3bc2455875af9dfdc01619d8217e033099e7e
Reviewed-on: https://chromium-review.googlesource.com/895690
Commit-Queue: Benedikt Meurer <bmeurer@chromium.org>
Reviewed-by: Benedikt Meurer <bmeurer@chromium.org>
Cr-Commit-Position: refs/heads/master@{#51006}
[modify] https://crrev.com/51c631563895ff9e2b2e73c1f09116f92256a4c6/test/js-perf-test/JSTests.json
[modify] https://crrev.com/51c631563895ff9e2b2e73c1f09116f92256a4c6/test/js-perf-test/Strings/string-indexof.js

Cc: sigurds@chromium.org
Can this be closed?

Sign in to add a comment