• Parsing, part 2: lazy parsing
  • V8. Dev
  • The Nuggets translation Project
  • Permanent link to this article: github.com/xitu/gold-m…
  • Translator: suhanyujie

This is the second in a series of articles on how V8 can parse JavaScript as fast as possible. Part 1 explained how to make the V8 scanner faster.

Parsing is the step provided by the compiler (in V8, the bytecode compiler Ignition) to convert source code into an intermediate representation. Parsing and compilation occur during the critical process of starting rendering of a Web page, rather than all of these functions being immediately available to the browser during page startup. While developers can use asynchronous and deferred scripting, it doesn’t always work. In addition, many Web pages only provide code for functions that may not be available to users during a small portion of the page’s run.

Rushing to compile unnecessary code can lead to real resource consumption:

  • CPU cycles are used to create code that actually delays the validity of the code when the page starts.
  • Code objects take up memory, at least when bytecode refresh determines that it is not currently needed, and allows the occupied memory to be garbage collected.
  • When the top-level script completes, the compiled code is eventually cached on disk, taking up disk space.

For these reasons, all major browsers implement lazy parsing. Instead of generating an abstract syntax tree for each function and then compiling it into bytecode, the parser “pre-parses” the actual functions it encounters, rather than all of them. This is done by switching to using a pre-parser, which is a copy of the parser that does the bare minimum and otherwise skips functions. The pre-parser verifies that it is syntactically valid to skip the function and produces all the information needed to compile the external function correctly. When a pre-parsed function is later called, it is fully parsed and compiled as needed.

Variable assignment

The main issue complicating pre-parsing is variable allocation.

Manage function activation on the machine stack for performance reasons. For example, if a function g calls f with arguments 1 and 2:

function f(a, b) {
  const c = a + b;
  return c;
}

function g() {
  returnf(1, 2); // This returns a pointer to 'f', which points to here (because when 'f' returns, it will return here). }Copy the code

The receiver (such as the this value of f, which is globalThis because it is an arbitrary function call) is first pushed onto the stack, followed by the called function f. Parameters 1 and 2 are then pushed onto the stack. The function f is called. To perform the call, we first save the state of G on the stack: return an instruction pointer to f (rip; What code do we need to return) and “frame Pointers” (fp; What the stack should look like when it returns). Then we enter f, which allocates space for the local variable C, and any temporary space it may need. This ensures that if a function is called out of scope, the data used by the function is not available: it is simply popped off the stack.

Stack layout when calling function f, assigning parameters A and B and local variable C on the stack.

The problem with this situation is that the function can refer to variables declared outside the function. Internal functions, which can last longer than the calls that created them:

functionMake_f (d) {// ← 'd' declarationreturn functioninner(a, b) { const c = a + b + d; // ← 'd' referencesreturn c;
  };
}

const f = make_f(10);

function g() {
  return f(1, 2);
}
Copy the code

In the example above, the reference to the local variable d declared in make_f from inner is not evaluated until make_f returns. To achieve this, language virtual machines that use lexical closures assign references to variables from internal functions on the heap in a structure called a “context.”

Stack layout when make_f is called, with parameters copied into the context allocated in the heap for subsequent capture of D in inner.

This means that for a variable declared in a function, we need to know whether the internal function refers to the variable so that we can decide whether to store it on the stack or in the heap-allocated context. When we evaluate a function literal, we assign a closure that points to the code in the function and the current context: the context contains variable values that it may need to access.

In short, we need to at least keep track of references to variables in the preparser.

If we only track references, we overestimate references to variables. Variables declared in an outer function can be overridden by redeclarations in the inner function, so that references from the inner function point to the inner declaration rather than to the outer declaration. If you keep external variables in context without limitation, performance suffers. Therefore, variable allocation allows pre-parsing to perform reasonably, and we need to ensure that pre-parsed functions properly track variable references and declarations.

Top-level code is an exception to this rule. Top-level scripts always allocate heap memory because variables are visible across scripts. An easy way to approach a better implementation of this architecture is simply to run the preparser without having to trace variables to quickly parse the top-level function; And use the full parser only for internal functions, skipping compiling them. Although this was more expensive than pre-parsing because we didn’t have to build the entire AST, it got us up and running. This is exactly what V8 did in V8 V6.3 / Chrome 63 and later.

Tells the preparser about variables

Tracing variable assignments and references in a pre-parser is complicated because it is not clear from the start in JavaScript what the partial expression means. For example, if we have a function f that takes d, and it has an inner function g, this expression looks like it might refer to D.

