639420 - Speed up the scanner ten ways

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

Attachment: merged stack just for back-up purposes

I have a stack of patches that speeds up scanning by over 10%.  I'll put them up one by one with detailed measurements once bug 638034 is done.  For the moment, I've attached the union of patches.

Comment 1

[Nicholas Nethercote [inactive]]

(In reply to comment #0)
> 
> I have a stack of patches that speeds up scanning by over 10%.

Actually, it speeds up parse() -- which includes scanning and parsing -- by over 10%, so it really speeds up scanning itself by a lot more.  Also see bug 637549.

Comment 2

[Robert Sayre]

(In reply to comment #1)
> 
> Actually, it speeds up parse() -- which includes scanning and parsing -- by
> over 10%, so it really speeds up scanning itself by a lot more. 

woot!

Comment 3

[Nicholas Nethercote [inactive]]

First, here are the parsemark-njn (which is parsemark + kraken-imaging data)
results for all the patches.  In each case I've given the kraken-imaging
(which is number-heavy), zimbra-combined and parsemark-njn overall
instruction counts.

  changeset           imaging-kraken   zimbra-combined  parsemark-njn
  ---------           --------------   ---------------  -------------
  63054:ccc55e56efc9  788.5M           433.5M           2440.7M
  avoid-tokenbuf:     770.2M (1.024x)  433.0M (1.001x)  2420.1M (1.009x)
  split-dec-hex-oct   720.1M (1.095x)  433.3M (1.001x)  2370.3M (1.030x)
  hasFracOrExp        650.4M (1.212x)  432.3M (1.003x)  2296.0M (1.063x)
  getCharIgnoreEOL    645.3M (1.222x)  432.2M (1.003x)  2290.0M (1.066x)
  no-TOLOWER          636.6M (1.239x)  432.0M (1.004x)  2280.1M (1.070x)
  JS_ISSPACE2         633.6M (1.245x)  431.3M (1.005x)  2274.1M (1.073x)
  JS_ISIDSTART        613.0M (1.286x)  415.8M (1.043x)  2201.8M (1.108x)
  oneCharTokens       608.4M (1.296x)  417.7M (1.038x)  2200.4M (1.109x)
  avoid-tokenbuf2     606.2M (1.301x)  399.4M (1.099x)  2146.0M (1.146x)
  no-TSF_ERROR-check  594.2M (1.327x)  390.0M (1.111x)  2100.5M (1.162x)

Timing-wise the gains are slightly smaller:  I see 1.24x on imaging-kraken,
1.09x on zimbra-combined, and 1.12x overall.


Here's the description of all the patches, coming shortly.

1. avoid-tokenbuf: when tokenizing a number, don't copy the number into
tokenbuf, just do the conversion directly from userbuf.  Safe because
numbers never contain escape sequences.

2. split-dec-hex-oct: split up number parsing into three parts: decimal, hex,
and octal.  Make things faster by avoiding lots of repeated radix checks.
Also is easier to read IMO, though the code is slightly longer.

3. hasFracOrExp: use GetPrefixInteger() to convert decimals that don't have a
fraction or exponent;  it's much faster than js_strtod().

4. getCharIgnoreEOL: replace uses of getChar() in number scanning with
getCharIgnoreEOL(), which is faster.

5. no-TOLOWER: don't use JS_TOLOWER for the exponent 'e' or 'E';  it's horribly
slow.

6. JS_ISSPACE2: add a lookup table for 7-bit whitespace chars.  Also introduces
'____' as a local synonym for 'false' in char predicate lookup tables, which
make it easier to see if they are correct.  (I did this in response to
getting an entry wrong in one of these tables.)

7. JS_ISIDSTART: add lookup tables for 7-bit identifier chars.

8. oneCharTokens: add a lookup table for tokens that are always one character
long, and try to match them early on because they're very common.  [Nb: The
numbers above for this patch look bad, I think it's due to noise (eg.
variations in register spilling) because it's clearly a win when you look at
the code.  Also, if I undo it at the end of the patch perf gets worse by
about 20M instructions.]

9. avoid-tokenbuf2: when scanning identifiers, make the case where the
identifier doesn't have any escape sequences (which is very common) faster
by atomizing directly from userbuf.  If an escape sequence is found, rescan
the string in order to copy it to tokenbuf.  Also, use getCharIgnoreEOL()
instead of getChar() in both cases.  Also, check for JS_ISIDENT before '\\'
inside identifiers.

