1351913 - Optimize ReservedWord searching

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Shu-yu Guo [:shu]]

Bug 1336783 caused a regression in octane-codeload that I think is due to reserved word handling being slow.

(For completeness: at first I thought it might be the extra TokenKind range checking that goes on. I hacked TokenKind to be tagged instead of ranged instead and use bitwise & to check the TokenKind categories. This had no impact on the benchmark.)

Here're things to try to optimize reserved word handling:

1. Currently we parse fully parse an identifier, then check if it's a reserved word. We could check if the next token is a reserved word first by checking the next N characters in the userbuf directly. E.g., |if (end - userbuf >= 2 && userbuf[0] == 'i' && userbuf[1] == 'f' && !isIdentPart(userbuf+2))|.

2. Related to 1 above, sometimes we parse the reserved word, then convert it to an identifier, then re-check later (with more context) if that identifier is an allowed or disallowed reserved word. The last check incurs another search, we shouldn't do that.

3. Weight the search for more common reserved words first.

4. Vectorize the searching by checking multiple characters at once, by casting to a uint32 or 64 or something.

Comment 1

[Jeff Walden [:Waldo]]

#4 will violate strict aliasing rules.  Compilers should be intelligent enough to optimize comparisons of sequences of characters to that level, in any event.

Comment 2

[Shu-yu Guo [:shu]]

Bummer, 1 didn't pan out. Peeking for a reserved word when there's enough space left in userbuf actually resulted in a tiny regression.

Gonna try 2 next.

Comment 3

[Shu-yu Guo [:shu]]

Attachment: Hacky PeekReservedWord

This actually resulted in a small regression.

Comment 4

[André Bargull [:anba]]

Attachment: bug1351913-reduce-findreservedword-calls.patch

checkLabelOrIdentifierReference() called FindReservedWord() multiple times (through IsKeyword, IsReservedWordLiteral, IsFutureReservedWord, and IsStrictReservedWord). So as a first step, I replaced these calls with the new ReservedWordTokenKind function which returns a TokenKind value. This allows us to reduce the calls to FindReservedWord() and to reorder the validation checks based on their likelihood (e.g. TOK_NAME is the most common case, so we want to check this case first). 

When checkLabelOrIdentifierReference() is called from either labelOrIdentifierReference() or bindingIdentifier(), we can reuse the token kind information from the token stream and pass it directly to checkLabelOrIdentifierReference(). This avoids one additional call to FindReservedWord(). We only need to ensure the name doesn't contain escape sequences, so we still detect syntax errors like |var c\u0061tch;|.

And two minor improvements:
- In isValidStrictBinding(), we effectively call FindReservedWord() every time through IsStrictReservedWord(). So let's call FindReservedWord() (through the new ReservedWordTokenKind function) first, that way we can improve the TOK_NAME case.
- Remove a bit of rooting where not necessary or it can easily be avoided, for example in checkBindingIdentifier() by handling the |arguments| and |eval| cases before calling checkLabelOrIdentifierReference().

I think we could get another minor improvement if it was possible to remove the rooting in labelOrIdentifierReference() and bindingIdentifier(). But I guess checkLabelOrIdentifierReference() can invoke GC when "extraWarnings" without "werror" is enabled, so the rooting is actually necessary here. :-(

Comment 5

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=1d784d4c48b8adeec67f1b39d380997dde564be1

Comment 6

[Shu-yu Guo [:shu]]

Comment on attachment 8859169 [details] [diff] [review]
bug1351913-reduce-findreservedword-calls.patch

Review of attachment 8859169 [details] [diff] [review]:
-----------------------------------------------------------------

This patch is awesome.

::: js/src/frontend/TokenStream.h
@@ +307,5 @@
>  
> +    bool currentNameHasEscapes() const {
> +        if (isCurrentTokenType(TOK_NAME)) {
> +            TokenPos pos = currentToken().pos;
> +            return (pos.end - pos.begin) != currentToken().name()->length();

Ah, clever!

Comment 7

[André Bargull [:anba]]

checkin-needed for "bug1351913-reduce-findreservedword-calls.patch" only.

Comment 8

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3c9dcaac0b9f
Reduce calls to FindReservedWord when checking for forbidden identifiers during parsing. r=shu

Comment 9

[André Bargull [:anba]]

Attachment: bug1351913-validate-function-names.patch

A small improvement which should allow us to skip another call to FindReservedWord:
We only need to call checkBindingIdentifier when we transitioned to strict mode. In all other cases the caller already validated the function name is a valid BindingIdentifier in the current context. And we can remove the rooting for the function name, seems like I forgot to apply this change in the other patch.

Comment 10

[André Bargull [:anba]]

With the new patch applied, there are only four places left where we reparse an identifier:
- when the identifier has escape sequences
- when we validate parameter and function names after transitioning to strict-mode (in functionFormalParametersAndBody() and hasValidSimpleStrictParameterNames())
- when validating local export names in checkLocalExportName()
- and when we validate destructuring patterns in checkDestructuringName().

The last case should probably be improved, the other ones are most likely not common enough to worry about.

Comment 11

[Shu-yu Guo [:shu]]

Comment on attachment 8859543 [details] [diff] [review]
bug1351913-validate-function-names.patch

Review of attachment 8859543 [details] [diff] [review]:
-----------------------------------------------------------------

Nice.

Comment 12

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/3c9dcaac0b9f

Comment 13

[André Bargull [:anba]]

Attachment: bug1351913-validate-function-names.patch

Update bug1351913-validate-function-names.patch to apply on inbound, carrying r+ from shu.

Comment 14

[André Bargull [:anba]]

Try: https://treeherder.mozilla.org/#/jobs?repo=try&revision=b100fbc4609b248bd8cd32c53c416063c8bbf977

Comment 15

[André Bargull [:anba]]

And checkin-needed for "bug1351913-validate-function-names.patch".

Comment 16

[André Bargull [:anba]]

(In reply to André Bargull from comment #10)
> With the new patch applied, there are only four places left where we reparse
> an identifier:
> ...
> - and when we validate destructuring patterns in checkDestructuringName().
> 
> The last case should probably be improved, the other ones are most likely
> not common enough to worry about.

See bug 1303703.

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/mozilla-inbound/rev/3e2f102ce3b2
Avoid redundant call to FindReservedWord when validating function names. r=shu

Comment 18

[Wes Kocher (:KWierso) (Not reading bugmail; email directly if needed)]

https://hg.mozilla.org/mozilla-central/rev/3e2f102ce3b2

Comment 19

[André Bargull [:anba]]

Shu, do you think there's still more work to do for this bug? If yes, I'd unassign myself, so someone else can take up this bug. If no, we can close this bug.

Comment 20

[Shu-yu Guo [:shu]]

(In reply to André Bargull from comment #19)
> Shu, do you think there's still more work to do for this bug? If yes, I'd
> unassign myself, so someone else can take up this bug. If no, we can close
> this bug.

Nope, I'm quite happy with the patches you've already done. Closing.

Comment 21

[Firefox Bug Husbandry Bot]

Removing leave-open keyword from resolved bugs, per :sylvestre.