2045097 - Consider a 4-code-unit-at-a-time pre-scan for JSON LiteralValue strings

Status: RESOLVED FIXED

(Core :: JavaScript Engine, enhancement, P1)

Description

[Bryan Thrall [:bthrall]]

Attachment: 8bc0c897-3073-407d-8f78-94d74cdc3051.diff

Add a 4-code-unit-at-a-time pre-scan for JSON LiteralValue strings that skips an initial run of code units greater than backslash before the existing fast-path scanner.

Comment 1

[Bryan Thrall [:bthrall]]

The backslash is the JSON escape character and is greater than '"', so the pre-scan will safely terminate if it hits an escaped character or the end of the string.

I think the patch could do with a little clean up and a comment explaining what is going on.

Comment 2

[Steve Fink [:sfink] [:s:]]

Ok, I dug into this pretty extensively. First, I wrote a SWAR version (SIMD Within A Register) that does bit twiddling tricks to check 8 latin1 chars at a time with no autovectorization required. That was a good speedup on all of my microbenchmark cases, including one modeled on an old sessionstore.js file I had lying around. That got a 1.4x speedup. Most cases were about 1.2x, and the pathological case was 0.95x. Not bad.

But a microbenchmark that restricted itself to only lowercase strings got over 8x on Claude's 4-at-a-time version. My SWAR version was better for every other case, but the AI one was still beating me by a factor of 6.8x! (Not on the sessionstore case, fwiw. It barely got any speedup on that.)

So I gave up on the SWAR approach, and found a way to expand the autovectorized one to handle many more cases (all of them, as it turns out, though I still don't depend on that.) The main problem with the original 4-at-a-time is that its fast path is ch > '\\', which works for lowercase keys and values but it bails out (drops back to the slow path) with any uppercase letter or a space character. Expanding the code to handle those cases (at least in the current clang we're using) made it much more robust -- and oddly enough, even faster even on the one case that never had to bail with the original code.

Anyway, that's a lot of text. Here are my current results:

Test              js-baseline     js-swar    js-chunk4  js-chunk4-precise  js-swar/base  js-chunk4/base  js-chunk4-precise/base
-------------------------------------------------------------------------------------------------------------------------------
sessionstore       115.8 MB/s  163.7 MB/s   121.7 MB/s         459.4 MB/s         1.41x           1.05x                   3.97x
lowercase_long     135.1 MB/s  177.9 MB/s  1208.0 MB/s        1248.9 MB/s         1.32x           8.94x                   9.24x
mixed_ascii_long   135.0 MB/s  156.2 MB/s   145.7 MB/s        1242.0 MB/s         1.16x           1.08x                   9.20x
uppercase_digits   134.7 MB/s  161.3 MB/s   145.1 MB/s        1261.9 MB/s         1.20x           1.08x                   9.37x
short_strings       43.9 MB/s   45.6 MB/s    42.3 MB/s          43.5 MB/s         1.04x           0.96x                   0.99x
escape_heavy        91.0 MB/s   86.9 MB/s    91.5 MB/s          92.3 MB/s         0.95x           1.01x                   1.01x
key_heavy           64.8 MB/s   76.5 MB/s    64.3 MB/s          84.4 MB/s         1.18x           0.99x                   1.30x
-------------------------------------------------------------------------------------------------------------------------------

The 4x speedup on the sessionstore case is really sweet.

Interestingly, this isn't the limit. The autovectorized code isn't even very good. I think I could drop about half the SSE instructions with a more direct implementation for the original version. The updated chunk4-precise one wouldn't gain as much, but I think the improvement would still apply (use pmovmskb to grab the high bits of each byte instead of doing unpack,unpack,grab sign bits of 32-bit values).

Comment 3

[Steve Fink [:sfink] [:s:]]

Oh, weird. I looked and it's now using pmovmskb for the equality checks, but persists in not using it for the range check. Silly autovectorizer.

Comment 4

[Steve Fink [:sfink] [:s:]]

I haven't managed to get an 8-element chunk version past the autovectorizer. It complains about multiple things that it was ok with for the 4-element version. The generated code makes inefficient use of the full vector width, and even though there are other approaches, it seems like its checks at least are constrained to what will work with that approach. Oh well, I'm happy with these results already.

Comment 5

[Steve Fink [:sfink] [:s:]]

Attachment: Bug 2045097 - Optimize JSONTokenizer::readString with 4-element pre-scan that the autovectorizer is ok with. r=bthrall

Comment 6

[Bryan Thrall [:bthrall]]

:denispal, this bug is for the claudometer patch 8bc0c897-3073-407d-8f78-94d74cdc3051

Comment 7

[Steve Fink [:sfink] [:s:]]