10. no-TSF_ERROR-check: the TSF_ERROR check never succeeds, AFAICT.  This
patch changes it to an assertion, and passes jsregtests.  If that's not
appropriate, moving the check into getToken() is almost as good -- the big
wins here are from getToken() being inlined more often.

Comment 4

[Nicholas Nethercote [inactive]]

Attachment: patch 1 (against TM 63063:87dcf64586a7)

Comment 5

[Nicholas Nethercote [inactive]]

Attachment: patch 2

Comment 6

[Nicholas Nethercote [inactive]]

Attachment: patch 3

Comment 7

[Nicholas Nethercote [inactive]]

Attachment: patch 4

Comment 8

[Nicholas Nethercote [inactive]]

Attachment: patch 5

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: patch 6

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: patch 7

Comment 11

[Nicholas Nethercote [inactive]]

Attachment: patch 8

Comment 12

[Nicholas Nethercote [inactive]]

Attachment: patch 9

Comment 13

[Nicholas Nethercote [inactive]]

Attachment: patch 10

Comment 14

[Brendan Eich [:brendan]]

> 10. no-TSF_ERROR-check: the TSF_ERROR check never succeeds, AFAICT.  This

See bug 636224 comment 3.

/be

Comment 15

[Nicholas Nethercote [inactive]]

