645598 - Trim last bits of fat from the scanner

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Nicholas Nethercote [inactive]]

A stack of patches for the scanner that speeds up parsing by ~1.05x.  Once 
these land I'm declaring victory on the scanner, I really can't see any fat
left that's worth removing.

Patch 1:
- The big patch.  The basic idea is to make the main scanning loop as tight
  and DFA-like as possible.

- By inlining the getChar() call that was in the whitespace-scanning loop, I
  was able to make the main loop go like this:
  - Check there's a char to get (EOF if not).
  - Get the char.
  - If it's not a 7-bit char, go to a slow path.  (Before this patch, the
    c<128 test potentially occurred multiple times.)
  - If it's whitespace, goto the top of the loop.
  - Otherwise, test it to see what kind of token it starts, in order of
    frequency (eg. identifiers and one-char tokens are very common, hex/oct
    numbers are much less common).  This test is done with a lookup table
    called firstCharKinds.

- Note that some of the rare cases (identifiers starting with '\', numbers
  starting with '.') are now handled separately, and then control jumps back
  to the identifier/number-handling code.

- Other minor changes:  used getCharIgnoreEOL/ungetCharIgnoreEOL in a couple
  of extra places;  removed js_alnum because it's dead;  changed some
  functions in TokenBuf to return jschar instead of int32, since they cannot
  return EOF.

Patch 2:
- Moves scanning of strings earlier, to match some measurements I did on
  parsemark.  Hardly any faster, but satisfies my inner pedant.

Patch 3:
- Adds versions of peekChar() and matchChar() that don't take flags, for a
  small win.

These patches apply on top of the patch in bug 636654.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: patch 1 (against TM 63372:62cac7587f11 + patch from bug 636654)

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: patch 2

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: patch 3

Comment 4

[Luke Wagner [:luke]]

Nice job on all this scanner work!  I'm not sure if you saw bug 639085 (it uses ad hoc rdtsc-logging to compare time in various components with overall browser time).  In attachment 522043 [details], you can see 9% (335ms) and 12% (293ms) being spent in scan/parse/emit, so you are definitely trimming where it matters.

Browser startup would be about 200ms, but XDR brings it down to 20ms.

Comment 5

[Nicholas Nethercote [inactive]]

With all three patches applied:

---------------------------------------------------------------
| millions of instructions executed                           |
| total                        | compiled (may overestimate)  |
---------------------------------------------------------------
|    12.028    11.711 (1.027x) |    158432    158432 (------) | 280slides-comb
|    45.919    43.942 (1.045x) |    802837    802837 (------) | ball-pool-comb
|    23.489    22.702 (1.035x) |    379362    379362 (------) | dojo
|    43.938    42.595 (1.032x) |    732997    732997 (------) | effectgames-ga
|    11.322    10.970 (1.032x) |    170028    170028 (------) | ga
|   239.205   229.923 (1.040x) |     4.834     4.834 (------) | gmail-combined
|    70.112    67.045 (1.046x) |     1.262     1.262 (------) | gravity-combin
|    17.041    16.501 (1.033x) |    263617    263617 (------) | jquery-min
|    29.256    28.455 (1.028x) |    499878    499878 (------) | jsgb-combined
|    43.832    42.239 (1.038x) |    759142    759142 (------) | mochikit
|   197.686   189.619 (1.043x) |     3.652     3.652 (------) | pipio-combined
|    10.137     9.895 (1.024x) |    122157    122157 (------) | processing-twi
|    35.098    34.550 (1.016x) |    319604    319604 (------) | sunspider-comb
|    14.417    13.961 (1.033x) |    224663    224663 (------) | tetris-combine
|    52.880    50.903 (1.039x) |    926663    926663 (------) | twitter-combin
|    54.656    52.611 (1.039x) |    915264    915264 (------) | v8-combined
|     7.965     7.792 (1.022x) |     99991     99991 (------) | yui-min
|   318.862   305.882 (1.042x) |     5.770     5.770 (------) | zimbra-combine
-------
|  1227.851  1181.305 (1.039x) |    21.894    21.894 (------) | all

Comment 6

[Nicholas Nethercote [inactive]]

Brendan: 3 week review ping!

Comment 7

[Nicholas Nethercote [inactive]]

Brendan: 7 week review ping!

Comment 8

[Nicholas Nethercote [inactive]]

Comment on attachment 522272 [details] [diff] [review]
patch 1 (against TM 63372:62cac7587f11 + patch from bug 636654)

Time to try another reviewer.

Comment 9

[Jeff Walden [:Waldo]]

Comment on attachment 522272 [details] [diff] [review]
patch 1 (against TM 63372:62cac7587f11 + patch from bug 636654)

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

You are starting to make me think the parser code is almost pretty!  I'm not sure whether I should be afraid or not.