Here are my results for the posted version of the patch. js-chunk4 is the original Claudometer patch (attached). js-chunk4-precise checks for all of '"', '\', and 0-0x1f (and still manages to get autovectorized). Test sessionstore_act is my actual (13MB) sessionstore.js file. sessionstore is a synthetic JSON file (100KB long) that uses the same distribution of characters as the actual sessionstore, which apparently doesn't make that good of a match since the results are wildly different. I think the best argument for landing this is the 9x speedup for js-chunk4-precise on mixed_ascii_long with no slowdowns. (Btw, a test that I don't include here is one where I broke the autovectorizer but match equivalent strings, which might be a decent proxy for a different architecture that can't vectorize this. It still got a respectable speedup. So this shouldn't do much harm.)

  sessionstore_act  Real-world: actual sessionstore.js file
      sessionstore  "Real-world": mixed-case keys, varied value lengths, ~1% escapes
    lowercase_long  Best for simple branchless (all chars > 0x5c). Also good for SWAR.
  mixed_ascii_long  Requires more precise branchless, still good for SWAR.
     short_strings  Poor for both.
      escape_heavy  Worst for both (immediate fallback to slow escape path).
         key_heavy  Big on property names.

JSON results written to /tmp/bench_r9bbblug.json

Test              js-baseline    js-chunk4  js-chunk4-precise  js-chunk4/base  js-chunk4-precise/base
-----------------------------------------------------------------------------------------------------
sessionstore_act    87.7 MB/s    82.2 MB/s         121.5 MB/s           0.94x                   1.39x
sessionstore       123.3 MB/s   130.1 MB/s         509.7 MB/s           1.06x                   4.13x
lowercase_long     135.9 MB/s  1208.7 MB/s        1183.7 MB/s           8.89x                   8.71x
mixed_ascii_long   126.9 MB/s   146.7 MB/s        1173.5 MB/s           1.16x                   9.25x
short_strings       41.2 MB/s    39.6 MB/s          41.4 MB/s           0.96x                   1.00x
escape_heavy        91.3 MB/s    91.4 MB/s          92.6 MB/s           1.00x                   1.01x
key_heavy           61.7 MB/s    56.3 MB/s          79.3 MB/s           0.91x                   1.29x
-----------------------------------------------------------------------------------------------------

Comment 8

[Steve Fink [:sfink] [:s:]]

The results on try show essentially no change whatsoever. This is a comparison between a base revision and a revision with the patch here as well as the further improvement from bug 2046272.

I downloaded the build to see if it was producing SSE code. Oddly, the symbol I have been comparing in the shell was not present:

_ZN2js13JSONTokenizerIDsNS_20JSONPerHandlerParserIDsNS_20JSONFullParseHandlerIDsEEEEE10readStringILNS_14JSONStringTypeE0EEENS_9JSONTokenEv
  which decodes to:
js::JSONToken js::JSONTokenizer<char16_t, js::JSONPerHandlerParser<char16_t, js::JSONFullParseHandler<char16_t> > >::readString<(js::JSONStringType)0>()

but a related instantiation was:

_ZN2js13JSONTokenizerIDsNS_20JSONPerHandlerParserIDsNS_22JSONSyntaxParseHandlerIDsEEEEE10readStringILNS_14JSONStringTypeE0EEENS_9JSONTokenEv
  which decodes to:
js::JSONToken js::JSONTokenizer<char16_t, js::JSONPerHandlerParser<char16_t, js::JSONSyntaxParseHandler<char16_t> > >::readString<(js::JSONStringType)0>()

(So, FullParseHandler vs SyntaxParseHandler). The latter does have the expected blob of SSE instructions.

Perhaps the first one was inlined into its parent? It's called by advance, but that also only has variants for JSONReviveHandler, JSONSyntaxParseHandler, and DelegateHandler. Odd. Anyway, the 2nd one is present in the shell as well.

Comment 9

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/026f9e497047
https://hg.mozilla.org/integration/autoland/rev/a161c29f4107
Optimize JSONTokenizer::readString with 4-element pre-scan that the autovectorizer is ok with. r=bthrall

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/a89d39365be6
https://hg.mozilla.org/mozilla-central/rev/d764910a7ea3
Optimize JSONTokenizer::readString with 4-element pre-scan that the autovectorizer is ok with. r=bthrall

Comment 11

[agoloman]

https://hg.mozilla.org/mozilla-central/rev/d764910a7ea3

Comment 12

[Florin Bilt]

(In reply to Pulsebot from comment #9)

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/026f9e497047
https://hg.mozilla.org/integration/autoland/rev/a161c29f4107
Optimize JSONTokenizer::readString with 4-element pre-scan that the
autovectorizer is ok with. r=bthrall

Perfherder has detected a browsertime performance change from push a161c29f4107ba165782641d9bdf344766c7b53b.

No action is required from the author; this comment is provided for informational purposes only.

Improvement	Test	Platform	Options	Absolute values [old vs new]	Performance Profiles
13%	jetstream3 json-parse-inspector-Geometric (doc)	macosx1500-aarch64-shippable	fission webrender	417.98 score -> 473.89 score
11%	jetstream3 json-parse-inspector-Average (doc)	macosx1500-aarch64-shippable	fission webrender	10.11 ms -> 9.03 ms
3%	speedometer3 TodoMVC-JavaScript-ES6-Webpack-Complex-DOM/total (doc)	macosx1500-aarch64-shippable	fission webrender	23.10 ms -> 22.46 ms	Before/After

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

Comment 13

[Performance Sheriff Bot]

Perfherder has detected a devtools performance change from push a161c29f4107ba165782641d9bdf344766c7b53b.

No action is required from the author; this comment is provided for informational purposes only.

Improvement	Test	Platform	Options	Absolute values [old vs new]
5%	damp custom.netmonitor.exportHar (doc)	linux2404-64-shippable	e10s fission stylo webrender	1,060.96 ms -> 1,006.52 ms

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.