function f(d) {
  function g() {
    const a = ({ d }
Copy the code

It may end up referring to D, because the tokens we see are part of the destructor assignment expression.

function f(d) {
  function g() {
    const a = ({ d } = { d: 42 });
    return a;
  }
  return g;
}
Copy the code

It may also end up being an arrow function with a destructor parameter D, in which case d in F is not referenced by G.

function f(d) {
  function g() {
    const a = ({ d }) => d;
    return a;
  }

  return [d, g];

}
Copy the code

Initially, our pre-parser was implemented as a separate copy of the parser, not having much in common, which caused the two parsers to differ over time. By rewriting ParserBase parsers and preparsers to implement the template recursive pattern, we managed to make them as common as possible while maintaining the performance benefits of a separate copy. This greatly simplifies the tracking of adding all variables to the preparser, since most implementations can be shared between the parser and the preparser.

In fact, it is incorrect to ignore variable declarations and references or even top-level functions. The ECMAScript specification requires that various types of variable conflicts be detected the first time a script is parsed. For example, if a variable is declared twice in the same scope, it is considered a prophase syntax error. Because our pre-resolver simply skips variable declarations, it will mistakenly allow code to pass in the preparation phase. At this point, what we consider to be performance optimizations violate the specification. However, now that the pre-parser tracks variables correctly, we eliminate such specification violations with variable resolution and no significant performance cost.

Skip internal functions

As mentioned earlier, when a pre-parsed function is first called, it is fully parsed and the generated AST is compiled into bytecode.

// This is the top-level scopefunction outer() {// Preparsing is completefunction inner}} outer(); // Fully parse and compile 'outer' instead of 'inner'.Copy the code

This function points directly to the external context, which contains the value of the declared variable that the internal function needs to use. To allow lazy compilation of functions (and support for debuggers), the context points to a metadata object named ScopeInfo. The ScopeInfo object describes the variables listed in the context. This means that in compiler internal functions, we can calculate the position of variables in the context chain.

However, to calculate whether the delayed-compiled function itself requires a context, we need to perform scope parsing again: we need to know whether the function nested in the delayed-compiled function refers to a variable declared by the delayed-compiled function. We can calculate that by precompiling again. This is exactly what V8 did up until V8 V6.3 / Chrome 63. But this is not an ideal performance optimization because it makes the relationship between source size and parsing cost nonlinear: we will prepare as many nested functions as possible. In addition to the natural nesting of dynamic programs, JavaScript packers typically wrap code in “callable function expressions” (IIFEs), giving most JavaScript programs multiple nesting layers.

At a minimum, each reparsing increases the cost of the parsing function

To avoid nonlinear performance overhead, we even perform global scoped parsing during pre-parsing. We store enough metadata so that we can simply skip the internal functions later without having to reparse them. One way is to store variable names referenced by internal functions. This is expensive storage, and it still requires us to repeat the work: we’ve already performed variable resolution during pre-parsing.

Instead, we serialize variables that are assigned as a dense array of markers for each variable. When we delay parsing a function, the pre-parser recreates the variables as it sees them, and we can simply apply metadata to the variables. Now that the function has been compiled, variable allocation metadata is no longer required, and garbage collection is available. Since we only need this function metadata to actually contain the internal functions, most functions don’t even need this metadata, significantly reducing the memory overhead.

By tracing the metadata of functions that have been pre-parsed, we can skip the inner functions entirely.

The performance impact of skipping internal functions is non-linear, as is the overhead of reparsing internal functions. Some sites promote all functions to the top-level scope. Because their nesting level is always 0, the overhead is always 0. Many modern websites, however, actually have deep nesting capabilities. On these sites, we saw significant performance improvements when V8 V6.3 / Chrome 63 enabled the feature. The main advantage is that nowadays the nesting depth of the code of a site is no longer important: any function is pre-parsed at most once, and fully parsed once [1].

Main-thread and non-main-thread parsing time, “skip internal function” optimization before and after startup.

Corruption-invoked function expression

As mentioned earlier, a packer encapsulates module code in a closure that they call immediately, and combines multiple modules into a single file. This provides isolation between modules, allowing them to run as if they were unique code in a script. These functions are essentially nested scripts; These functions are called immediately when the script executes. Wrappers typically provide callable function expressions (IIFEs; Pronounced “iffies”) as parenthesis functions: (function(){… }) ().

Since these functions are needed immediately during script execution, preprocessing them is not the best approach. During the top-level execution of the script, we immediately need to compile the function and fully parse and compile it. This means that the faster the parsing we performed in the previous attempt to speed up startup, the more unnecessary overhead is bound to be incurred at startup.

Why not simply compile the called function, you may ask? While it’s easy for a developer to notice when calling a function, it’s not the case with the parser. The parser needs to make a decision — even before it starts parsing the function! Whether to rush to compile the function or delay compiling. Ambiguities in the syntax make it difficult to simply scan quickly to the end of a function, and the cost quickly becomes similar to that of regular pre-parsing.

So V8 has two simple patterns, which can be identified as the corruption-invoked function expression (PIFEs; Pronounced “piffies”), it is faster to parse and compile a function:

  • If the function is a function expression with parentheses, as follows(function () {... }), we assume it is called. We see the beginning of this pattern, which is(function.
  • Starting with V8 V5.7 / Chrome 57, we also examined the use ofUglifyJSGenerated schema! The function () {... } (), function () {... } (), function () {... } (). As soon as we see! functionOr,,functionIf it currently follows a PIFE, the detection comes into play.

Because V8 compiles PIFEs prematurely, they can be used as feedback for control information [2] that tells the browser what functions are required for startup.

While V8 continues to parse internal functions repeatedly, some developers have noticed that JS parsing has a significant impact on startup. The optimize-JS package converts functions to PIFEs based on static inference. This has a significant impact on V8’s load performance when creating packages. We reproduced these results by running the benchmark provided by optimize-JS on V8 V6.1, just looking at the compressed minimized script.

Parsing and compiling PIFEs prematurely makes cold and hot loads (first and second page loads, measuring the total time of parsing + compiling + execution time, etc.) slightly faster. However, due to the significant improvements to the parser, this gives V8 V7.5 a much smaller performance boost than V8 V6.1.

However, the internal functions are no longer parsed repeatedly, and since the parser is already fast enough, the performance gains from optimize-js are much reduced. In fact, the default configuration of V7.5 is already much faster than the optimized version running on V6.1. Even in V7.5, PIFEs could still be used sparingly for code needed during startup: we avoided pre-parsing because we knew we needed it from the start.

The optimized-JS benchmark results are not fully representative of reality. Scripts are loaded synchronously, and the entire parse + compile time counts as load time. In a real world scenario, you might use the

But there are still costs, especially memory costs, so prematurely compiling everything is not a good idea:

Compiling all your JavaScript code up front can be a significant memory overhead.

While it’s a good idea to add parentheses to the required functions at the beginning (for example, based on starting the analysis), using the optimize-JS package to apply simple static inferences is not a good idea. For example, it assumes that a function is called at the start of compilation and that the function is an argument to a function. However, if such a function that implements an entire module takes a long time to compile, you end up compiling too much. Premature compilation is bad for performance: V8 without delayed compilation can significantly reduce load times. In addition, some of the advantages of optimize-JS come from UglifyJS and other compressor problems that remove parentheses from PIFEs that are not PIFEs, thus removing useful hints that could be applied to modules such as common module definitions – style modules. This is probably an issue that the compressor should fix to get the best performance on browsers that prematurely compile PIFEs.

conclusion

Lazy parsing speeds up startup and reduces the memory overhead of applications that deliver better code than they need. It is necessary to be able to properly track variable declarations and references in the pre-resolver so that pre-resolvers can be done correctly (according to the specification) and quickly. Allocating variables in a pre-parser also allows us to serialize the information about variable allocation so that it can be used in subsequent parsers, so that we can completely avoid pre-parsing internal functions again, avoiding the nonlinear parsing behavior of deeply nested functions.

PIFEs that are recognized by parsers avoid the overhead of having to initialize pre-parsed code immediately during startup. Careful use of PIFEs for boot profiles, or by packers, can also provide a cold start to the speed bump. However, you should avoid unnecessarily wrapping functions in parentheses to trigger such inferences, as this can lead to more code being compiled prematurely, resulting in worse startup performance and greater memory usage.

  1. For memory reasons, do not use V8 to refresh bytecode for a while. If we need to use this code again later, we will reparse and compile it. Since we allow variable metadata to be invalidated during compilation, this will cause the internal function to be parsed again during a delayed recompilation. At this point we recreate the metadata for its inner functions, so there is no need to pre-parse the inner functions within its inner functions again. ↩ ︎

  2. PIFEs can also be thought of as functional expressions based on brief information. ↩ ︎

If you find any mistakes in your translation or other areas that need to be improved, you are welcome to the Nuggets Translation Program to revise and PR your translation, and you can also get the corresponding reward points. The permanent link to this article at the beginning of this article is the MarkDown link to this article on GitHub.

The Nuggets Translation Project is a community that translates quality Internet technical articles from English sharing articles on nuggets. The content covers Android, iOS, front-end, back-end, blockchain, products, design, artificial intelligence and other fields. If you want to see more high-quality translation, please continue to pay attention to the Translation plan of Digging Gold, the official Weibo, Zhihu column.