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.

(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.

(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!

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.

> 10. no-TSF_ERROR-check: the TSF_ERROR check never succeeds, AFAICT. This See bug 636224 comment 3. /be

(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?

(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 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

(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?

(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

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.

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

(You got the r+ already.)

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 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 on attachment 518239 [details] [diff] [review] patch 4 Great to have the queued-up mini-patches to review. /be

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 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 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 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 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 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 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

(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.

(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.

(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

(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 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

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

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