(In reply to comment #14)
> > 10. no-TSF_ERROR-check: the TSF_ERROR check never succeeds, AFAICT.  This
> 
> See bug 636224 comment 3.

That comment is... dense.  IIUC, it's agreeing with my observation, and so this patch is valid.  Is that right?

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #15)
> (In reply to comment #14)
> > > 10. no-TSF_ERROR-check: the TSF_ERROR check never succeeds, AFAICT.  This
> > 
> > See bug 636224 comment 3.
> 
> That comment is... dense.  IIUC, it's agreeing with my observation, and so this
> patch is valid.  Is that right?

Yes! The last two paragraphs are the conclusion.

/be

Comment 17

[Brendan Eich [:brendan]]

Comment on attachment 518235 [details] [diff] [review]
patch 1 (against TM 63063:87dcf64586a7)

>+        /* 
>+         * Unlike identifiers and strings, numbers cannot contain escaped
>+         * chars, so we don't need to use tokenbuf.  Instead we can just
>+         * convert the jschars in userbuf directly to the numeric value.
>+         */
>         if (radix == 10) {
>-            if (!js_strtod(cx, tokenbuf.begin(), tokenbuf.end(), &dummy, &dval))
>+            if (!js_strtod(cx, numStart, userbuf.addressOfNextRawChar(), &dummy, &dval))
>                 goto error;
>         } else {
>-            if (!GetPrefixInteger(cx, tokenbuf.begin(), tokenbuf.end(), radix, &dummy, &dval))
..1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
>+            if (!GetPrefixInteger(cx, numStart, userbuf.addressOfNextRawChar(), radix, &dummy,
>+                                  &dval))
>                 goto error;
>         }

Total nit attack here: house style wants the goto error; braced because the condition is multiline, but that seems avoidable. Ideas:

* Manually hoist and common userbuf.addressOfNextRawChar() into a local whose name is shorter than that pretty-long userbuf... expression.

* Shorten addressOfNextRawChar's name -- there is no addressOfNextCookedChar so Raw is there for symmetry with the other *RawChar* method names. Lose it? I just realized that all the TokenBuf accessor method names are burdened with "Raw", which seems unnecessary.

* Use jsdouble d; not jsdouble dval; for the local, it's the canonical name for that kind of variable.

Or just brace.

/be

Comment 18

[Nicholas Nethercote [inactive]]

(In reply to comment #17)
> 
> * Shorten addressOfNextRawChar's name -- there is no addressOfNextCookedChar so
> Raw is there for symmetry with the other *RawChar* method names. Lose it? I
> just realized that all the TokenBuf accessor method names are burdened with
> "Raw", which seems unnecessary.

I originally didn't have "Raw" but then there was TokenBuf::{,un}getChar() and TokenStream::{,un}getChar() and they didn't feel sufficiently distinguished for my liking.  I can shorten addressOfNextRawChar, though -- maybe just nextRawChar?

Comment 19

[Brendan Eich [:brendan]]

(In reply to comment #18)
> I originally didn't have "Raw" but then there was TokenBuf::{,un}getChar() and

No longer in TokenBuf, right? I don't see them but I'm looking at tm tip, not all the patches here.

> TokenStream::{,un}getChar() and they didn't feel sufficiently distinguished for
> my liking.

Different struct/class.

> I can shorten addressOfNextRawChar, though -- maybe just nextRawChar?

You've used addressOf elsewhere (grep shows all of these

jsinterp.h
jsobj.h
jsobjinlines.h

plus jsscan.h).

So I'd rather keep consistency there. But since TokenBuf is not TokenStream, adding Raw to every method save init, atStart, poison, and findEOL seems unnecessary. There's no atRawStart :-P.

/be

Comment 20

[Nicholas Nethercote [inactive]]

TokenBuf now has getRawChar and ungetRawChar.  I'll change it if it gets me the r+, but having both TokenBuf::getChar and TokenStream::getChar makes me nervous, because they have subtly different meanings (ie. the latter normalizes EOLs, the former doesn't.)  And likewise for peekChar/matchChar/ungetChar.

Comment 21

[Brendan Eich [:brendan]]

Different abstractions can have the same method name, but I take your point. The nesting makes a stronger case for encoding the difference in the struct or class into the method name. No worries, just do something about the nit.

/be

Comment 22

[Brendan Eich [:brendan]]

(You got the r+ already.)

Comment 23

[Brendan Eich [:brendan]]

Comment on attachment 518237 [details] [diff] [review]
patch 2

>+    const jschar *numStart;

Could localize to the two major then-blocks that need it. Not sure what's best or if it matters with any compiler.

>+    if (JS7_ISDNZ(c) || (c == '.' && JS7_ISDEC(peekChar()))) {

Wow, DNZ -- ok, it matches (or sees and raises) the short JS7_ISDEC style names. Would JS7_ISDECNZ be better? It would break the 9-letter mold of all these JS7_* macros.

>+                ReportCompileErrorNumber(cx, this, NULL, JSREPORT_ERROR, JSMSG_MISSING_HEXDIGITS);
>                 goto error;
>+            }
>+            numStart = userbuf.addressOfNextRawChar() - 1;
>+            while (JS7_ISHEX(c))
>+                c = getChar();
>+

Blank line here is unnecessary in prevailing style.

>+        } else if (JS7_ISDEC(c)) {
>+            radix = 8;
>+            numStart = userbuf.addressOfNextRawChar() - 1;
>+            while (JS7_ISDEC(c)) {
>+                /* Octal integer literals are not permitted in strict mode code. */
>+                if (!ReportStrictModeError(cx, this, NULL, NULL, JSMSG_DEPRECATED_OCTAL))
>+                    goto error;
>+
..12345678901234567890123456789012345678901234567890123456789012345678901234567890
>+                /*
>+                 * Outside strict mode, we permit 08 and 09 as decimal numbers, which
>+                 * makes our behaviour a superset of the ECMA numeric grammar. We
>+                 * might not always be so permissive, so we warn about it.
>+                 */

This comment somehow ended up overflowing the soft-ish comment margin of 79. How about rewrapping since you're moving it.

>+                if (c >= '8') {
>+                    if (!ReportCompileErrorNumber(cx, this, NULL, JSREPORT_WARNING,
>+                                                  JSMSG_BAD_OCTAL, c == '8' ? "08" : "09")) {
>+                        goto error;
>+                    }
>+                    goto decimal;   /* use the decimal scanner for the rest of the number */
>+                }
>+                c = getChar();
>+            }
>         } else {
>-            if (!GetPrefixInteger(cx, numStart, userbuf.addressOfNextRawChar(), radix, &dummy,
>-                                  &dval))
>-                goto error;

Oh, this goes away, so nm my nit on patch 1!

Looks great, a diff -w or -b would be even easier to read (I think -- try it and attach if true?).

/be

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 518238 [details] [diff] [review]
patch 3

>diff --git a/js/src/jsscan.cpp b/js/src/jsscan.cpp
>--- a/js/src/jsscan.cpp
>+++ b/js/src/jsscan.cpp
>@@ -1110,15 +1110,18 @@ TokenStream::getTokenInternal()
>     if (JS7_ISDNZ(c) || (c == '.' && JS7_ISDEC(peekChar()))) {
>         numStart = userbuf.addressOfNextRawChar() - 1;
>       decimal:

Forgot to note that, as with comments not preceded by { taking up one or more lines, and other paragraph-breaking structures, a label usually merits a blank line before it. Pre-existing nit.

/be

Comment 25

[Brendan Eich [:brendan]]

Comment on attachment 518239 [details] [diff] [review]
patch 4

Great to have the queued-up mini-patches to review.

/be

Comment 26

[Brendan Eich [:brendan]]

Comment on attachment 518240 [details] [diff] [review]
patch 5

Why didn't I write a JS7_TOLOWER ages ago? Presumably it would be even faster:

#define JS7_TOLOWER(c) ((c) | 0x20)

But it's pretty low-level and not worth doing unless there's a huge win, which there can't be for this 'e'/'E' test.

/be

Comment 27

[Brendan Eich [:brendan]]

Comment on attachment 518241 [details] [diff] [review]
patch 6

Ah, the old "-2" suffix. Could you use JS_ISSPACE_OR_BOM instead? I know it goes against the <ctypes.h> naming convention but something has got to give.

/be

Comment 28

[Brendan Eich [:brendan]]

Comment on attachment 518242 [details] [diff] [review]
patch 7

>+extern const bool js_isidstart[];
>+extern const bool js_isident[];
>+
>+static inline bool
>+JS_ISIDSTART(int32 c)

The JS_ISSPACE{,2} last time too jschar c -- these JS_ISID* ones don't. Necessary difference?

>+{
>+    unsigned w = c;
>+
>+    return (w < 128)
>+           ? js_isidstart[w]
>+           : JS_ISLETTER(c);

Fits on one line, arms of ?: are simple-enough expressions (member, call), why make it multiline?

>+}
>+
>+static inline bool
>+JS_ISIDENT(int32 c)
>+{
>+    unsigned w = c;
>+
>+    return (w < 128)
>+           ? js_isident[w]
>+           : JS_ISIDPART(c);

Ditto.

/be

Comment 29

[Brendan Eich [:brendan]]

Comment on attachment 518243 [details] [diff] [review]
patch 8

>diff --git a/js/src/jsscan.cpp b/js/src/jsscan.cpp
>--- a/js/src/jsscan.cpp
>+++ b/js/src/jsscan.cpp
>@@ -182,6 +182,27 @@ TokenStream::init(const jschar *base, si
>     listener = cx->debugHooks->sourceHandler;
>     listenerData = cx->debugHooks->sourceHandlerData;
> 
>+    /*
>+     * This table holds all the token kinds that satisfy these properties:
>+     * - A single char long.
>+     * - Cannot be a prefix of any longer token (eg. '+' is excluded because
>+     *   '+=' is a valid token).
>+     * - Doesn't need tp->t_op set (eg. this excludes '~').
>+     *
>+     * The few token kinds satisfying these properties cover roughly 35--45%
>+     * of the tokens seen in practice.
>+     */
>+    memset(oneCharTokens, 0, sizeof(oneCharTokens));
>+    oneCharTokens[';'] = TOK_SEMI;
>+    oneCharTokens[','] = TOK_COMMA;
>+    oneCharTokens['?'] = TOK_HOOK;
>+    oneCharTokens['['] = TOK_LB;
>+    oneCharTokens[']'] = TOK_RB;
>+    oneCharTokens['{'] = TOK_LC;
>+    oneCharTokens['}'] = TOK_RC;
>+    oneCharTokens['('] = TOK_LP;
>+    oneCharTokens[')'] = TOK_RP;

Do this statically. We have lots of ways to automate (Python is one obvious choice).

>     /*
>+     * Look for a one-char token;  they're common and simple.
>+     */
>+
>+    if (c < 128) {

No blank line between major comment and statement it prefixes (could use minor comment style too but maybe this is part of a larger structure where majors in a row all want to look the same).

>+        tt = oneCharTokens[c];
>+        if (tt != 0)
>+            goto out;
>+    }
>+
>+    /*
>      * Look for an identifier.
>      */
> 

Ulp, pre-existing same nit.

>+    TokenKind           oneCharTokens[128];  /* table of one-char tokens */

So this would be a static const array, generated in a .h file.

/be

Comment 30

[Brendan Eich [:brendan]]

Comment on attachment 518244 [details] [diff] [review]
patch 9

>+        c = getCharIgnoreEOL();
>+        if (JS_ISIDENT(c)) {
>+            /* do nothing */
>+        } else if (c == '\\') {
>+            if (!matchUnicodeEscapeIdent(&qc))
>+                break;
>+            c = qc;
>+        } else {
>+            break;
>+        }

Here and below where the same if-else-if-else-break structure recurs, this is shorter and simpler:

>+        if (!JS_ISIDENT(c)) {
>+            if (c != '\\' || !matchUnicodeEscapeIdent(&qc))
>+                break;
>+            c = qc;
>+        }

r=me with that in both places.

/be

Comment 31

[Brendan Eich [:brendan]]

Comment on attachment 518245 [details] [diff] [review]
patch 10

I leave it to Luke to remove the TSF_ERROR setting TokenStream::getTokenInternal over in bug 636224.

/be

Comment 32

[Brendan Eich [:brendan]]

Comment on attachment 518243 [details] [diff] [review]
patch 8

>+    TokenKind           oneCharTokens[128];  /* table of one-char tokens */

Compress using uint8, per IRC discussion. A comment in TokenStream::init about how this re-init'ed, per-ts constant data is tolerable would be good for future readers. Cite this bug.

>+    bool                maybeEOL[256];       /* probabilistic EOL lookup table */
>     bool                maybeStrSpecial[256];/* speeds up string scanning */

Should these be JSPackedBool not bool?

/be

Comment 33

[Nicholas Nethercote [inactive]]

(In reply to comment #32)
> >
> >+    bool                maybeEOL[256];       /* probabilistic EOL lookup table */
> >     bool                maybeStrSpecial[256];/* speeds up string scanning */
> 
> Should these be JSPackedBool not bool?

Makes no difference with GCC, but I can do it to be safe.

Comment 34

[Nicholas Nethercote [inactive]]

(In reply to comment #23)
>
> >+    const jschar *numStart;
> 
> Could localize to the two major then-blocks that need it. Not sure what's best
> or if it matters with any compiler.

That doesn't work because the octal parser can goto the decimal parser, and numStart's value needs to be preserved across the goto.

Comment 35

[Brendan Eich [:brendan]]

(In reply to comment #34)
> (In reply to comment #23)
> >
> > >+    const jschar *numStart;
> > 
> > Could localize to the two major then-blocks that need it. Not sure what's best
> > or if it matters with any compiler.
> 
> That doesn't work because the octal parser can goto the decimal parser, and
> numStart's value needs to be preserved across the goto.

D'oh -- noctal.

I trust you have a plan to de-spaghetti-ize getTokenInternal at some point.

/be

Comment 36

[Nicholas Nethercote [inactive]]

(In reply to comment #35)
> 
> I trust you have a plan to de-spaghetti-ize getTokenInternal at some point.

Other than moving the two big XML-specific chunks out, no.  Looking through the rest of it, the only other thing that bugs me is the handling of "//@line 123\n" lines, and maybe the handling of sharps, because they're obscure cases and relatively large.  I'll add them to bug 636654.

Comment 37

[Brendan Eich [:brendan]]

Comment on attachment 518242 [details] [diff] [review]
patch 7

We talked on IRC about "int c" being best for stdio/ctypes and ultimate compiler happiness. r=me with that and the one-line ?: nits picked.

/be

Comment 38

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/04a14872bdaf
http://hg.mozilla.org/tracemonkey/rev/38ed15659426
http://hg.mozilla.org/tracemonkey/rev/4b2d4ae70a91
http://hg.mozilla.org/tracemonkey/rev/7e136a2e97c6
http://hg.mozilla.org/tracemonkey/rev/143417141210
http://hg.mozilla.org/tracemonkey/rev/e5e7641a838e
http://hg.mozilla.org/tracemonkey/rev/04463409002b
http://hg.mozilla.org/tracemonkey/rev/3d399dda0723
http://hg.mozilla.org/tracemonkey/rev/1c3246c67c63
http://hg.mozilla.org/tracemonkey/rev/d70e52fad241

Plus a breakage fix for good luck:

http://hg.mozilla.org/tracemonkey/rev/40092c96120b

Comment 39

[Chris Leary [:cdleary] (not checking bugmail)]

http://hg.mozilla.org/mozilla-central/rev/04a14872bdaf
http://hg.mozilla.org/mozilla-central/rev/38ed15659426
http://hg.mozilla.org/mozilla-central/rev/4b2d4ae70a91
http://hg.mozilla.org/mozilla-central/rev/7e136a2e97c6
http://hg.mozilla.org/mozilla-central/rev/143417141210
http://hg.mozilla.org/mozilla-central/rev/e5e7641a838e
http://hg.mozilla.org/mozilla-central/rev/04463409002b
http://hg.mozilla.org/mozilla-central/rev/3d399dda0723
http://hg.mozilla.org/mozilla-central/rev/1c3246c67c63
http://hg.mozilla.org/mozilla-central/rev/d70e52fad241
http://hg.mozilla.org/mozilla-central/rev/40092c96120b