Reconcile streaming interpreter and streaming compiler usecases

[syg]

As @sebmarkbage and others have pointed out, the deferred-until-invocation-of-function error model is not amenable to streaming interpreters. That model is amenable to streaming compilers, but to be able to interpret a binary AST stream incrementally, errors need to be even more lazy.

It is not clear to me how to reconcile the two use cases. Maximum laziness on errors enables streaming interpreters, but hurts compiled code performance by requiring runtime checks. Per-function laziness means the entire function needs to be inspected before any code can execute.

In the browser world, streaming interpreters is not a compelling use case IMO. However, streaming interpreters is more compelling for an engine specialized only for run-once code (e.g., no JITs).

We should either come up with a technical solution that enables both use cases, or explicitly decide to not support one.

[Yoric]

In terms of performance, I believe that interpreting the toplevel before compiling delayed functions makes lots of sense: the toplevel is executed only once, while functions may be executed more than once. So I would optimize for this use case.

I would say that this use case is at the intersection between a streaming interpreter and a streaming compiler: parse + compile the toplevel, then run it immediately. Or, if the VM doesn't want to compile to bytecode, parse then run.

I suspect that once we have this scenario, we can apply the same strategy recursively for free.

Per-function laziness means the entire function needs to be inspected before any code can execute.

Entire function, including nested functions? If so, we're game over, but I would be a bit surprised by it. What's wrong with doing what we've had in mind so far: assume that Asserted Scopes are true until proven otherwise.

[syg]

Entire function, including nested functions? If so, we're game over, but I would be a bit surprised by it.

Good clarification. I meant not including nested functions.

What's wrong with doing what we've had in mind so far: assume that Asserted Scopes are true until proven otherwise.

The issue is this. We're trying to specify the answers to the following questions: What point should the assertions be deferred to? Does the performance model of that point of deferral for the deferred assertions make sense? Is the mental model easy to understand?

1. For a streaming compiler, deferring to function boundaries made the most sense to me. It's easy enough to reason about. It is also fairly easy to implement in theory: the deferred assertions are all checked at the same time as bytecode compilation. The performance model is that calling functions incur the checking costs for the very first time a function is called; nothing else changes.

2. For a streaming interpreter, you can't defer to function boundaries. Instead, deferred assertions need to be checked as the code executes. Declarations would need to be compiled to run-time checks, etc. In theory this is not much different from a streaming compiler.

The core issue is that since errors are observable, this necessarily means that we have to choose a particular one. Having an implementation-defined time of when errors may be thrown for these deferred assertions is a bad idea, along the general philosophy of JS having as little undefined/under-defined behavior as possible.

If we choose 1, that means we can't do a streaming interpreter as errors would need to be thrown upon first invocation of the function. If we choose 2, that means we can't streaming compilers, as it means we have to throw errors at particular points of execution.

So it seems to me we have to make a choice on which is the use case we want to enable. I believe strongly that enabling streaming compilers is the way to go.

[Yoric]

I agree that we should defer to function boundaries.

I also believe that this will not block us from the following execution model:

1. fetch the toplevel of a function (including immediately executed function expressions);
2. amortize parsing, verification and compilation of this toplevel on top of fetching the rest of the toplevel (i.e. streaming compilation);
3. throw any (Delayed)SyntaxError now;
4. in the absence of (Delayed)SyntaxError, amortize execution of the bytecode for this toplevel on top of fetching/parsing/compiling the rest of the binary (i.e. streaming interpretation).

While this is may not be the ideal, purest, implementation of a streaming interpreter, I believe that this can still be a considerable benefit.

Does this make sense?

[syg]

I don't understand 4. How do you know there will be no deferred SyntaxErrors ahead of time if you're streaming the interpretation of the top level?

[Yoric]

Because I'm actually waiting for the end of 4. before starting actual interpretation. I'm talking of streaming interpretation, but where the unit of streaming is not the opcode, it's the function toplevel.

[syg]

We discussed in a backchannel some more and have agreed on that @Yoric's 1-4 make sense. I've been using "streaming interpretation" to mean a fine-grained streaming execution. To avoid confusing that concept with what @Yoric proposed in 4, he proposed the name "streaming startup", which I like.

The conclusion is we'll strive for streaming compilation and startup, not for finer-grained streaming execution.

[Yoric]

So, we agreed off-github that:

• we cannot reasonably aim for full streaming interpretation;
• we can aim for full streaming compilation;
• we can optimize for something that we'll call "streaming startup", i.e. reaching a stage at which we can start executing the code as soon as we have compiled for the toplevel.

The objective of https://github.com/binast/binjs-ref/issues/86 is to make sure that we can produce a binary that lets us achieve full toplevel compilation as early as possible, typically by moving everything not needed for startup after what is.

We might eventually realize that full streaming interpretation is possible after all, but that's clearly not our objective for the time being.

[guybedford]

Thanks @Yoric for the update here. With "streaming startup" as the current direction, I was wondering if this might also apply to module graphs? That is, graph execution itself should also be able to follow a streaming startup critical path, when all modules in the execution group have completed streaming so far as each dependent module needs for its own critical execution. Perhaps this is an engine-level optimization, but it would be worth ensuring these behaviours play well with eg live binding handling for modules (eg would a concept of deferred live bindings apply when not needed on the critical path?).

The basic scenario that would be most useful to consider I think is imagining a large library from CDN, where there is a small critical startup section, followed by exported function sections. If the application only uses one of the functions, which has already been seen in the stream and in turn has all its bindings ready for execution, then execution might be possible before the full library has completed streaming.

Although perhaps this level of variable tracking across module scopes becomes similar to full streaming at some level, making these directions unsuitable.