::: js/src/jsscan.cpp
@@ +400,4 @@
>          if (c == EOF)
>              break;
>          if (c == '\n') {
> +            ungetCharIgnoreEOL(c);

This is the comment by peekChars right now:

/*
 * Peek n chars ahead into ts.  Return true if n chars were read,  if
 * there weren't enough characters in the input stream.  This function cannot
 * be used to peek into or past a newline.
 */

I had to look at the callers to make complete sense of this, because the newline-y bits here were unclear to me.  I propose this alternative:

Return true iff n raw characters can be read from this without reading past EOF or a newline, and copy those characters into cp if they could be read.  The characters are not consumed: use skipChars(n) to do so after checking that the consumed characters had appropriate values.

@@ +1321,5 @@
> + * HexOct:  48: '0'
> + * Space:   9, 11, 12: '\t', '\v', '\f'
> + * EOL:     10, 13: '\n', '\r'
> + */
> +uint8 firstCharKinds[] = {

static const uint8 firstCharKinds[]

@@ +1322,5 @@
> + * Space:   9, 11, 12: '\t', '\v', '\f'
> + * EOL:     10, 13: '\n', '\r'
> + */
> +uint8 firstCharKinds[] = {
> +/*       0        1        2        3        4        5        6        7        8        9    */

I think this is a case where, if we're not already breaking a 99-character line limit, we should.  The natural way to read and evaluate this (at least for me) is to compare it to a character map.  Probably you can readjust a character map to match 10-wide and all.  But it's less likely you can adjust how it displays code units, which are likely displayed as hexadecimal numbers.  (That's how the one in Fedora 14 displays it.)  I think this table should be sixteen entries wide so that it's easier to go from a hex number to the actual location in the table, and vice versa.

@@ +1336,5 @@
> +/*  9 */   Ident, OneChar, _______, OneChar, _______,   Ident, _______,   Ident,   Ident,   Ident,
> +/* 10 */   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,
> +/* 11 */   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,   Ident,
> +/* 12 */   Ident,   Ident,   Ident, OneChar, _______, OneChar, _______, _______
> +};

|JS_STATIC_ASSERT(sizeof(firstCharKinds) == 128);| just to double-check the desired range is covered.

This would have been clearer with a 16-wide table; I tied myself into mental knots trying to verify this due to mental off-by-one errors.

@@ +1401,5 @@
> +
> +    /*
> +     * Get the token class, based on the first char.
> +     */
> +    c1kind = (FirstCharKind) firstCharKinds[c];

C++-style FirstCharKind(firstCharKinds[c]) cast.

@@ +1421,4 @@
>      tp = newToken(-1);
>  
>      /*
>       * Look for a one-char token;  they're common and simple.

It's not so much that it's a single-character token -- it's also that it can't be a multi-character token.  (I got hung up on why '!' wasn't in the 'OneChar' list until I figured this out.)  I suggest the following elucidative comment:

/* Look for an unambiguous single-char token; update line state on EOLs. */

@@ +1603,5 @@
> +#endif
> +        /*
> +         * Default so compiler can modify to JSOP_GETTER if 'p getter: v' in an
> +         * object initializer, likewise for setter.
> +         */

This comment's definitely out-of-date, because |p getter:| syntax has been gone from the engine for nearly a year now.  I think the comment can be removed completely without losing any communicative element here, but I'm not 100% sure.

::: js/src/jsstr.h
@@ -882,5 @@
>      /* Treat little- and big-endian BOMs as whitespace for compatibility. */
>      return (w < 128)
>             ? js_isspace[w]
> -           : w == NO_BREAK_SPACE || w == BYTE_ORDER_MARK ||
> -             (JS_CCODE(w) & 0x00070000) == 0x00040000 || w == 0xfffe || w == 0xfeff;

Are you really sure it's just as safe to check for |w == BYTE_ORDER_MARK| once as to check for it twice?  ಠ_ಠ

Comment 10

[Jeff Walden [:Waldo]]

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

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

rs=me assuming this was just a copy-paste, as it appears at a glance.

Comment 11

[Jeff Walden [:Waldo]]

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

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

Comment 12

[Brendan Eich [:brendan]]

Nick: please accept my abject apologies, I was traveling and lost track of my review queue -- no excuses, I owe you big-time, Waldo too. Call in favors by IRC and direct email.

/be

Comment 13

[Nicholas Nethercote [inactive]]

>
> I think this is a case where, if we're not already breaking a 99-character
> line limit, we should.  The natural way to read and evaluate this (at least
> for me) is to compare it to a character map.  Probably you can readjust a
> character map to match 10-wide and all.  But it's less likely you can adjust
> how it displays code units, which are likely displayed as hexadecimal
> numbers.  (That's how the one in Fedora 14 displays it.)  I think this table
> should be sixteen entries wide so that it's easier to go from a hex number
> to the actual location in the table, and vice versa.

I'm happy to do that, the reason I made it 10 wide was that there are several existing tables that are 10 wide.

Comment 14

[Nicholas Nethercote [inactive]]

(In reply to comment #12)
> Nick: please accept my abject apologies, I was traveling and lost track of
> my review queue -- no excuses, I owe you big-time, Waldo too. Call in favors
> by IRC and direct email.

Apology accepted! :)  You're normally very reliable and quick and this was hardly urgent so I'm not too worried.

Comment 15

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/0fd30fdb7a6b
http://hg.mozilla.org/tracemonkey/rev/3bae9deeb9b4
http://hg.mozilla.org/tracemonkey/rev/b71f5419e37a

Comment 16

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

cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/0fd30fdb7a6b
http://hg.mozilla.org/mozilla-central/rev/3bae9deeb9b4
http://hg.mozilla.org/mozilla-central/rev/b71f5419e37a