Closed
Bug 645598
Opened 14 years ago
Closed 13 years ago
Trim last bits of fat from the scanner
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
RESOLVED
FIXED
People
(Reporter: n.nethercote, Assigned: n.nethercote)
Details
(Whiteboard: fixed-in-tracemonkey)
Attachments
(3 files)
17.48 KB,
patch
|
Waldo
:
review+
|
Details | Diff | Splinter Review |
9.76 KB,
patch
|
Waldo
:
review+
|
Details | Diff | Splinter Review |
1.49 KB,
patch
|
Waldo
:
review+
|
Details | Diff | Splinter Review |
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.
Assignee | ||
Comment 1•14 years ago
|
||
Attachment #522272 -
Flags: review?(brendan)
Assignee | ||
Comment 2•14 years ago
|
||
Attachment #522273 -
Flags: review?(brendan)
Assignee | ||
Comment 3•14 years ago
|
||
Attachment #522274 -
Flags: review?(brendan)
Comment 4•14 years ago
|
||
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.
Assignee | ||
Comment 5•14 years ago
|
||
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
Assignee | ||
Comment 6•14 years ago
|
||
Brendan: 3 week review ping!
Assignee | ||
Comment 7•14 years ago
|
||
Brendan: 7 week review ping!
Assignee | ||
Comment 8•14 years ago
|
||
Comment on attachment 522272 [details] [diff] [review]
patch 1 (against TM 63372:62cac7587f11 + patch from bug 636654)
Time to try another reviewer.
Attachment #522272 -
Flags: review?(brendan) → review?(jwalden+bmo)
Assignee | ||
Updated•14 years ago
|
Attachment #522273 -
Flags: review?(brendan) → review?(jwalden+bmo)
Assignee | ||
Updated•14 years ago
|
Attachment #522274 -
Flags: review?(brendan) → review?(jwalden+bmo)
Comment 9•13 years ago
|
||
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? ಠ_ಠ
Attachment #522272 -
Flags: review?(jwalden+bmo) → review+
Comment 10•13 years ago
|
||
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.
Attachment #522273 -
Flags: review?(jwalden+bmo) → review+
Comment 11•13 years ago
|
||
Comment on attachment 522274 [details] [diff] [review]
patch 3
Review of attachment 522274 [details] [diff] [review]:
-----------------------------------------------------------------
Attachment #522274 -
Flags: review?(jwalden+bmo) → review+
Comment 12•13 years ago
|
||
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
Assignee | ||
Comment 13•13 years ago
|
||
>
> 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.
Assignee | ||
Comment 14•13 years ago
|
||
(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.
Assignee | ||
Comment 15•13 years ago
|
||
http://hg.mozilla.org/tracemonkey/rev/0fd30fdb7a6b
http://hg.mozilla.org/tracemonkey/rev/3bae9deeb9b4
http://hg.mozilla.org/tracemonkey/rev/b71f5419e37a
Whiteboard: fixed-in-tracemonkey
Comment 16•13 years ago
|
||
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
Updated•13 years ago
|
Status: ASSIGNED → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•