Introducing the JetStream 2 Benchmark Suite
- Almost all JetStream 1 benchmarks.
- New benchmarks inspired by subtests of Kraken.
- All of ARES-6.
- About half of the Web Tooling Benchmark.
- New WebAssembly tests derived from the asm.js benchmarks of JetStream 1.
- New benchmarks covering areas not tested by the other six benchmark suites.
You can read about each benchmark in JetStream 2 in the summary page.
Each benchmark in JetStream 2 measures a distinct workload, and no single optimization technique is sufficient to speed up all benchmarks. Some benchmarks demonstrate tradeoffs, and aggressive or specialized optimizations for one benchmark might make another benchmark slower. Each benchmark in JetStream 2 computes an individual score. JetStream 2 weighs each benchmark equally.
For this reason, JetStream 1 categorized each benchmark into one of two buckets: latency or throughput. Latency tests either measured startup performance or worst case performance. Throughput tests measured sustained peak performance. Like JetStream 1, JetStream 2 measures startup, worst case, and peak performance. However, unlike JetStream 1, JetStream 2 measures these metrics for every benchmark.
JetStream 2’s WebAssembly benchmarks are scored in two parts that equally weigh startup time and total execution time. The first part is the startup time, which is the time it takes until the WebAssembly module is instantiated. This is the time it takes the browser to put the WebAssembly code in a runnable state. The second part is the execution time. This is the time it takes to run the benchmark’s workload after it is instantiated. Both metrics are crucial for JetStream 2 to measure. Good startup performance makes it so that WebAssembly applications load quickly. Good execution time makes it so WebAssembly benchmarks run quickly and smoothly.
In total, JetStream 2 includes 64 benchmarks. Each benchmark’s score is computed as outlined above, and the final score is computed as the geometric mean of those 64 scores.
Optimizing Regular Expressions
A back reference takes the form of
/^(x*) 123 \1$/, where we match what is in the parenthesized group and then match the same thing again later in the string when a prior group is referenced. For the example given here, the string
"x 123 x" would match as well as the string
“xxxxx 123 xxxxx”. It matches any line that begins with 0 or more
" 123 " in the middle, and then ends with the same number of
'x' characters as the string started with. JIT support for back references was added for both Unicode and non-Unicode patterns. We also added JIT support for patterns with the ignore case flag that process ASCII and Latin1 strings. Back reference matching of Unicode ignore case patterns is more problematic due to the large amount of case folding data required. So, we revert to the YARR interpreter for Unicode regular expressions that contain back references that also ignore character case.
Before discussing the next improvement we made to the regular expression engine, some background is in order. The YARR Regular Expression engine uses a backtracking algorithm. When we want to match a pattern like
/a[bc]*c/, we process forward in the pattern and when we fail to match a term, we backtrack to the prior term to see if we can try the match a little differently. The
[bc]* term will match as many b’s and/or c’s in a row as possible. The string
“abc” matches the pattern, but it needs to backtrack when matching the
'c' the first time. This happens because the middle
[bc]* term will match both the
'b' and the
'c', and when we try to match the final
'c' term in the pattern, the string has been exhausted. We backtrack to the
[bc]* term and reduce the length of that term’s match from
“bc” to just
“b” and then match the final
'c' term. This algorithm requires state information to be saved for various term types so that we can backtrack. Before we started this work, backtracking state consisted of counts and pointers into the term’s progress in a subject string.
We had to extend how backtracking state was saved in order to add support for counted captured parenthesized groups that are nested within longer patterns. Consider a pattern like
/a(b|c)*bc/. In addition to the backtracking information for the contents of the captured parenthesized group, we also need to save that group’s match count, and start and end locations as part of the captured group’s backtracking state. This state is saved in nodes on a singly linked list stack structure. The size of these parenthesized group backtracking nodes is variable, depending on the amount of state needed for all nested terms including the nested capture group’s extents. Whenever we begin matching a parenthesized group, either for the first or a subsequent time, we save the state for all the terms nested within that group as a new node on this stack. When we backtrack to the beginning of a parenthesized group, to try a shorter match or to backtrack to the prior terms, we pop the captured group’s backtracking node and restore the saved state.
We also made two other performance improvements that helped our JetStream 2 performance. One is matching longer constant strings at once and the other is canonicalizing constructed character classes. We have had the optimization to match multiple adjacent fixed characters in a pattern as a group for some time, where we could match up to 32bits of character data at once, e.g four 8 bit characters. Consider the expression
/starting/, which simply looks for the string
“starting”. These optimizations allowed us to match
“star” with one 32 bit load-compare-branch sequence and then the trailing
“ting” with a second 32 bit load-compare-branch sequence. The recent change was made for 64 bit platforms and allows us to match eight 8 bit characters at a time. With this change, this regular expression is now matched with a single 64 bit load-compare-branch sequence.
The latest Regular Expression performance improvement we did that provided some benefit to JetStream 2 was to coalesce character classes. For background, character classes can be constructed from individual characters, ranges of characters, built in escape characters, or built in character classes. Prior to this change, the character class
[\dABCDEFabcdef], which matches any hex digit, would check for digit characters by comparing a character value against ‘0’ and ‘9’, and then individually compare it against each of the alphabetic characters,
'B', etc. Although this character class could have been written as
/[\dABCDEFabcdef]/.exec(“X”) would require 14 compares and branches to determine there wasn’t a match. Now it takes just 4 compares and branches.
The performance impact of these optimizations was dramatic for some of the Web Tooling Benchmark tests. Adding the ability to JIT greedy nested parens improved the performance of coffeescript by 6.5x. JIT’ing non-greedy nested parens was a 5.8x improvement to espree and a 3.1x improvement to acorn. JIT’ing back references improved coffeescript by another 5x for a total improvement of 33x on that test. These changes also had smaller, but still measurable improvements on other JetStream 2 tests.
All numbers are gathered on a 2018 MacBook Pro (13-inch, Four Thunderbolt 3 Ports, MacBookPro15,2), with a 2.3GHz Intel Core i5 and 8GB of RAM. The numbers for Safari 12.0.3 were gathered on macOS 10.14.3. The numbers for Safari 12.1, Chrome 73.0.3683.86, and Firefox 66.0.1 were gathered on macOS 10.14.4. The numbers are the average of five runs of the JetStream 2 benchmark in each browser. Each browser was quit and relaunched between each run.
The above figure shows that Safari 12.1 is the fastest browser at running JetStream 2. It is 9% faster than Safari 12.0.3, 8% faster than Chrome 73.0.3683.86, and 68% faster than Firefox 66.0.1.
We’d love to hear any feedback you have on JetStream 2 or the optimizations we’ve made for it. Get in touch with Saam or Michael on Twitter with any feedback you have.