Proposal: DOMChangeList

`DOMChangeList` and `DOMTreeConstruction`

Motivation

There are three high-level motivations for this API:

To make it clearer and less error prone to apply a sequence of DOM operations at once, that can support the full gamut of mutations to Elements and Nodes.
For efficiency, to provide an API for constructing a sequence of DOM operations that can be:
1. constructed in a worker and transferred to the UI thread
2. constructed with a minimum of allocations
3. applied in one shot without interleaved user code
To support, in one API, the superset of trees that can be produced using the HTML parser and using the DOM API (the HTML parser supports more tag names, while the DOM API supports more trees, such as custom elements nested inside a table).

This is an initial, minimal version of this API, which could be expanded over time with more capabilities. It should always maintain its goals of predictable, allocation-lite performance, focusing on giving user-space abstractions the capabilities they need for maximum performance.

Concepts

NodeToken

A NodeToken is an opaque value that represents a Node. It can be efficiently transferred from one worker to another.

It serves two purposes:

To represent a Node that already exists in another worker, and can serve as the starting point of a series of mutations expressed in a DOMChangeList.
To represent an intermediate Node that was produced as part of the process of building a DOMChangeList.

Applying a Change

The intent of this API is to have these performance characteristics:

Creating a change list (DOMTreeConstruction or DOMChangeList) significantly reduces GC-managed allocations compared to the current DOM APIs.
Applying a change list should not create intermediate JavaScript wrappers for the DOM objects it creates, which should reduce costs.
It is possible to run the JavaScript code necessary to construct a change list in a worker, and apply it on the UI thread with minimal additional work or allocations in JavaScript.
The API creates a single immutable blob of instructions to pass to the engine, which is intended to avoid JavaScript side effects while the application proceeds. (as Boris Zbarsky said in his comment about proposals in this space, "that would simplify both specification and implementation (in the sense of not having to spell out a specific processing algorithm, allowing parallelized implementation, etc).")
It is reasonable to assume that the builder APIs could be exposed to WebAssembly.

If there is some reason that a concrete implementation of this design might not be able to accomplish these goals, it's almost certainly something we should discuss.

Details

DOMTreeConstruction

Note: Use of TypeScript generics notation in the details of this proposal does not intend to imply any additional type checking. It is simply a way to annotate which kinds of node a particular node tokens is intended to produce for clarity. This proposal expects checking at the point of application (e.g. appending a node to a non-element node doesn't make sense and would be an error at the time of application). At present, this proposal does not assume that errors in the change list cause previously applied operations to be rolled back; that is listed as an open question below.

// you can create a NodeToken in the UI thread and transfer it into
// a worker that constructs the DOMChangeList or DOMTreeConstruction.
partial interface Node {
  getToken(): NodeToken<this>;  
}

interface Bounds {
  firstNode: NodeToken<Node>;
  lastNode: NodeToken<Node>;
}

partial interface Element {
  // this has the same semantics as insertBefore, but takes a `DOMTreeConstruction`
  insertTreeBefore(element: Element, tree: DOMTreeConstruction, reference: Node): Promise<AppliedChanges>;
}

// The intent of this object is to allow engines to clean up any bookkeeping maps they
// need to track `NodeToken`s once the `AppliedChanges` is GCed.
interface AppliedChanges {
  // this allows code that created a ChangeList to get the actual
  // node they were creating so they can add listeners or change
  // the node later.
  getNode<T extends Node>(t: NodeToken<T>): T;
}

// DOMTreeConstruction is transferrable, and is backed by raw bytes. This
// allows trees to be constructed in workers.
interface DOMTreeConstruction {
  openElement(name: string, ns: string = "html"): NodeToken<Element>;
  closeElement();

  setAttribute(name: string, value: string = "", ns: string = ""): void;
  appendText(text: string): NodeToken<Text>;
  appendComment(text: string): NodeToken<Comment>;
  appendHTML(html: string): Bounds;
}

DOMChangeList

partial interface Document {
  applyChanges(changes: DOMChangeList): Promise<AppliedChanges>;
}

// DOMChangeList is transferrable, and is backed by raw bytes. This
// allows change lists to be constructed in workers.
interface DOMChangeList {
  /// traverse
  nextSibling(n: NodeToken<Node>): NodeToken<Node | null>;
  previousSibling(n: NodeToken<Node>): NodeToken<Node | null>;
  firstChild(n: NodeToken<Node>): NodeToken<Node | null>;
  lastChild(n: NodeToken<Node>): NodeToken<Node | null>;
  parentNode(n: NodeToken<Node>): NodeToken<Element | null>;

  /// create
  createElement(name: string, ns: string = 'html'): NodeToken<Element>;
  createText(text: string): NodeToken<Text>;
  createComment(text: string): NodeToken<Comment>;

  /// update
  setAttribute(el: NodeToken<Element>, name: string, value: string = '', ns: string = ''): void;
  updateTextData(n: NodeToken<Text>, text: string): void;
  updateCommentData(n: NodeToken<Comment>, text: string): void;
  remove(n: NodeToken<Node>): void;

  /// append
  appendChild(el: NodeToken<Element>, node: NodeToken<Node>): void;
  appendTree(el: NodeToken<Element>, tree: DOMTreeConstruction): void;

  // this unifies the various HTML-based APIs in the DOM; the return value is
  // a token corresponding to the start and a token corresponding to the end of
  // the inserted tree which can be reified after application.
  //
  // IMPORTANT NOTE: The HTML is parsed during application, not when
  // it is added to the change list.
  insertHTMLBefore(node: NodeToken<Node>, html: string): [NodeToken, NodeToken];
}

Example

Using the usual DOM API:

let article = document.getElementById('main-article');
let text = node.firstChild;
text.textValue = "Hello world";
node.setAttribute("data-active", "yes");
node.removeAttribute("data-pending");

Using the ChangeList API:

let articleToken = document.getToken(document.getElementById('main-article'));

let changes = new DOMChangeList();
let textToken = changes.firstChild(token);
changes.updateTextData(textToken, "Hello world");
changes.setAttribute(articleToken, "data-active", "yes");
changes.removeAttribute(articleToken, "data-pending");

document.applyChanges(changes);

FAQ

Is this actually faster?

Don't you still have to create all of the DOM nodes anyway? If so, why is it cheaper?
Isn't DOM pretty fast in modern browsers already?

The intent of this API is to create a low-level interface that is as close as possible to the underlying implementations. It attempts to avoid introducing new costs while reducing a number of paper-cuts that exist in today's usage.

This API creates DOM nodes in the engine, but it does not need to create JavaScript wrappers. Experiments with deep cloneNode show that skipping those wrappers provides a performance benefit, but cloneNode() can't satisfy as many use-cases as this API.
It allows the construction of the set of mutations to occur separately from the application (or even in a worker), keeping the sensitive work that limits 60fps to a minimum.
Since applying changes is asynchronous, the full change list can be applied in batches that avoid blocking interaction (especially scroll). If the browser reaches its budget, it can interleave some work to keep the UI interactive and pick up the mutation process afterward. In short, the API should allow browsers to experiment with more scheduling strategies.
It encourages good staging practices, eliminating some of the major causes of layout thrash (see the next section).

Isn't the real issue that people are interleaving DOM manipulation and layout?

That is certainly a major issue, and this API puts developers on the path to success by encouraging them to stage DOM manipulation work separately from APIs that can trigger painting or layout.

Because the API guarantees that no user script can interleave during the application of changes, there is no way to "mess up" and trigger an immediate flush of any deferred work.

Unresolved Questions

The current state of this API allows failures to occur during the processing of a change list, and does not require engines to roll back earlier changes (rolling back changes like "remove an iframe" may not be trivial to implement). Would engines prefer to roll back changes?
Should we support APIs like ClassList and the style property through this API? It may be difficult to represent these kinds of changes with the operations already proposed (since this API does not allow direct imperative access to the DOM), and a few additional APIs probably wouldn't do damage to the constraints.
Are there other optimizations that could be performed by engines? For example, Luke Wagner suggested that a parameterized version of this API could work like "prepared statements" in SQL, allowing engines to do up-front work to optimize the access and mutation patterns for application. What can we do to make this API more hospitable to hypothetical optimizations like those?

This introduces quite a few concepts for manipulating the DOM for something that's ultimately an optimization. This seems like an optimization that, with slightly an improved DOM API could accomplish the exact same thing with only minor additions to the API (perhaps ~~~a suspend and resume layout plus~~~ a way to mix elements so you can generate them external to the current thread and have the rendering engine apply them at once similar to your proposal but significantly less complex).

This introduces quite a few concepts for manipulating the DOM for something that's ultimately an optimization.

... perhaps a suspend and resume layout ...

What would the existing APIs that trigger a layout flush do while layout was paused? Would pausing layout force an immediate layout flush to update all layout caches? If not, how would they compute the "old" layout once mutations have begun?

One of my concerns with proposals to augment the existing DOM APIs with some sort of transaction is that you have to decide what happens to all of the DOM's APIs while the transaction is in flight. In contrast, the proposed API is a closed set of operations, disallowing any other interleaved operations, making it possible to understand the complexity of the entire API.

Great to see this! I'm coming at this in comparison to Dru's proposal at https://github.com/drufball/async-append/blob/master/EXPLAINER.md, so let me share some thoughts:

As far as I can tell this proposal focuses mostly on trying to minimize allocations (but see below) and on providing a proxy API that can be used in a worker, instead of focusing on allowing chunking and scheduling of parsing/style/layout/paint as Dru's proposal does. I can't tell at first glance whether it can serve both purposes, or whether its design prevents that. There's a brief paragraph under "Is this actually faster?" number 3 that indicates it is intended to be compatible, but I'll defer to the Blink engineers.

I think the proposal might have a misapprehension about how DOM nodes and wrappers are related. Remember that wrappers are not created until they are accessed. With this in mind it seems like the proposal just substitutes one set of wrapper allocations (NodeTokens and DOMTreeConstructions) for another (Nodes and DocumentFragments). Looking at the example code seems to bear this out; counting wrapper allocations it seems to have the same amount as normal DOM manipulation code. (And remember a wrapper is just a pointer; a wrapper to a NodeToken and a wrapper to a Node are both the same cost.) If you assume the DOM nodes will eventually exist anyway, as Yehuda discusses, Yehuda's proposal actually seems to have more allocations: NodeToken backing + NodeToken wrapper + Node backing, vs. Dru's proposal which has Node wrapper + Node backing.

One concern I have about the idea of running these things in a worker is that the IPC involved in getting back to the main thread (in the case of hundreds or thousands of nodes/nodetokens) would probably be a significant cost. I'm not sure whether it would be greater than or less than the cost of just doing the work on the main thread; similarly I am not sure whether the IPC would be significant enough to cause jank. But maybe all you have to IPC is a single memory location of the queue in which case it is presumably fine.

So, going through the three high-level motivations Yehuda lists:

Both proposals make it clear and less error prone to apply a sequence of DOM operations at once, through similar queue-then-commit systems. Both support the full gamut of mutations to Elements and Nodes, with Dru's doing so by just allowing you to use those normal DOM APIs and Yehuda's by creating new versions of (most of) them that operate on analogous data structures.
This bullet is weird since it doesn't list actual use cases, but instead specific ideas as to how good performance would be achieved, despite lack of data showing that these proposed solutions actually help. But anyway, going through each in turn:
1. Yehuda's proposal allows the sequence of operations to be constructed in a worker and transferred; Dru's does not.
2. Yehuda's proposal has slightly more allocations, as discussed aboved.
3. Both have the queue-then-commit structure.
Both support the union of the trees that can be produced using the HTML parser and using the DOM API, Dru's by using the HTML parser directly (innerHTML/outerHTML) and Yehuda's presumably by e.g. allowing openElement to take more element names than createElement does (although I couldn't find where this is specified). We could of course try to expand createElement again; nobody's had the motivation so far, but maybe this will be the last straw.

Also going through the "Applying a Change" bullets:

Neither proposal reduces GC-managed allocations compared to current DOM APIs, as discussed above; Yehuda's slightly increases it.
Both proposals avoid creating intermediate JavaScript wrappers in most cases (e.g. using innerHTML, textContent, setAttribute). Both proposals do not avoid creating wrappers for other cases; e.g. creating an element requires creating a NodeToken wrapper1 in Yehuda's and a Node wrapper in Dru's.
As above, Yehuda's proposal works in a worker with minimal extra work and a slight amount of extra allocations in JavaScript at commit time (but perhaps quite a lot in the browser; I am not sure). Dru's proposal does not run in a worker.
Both proposals create a single immutable (?) blob of instructions to pass to the engine (the queue), and do not allow JavaScript side effects to interleave during a commit of the queue.
Both proposals could equally be exposed to WebAssembly since both would be specified using Web IDL.

So it seems to me like the proposals are very similar with the main divergence being the desire to allow building the queue of mutations in a worker in Yehuda's proposal, which necessitates creating a parallel object hierarchy in order to build the queue over in the worker, before then transferring the queue to the main thread before (or during?) a commit.

To me it feels like an empirical question whether the gains from building the parallel DOM-like tree in the worker instead of building a DOM tree in the main thread outweigh the costs of transferring it. There's also the empirical question of whether building a DOM tree in the main thread actually takes long enough to cause jank; if it takes e.g. 1-2 ms for thousands of nodes, then it'd probably be best to just eat the cost and avoid the conceptual burden of introducing a parallel object hierarchy, or at least save it for a future extension once we have gotten rid of all the more low-hanging perf fruit and are grubbing for a few milliseconds.

What would the existing APIs that trigger a layout flush do while layout was paused? Would pausing layout force an immediate layout flush to update all layout caches? If not, how would they compute the "old" layout once mutations have begun?

No a pause wouldn't flush only a resume. This is how other frameworks operate. Regardless I struck the suspend / resume from my comment as it unnecessarily complicated my position.

One of my concerns with proposals to augment the existing DOM APIs with some sort of transaction is that you have to decide what happens to all of the DOM's APIs while the transaction is in flight. In contrast, the proposed API is a closed set of operations, disallowing any other interleaved operations, making it possible to understand the complexity of the entire API.

Transaction capability typically takes on a begin then rollback or commit pattern. This proposal doesn't do that. This proposal creates multiple new APIs to do what the existing DOM APIs can already do today except that it applies them in bulk when you're finished.

This proposal, in my opinion, could be significantly simplified by simply making it: document.appleChanges(source, destination);. Obviously you'd need to update how web workers work if you want to build a DOM tree in it but you'll have to do something similar anyway in your proposal for the Token pseudo elements.

The destination is the HTML node to apply all your changes to and the source is your separately built DOM. No reason the underlying engine couldn't handle all the complexity your introduced.

The DOM API is inelegant; I don't think it's a good idea to incorporate increased complexity for a theoretical optimization. If possible, re-use or work towards a better designed API that lends itself better to transactions. Transactions would be pretty cool.

@domenic

@domenic most of the "allocations" in this proposal are not actually allocations. Integers are created which should be much more light-weight than actual objects and don't impact GC and such. (And also, I think it might be a good idea to define DOMChangeList and DOMTreeConstruction as ECMAScript-style objects. They really shouldn't perform much validation and the more browsers can inline the better.)

@KrisSiegel the API is not meant to be elegant. It's meant to be fast. Having discussed this with implementers it seems unlikely we'll get proper transactions. Doing that efficiently would be very hard and unlikely to materialize anytime soon.

@annevk

the API is not meant to be elegant

@annevk I don't think the WHATWG should consider an API only for speed. The DOM APIs are public for web developers to use so usability of APIs shouldn't be forgotten or tossed away (this is how we ended up with jQuery and a new front end framework every two weeks). The DOM API is inelegant enough as is. I would like to see more re-usage of existing APIs where possible (which I see no reason why you couldn't do so while still accomplishing the goals of the proposal). I'm curious how efficient the passing of node objects to and from web workers would be. I could see that being useful in more scenarios than just this one.

Yeah I wouldn't be expecting transactions for any type of GUI state. It would be cool but yeah implementing it efficiently while maintaining generic capabilities is very difficult.

Transactions is pretty much impossible due to how <iframe> and such work. While we should make the DOM more elegant, we should also offer fast paths for advanced applications. Passing node objects around would not be efficient and getting node objects in workers is also something that's too hard (no implementation is anywhere near ready for that, if ever). This proposal, which avoids all that, is really our best bet to get something done in that area.

@drufball

cc/ @drufball @esprehn @n8schloss

@domenic has summarized some of my thoughts up pretty well, but I'd just like to add my 2c. :)

This proposal has three parts that are potential performance benefits.

(1) Worker Construction of Tree.
Having something that is transferrable sounds great. Moving more script logic off the critical path is something that authors have typically struggled with.

It may be worth thinking about this part of the problem as a separate API which integrates nicely with this proposal, and regular DOM APIs?

(2) Tree Construction
We haven't seen in traces that we've performed that the bindings cost is the bottleneck here. For this part of the proposal we'd really love to see some data on this to be convinced that this is an issue worth solving.

@wycats , you mentioned some experiments with cloneNode you did? Do you have data on this?

It looks like that this is a pretty simple API to actually implement (if you are just worried about the bindings type cost); getting numbers from someone wouldn't be too hard?

If there is a significant performance difference: this should then be compared to a polyfill of the current DOM API on top of this API. I.e. when a sync DOM API is called, perform the mutation list synchronously.

Blink's implementation has the ability to create IDL APIs that live in javascript instead of cpp. If this is a huge performance win, then theoretically engines could change their implementations to mitigate this.

Again, we really need numbers to be convinced here.

(3) applyChanges
It will soon be possible in blink for us to styleRecalc separately from layout and be able to "smear" work for a particular DOM mutation over multiple frames.
This was the initial motivation behind asyncAppend; the fact that when you append DOM, it will typically jank that frame as more work is needed to be done than is possible in one frame.

We think it's really valuable for engines to be able to resolve applyChanges multiple frames after the initial request.

One thing that I think is missing in this API is the "DoItNow" button. I.e. calling this api would perform all the changes synchronously like the current DOM APIs.

As an example, say your UI can tolerate 100ms (~6frames) of the async DOM not appearing, but after that it would prefer to jank the main thread, as opposed to delaying further. A sync "commit" function would do this.

One way to do this with the current API would be:

changes = new DOMChangeList();
/* build up changes here */

changes.execute().then(() => {
  // changes aren't actually performed until you call "commit" here?
  // e.g. all the style/layout/etc work is performed. "commit" just makes it appear in the DOM tree.
  changes.commit();
});

requestAnimationFrame(() => {
  changes.commit(); // Promise above is now not resolved, as already done "commit".
});

We see really large benefits from this part. ^-^.

It looks like that this is a pretty simple API to actually implement

That was my intent. Getting many of the benefits people are after with a simple-to-implement API should be valuable.

We think it's really valuable for engines to be able to resolve applyChanges multiple frames after the initial request.

That is definitely the intent of this proposal. By making applyChanges async, engines can choose to smear the work across multiple frames, without janking user interactions like scroll. (making it async gives the engine's scheduler control over the timing.)

One thing that I think is missing in this API is the "DoItNow" button. I.e. calling this api would perform all the changes synchronously like the current DOM APIs.

Good request! I'd have no problem adding it if engines thought it wouldn't introduce new problems 😄

We see really large benefits from this part. ^-^.

Great!

@annevk

@annevk

most of the "allocations" in this proposal are not actually allocations. Integers are created which should be much more light-weight than actual objects and don't impact GC and such. (And also, I think it might be a good idea to define DOMChangeList and DOMTreeConstruction as ECMAScript-style objects. They really shouldn't perform much validation and the more browsers can inline the better.)

Hmm, can you expand on this? I didn't see any integers in this proposal. Going through the sample code:

// Usual DOM API:
let article = document.getElementById('main-article'); // Node wrapper (1)
let text = node.firstChild; // Node wrapper (2)
text.textValue = "Hello world"; // no allocations
node.setAttribute("data-active", "yes"); // no allocations
node.removeAttribute("data-pending"); // no allocations

// ChangeList API:

let articleToken = document.getToken(document.getElementById('main-article')); // Node wrapper + Token backing + Token wrapper (3)

let changes = new DOMChangeList(); // ChangeList backing + ChangeList wrapper (5)
let textToken = changes.firstChild(token); // Token backing + Token wrapper (7)
changes.updateTextData(textToken, "Hello world"); // no allocations
changes.setAttribute(articleToken, "data-active", "yes"); // no allocations
changes.removeAttribute(articleToken, "data-pending"); // no allocations

document.applyChanges(changes); // promise (8)

I see 2 allocations for normal DOM APIs (both simple wrapper allocations, which are "an integer" (pointer) size each) and 8 allocations for the ChangeList example. And that isn't including the transfer cost.

@lukewagner

Great to see this! I'm coming at this in comparison to Dru's proposal at https://github.com/drufball/async-append/blob/master/EXPLAINER.md

I also reviewed that in detail before I began work on this proposal.

As far as I can tell this proposal focuses mostly on trying to minimize allocations

That is certainly an important characteristic of this proposal. It also has several other goals, both related to efficiency and expanding capabilities. (one example is supporting the superset of the HTML syntax and the DOM API, which I talk about in the proposal; another is allowing the end-developer to directly control the staging of work across threads by using workers).

(but see below)

I'll reply inline.

and on providing a proxy API that can be used in a worker

I don't think you should see ChangeList as a "proxy", but rather as a collection of instructions that can be freely transferred until it's applied.

instead of focusing on allowing chunking and scheduling of parsing/style/layout/paint as Dru's proposal does

Since the application of a ChangeList is asynchronous, the benefits to the browser's scheduling algorithm is more-or-less equivalent to Dru's proposal. ChangeList supports many more operations, and allows them to be performed in a batch, which should further increase the scope of the benefit to authors.

I can't tell at first glance whether it can serve both purposes, or whether its design prevents that.

This is something I spent a lot of time talking to @lukewagner, @smaug--- and @annevk about, and our intent was for this API to serve both purposes. As I said in the proposal: "If there is some reason that a concrete implementation of this design might not be able to accomplish these goals, it's almost certainly something we should discuss."

There's a brief paragraph under "Is this actually faster?" number 3 that indicates it is intended to be compatible, but I'll defer to the Blink engineers.

I'm very eager to hear from them about this. I'd be very happy to have a call with anyone interested in this area as well.

I think the proposal might have a misapprehension about how DOM nodes and wrappers are related. Remember that wrappers are not created until they are accessed.

This particular constraint was one of the most important aspects of this design, and I spent a lot of time thinking about it and discussing the details with others.

The intent of NodeToken is that it can be represented as a simple internal value (e.g. an representing the n'th object to be allocated in this transaction) but that the nature of that representation is not directly exposed to users. The only way in which these values can be reified into Nodes is through AppliedChanges. I've spoke with some engineers at Mozilla about how to structure the API to allow it to work as a simple value, and would love to discuss it further with engineers who work on Blink.

Looking at the example code seems to bear this out; counting wrapper allocations it seems to have the same amount as normal DOM manipulation code. (And remember a wrapper is just a pointer; a wrapper to a NodeToken and a wrapper to a Node are both the same cost.) If you assume the DOM nodes will eventually exist anyway, as Yehuda discusses, Yehuda's proposal actually seems to have more allocations: NodeToken backing + NodeToken wrapper + Node backing, vs. Dru's proposal which has Node wrapper + Node backing.

Both proposals make it clear and less error prone to apply a sequence of DOM operations at once, through similar queue-then-commit systems.

Both support the full gamut of mutations to Elements and Nodes, with Dru's doing so by just allowing you to use those normal DOM APIs and Yehuda's by creating new versions of (most of) them that operate on analogous data structures.

It looks like Dru's proposal creates several new async APIs for existing operations. It also postulates a "wrapper" that could be used with the regular APIs. I understood Dru's proposal as an early exploration with several different possible directions; can you flesh out which of those directions your comments are talking about?

Both support the union of the trees that can be produced using the HTML parser and using the DOM API, Dru's by using the HTML parser directly (innerHTML/outerHTML) and Yehuda's presumably by e.g. allowing openElement to take more element names than createElement does (although I couldn't find where this is specified). We could of course try to expand createElement again; nobody's had the motivation so far, but maybe this will be the last straw.

From my original statement about the union of trees: "the HTML parser supports more tag names, while the DOM API supports more trees, such as custom elements nested inside a table)."

DOMChangeList also supports using the HTML parser, but the HTML parser limits which nodes can be made children of certain elements. We could perhaps fix createElement to support the full set of element names supported by the HTML parser, and that would address this benefit of the ChangeList proposal.

To me it feels like an empirical question whether the gains from building the parallel DOM-like tree in the worker instead of building a DOM tree in the main thread outweigh the costs of transferring it. There's also the empirical question of whether building a DOM tree in the main thread actually takes long enough to cause jank;

I have heard this thinking before and I think it might misapprehend the reasons people want to do build DOM trees and calculate DOM mutations in a worker.

It's not so much shrinking the cost of the DOM work, but rather all of the JavaScript work that is necessary to calculate the needed mutations. In practice, a lot of application work is done on the UI thread simply because of the close proximity of the DOM APIs.

It is of course possible to implement some of this strategy as a user-space library, but not all of it. In user-space, applying a change set is inherently single-threaded, for example. The process of deserializing a transferred ChangeList would have to choose between interleaving the DOM operations or deserializing them into an intermediate data structure, both of which would introduce new costs that the native implementations would not need.

And that's all assuming that a user-space library has enough primitives to do an efficient job at the limit. The basic idea behind this API is to provide a low-level primitive that libraries can use to build up different useful libraries with different tradeoffs, and start lower level than the current set of primitives.

There are many small paper-cuts that the ChangeList proposal addresses in one, fairly contained proposal. It attempts to create an API that, when used, has noticeably fewer common gotchas for web developers, and does not require library, framework or application developers to reverse engineer which APIs produce hazards, and keep that knowledge up to date as implementations change.

I am especially interested in feedback from implementors that there is something about this proposal that is difficult to implement, or that would make reasonable initial implementations slower than the equivalent use of DOM APIs. Any suggested changes to this proposal that would improve

@wycats

@wycats We really need numbers for point (2) - (bindings related costs are really the problem) before going too deeply into API design however.

Without numbers on if this will actually get us a significant performance benefit, it's impossible to tell if this is the right design or not.

I.e. we could get a simpler API if this wasn't a significant problem. For example just the asyncAppend APIs for (3) - (performing style/layout work async), and a "WorkerNode" API separately.

Are you able to get numbers for (2)? Or work with someone to get numbers for this?

The intent of NodeToken is that it can be represented as a simple internal value (e.g. an representing the n'th object to be allocated in this transaction) but that the nature of that representation is not directly exposed to users. The only way in which these values can be reified into Nodes is through AppliedChanges. I've spoke with some engineers at Mozilla about how to structure the API to allow it to work as a simple value, and would love to discuss it further with engineers who work on Blink.

Well, one issue with the above proposal is that it uses a type notation (TypeScript?) that implies type checking. This would necessitate creating Web IDL interfaces in order to get type checking so that you couldn't pass arbitrary values. It in fact uses a generics notation that implies we'd need (when converted to Web IDL) TextNodeToken, CommentNodeToken, ElementNodeToken, etc. So even if it's conceptually a simple internal value, it would need to be implemented as several wrappers + backing classes where the backing classes have those simple internal values.

It looks like Dru's proposal creates several new async APIs for existing operations. It also postulates a "wrapper" that could be used with the regular APIs. I understood Dru's proposal as an early exploration with several different possible directions; can you flesh out which of those directions your comments are talking about?

What I meant is that both of Dru's proposed APIs have minimal extra surface. For example they allow you to create Nodes and e.g. set their text data or attributes using the usual DOM APIs, whereas yours involves creating NodeTokens and using the parallel interface for such operations. In other words, instead of creating a parallel DOM API with a full parallel object hierarchy of NodeTokens and APIs that operate on them, Dru's proposal only duplicates the few APIs necessary for queue-building.

It's not so much shrinking the cost of the DOM work, but rather all of the JavaScript work that is necessary to calculate the needed mutations. In practice, a lot of application work is done on the UI thread simply because of the close proximity of the DOM APIs.

This is a great point; it's good to bring it up. It certainly makes the empirical question harder, but still worth investigating.

or that would make reasonable initial implementations slower than the equivalent use of DOM APIs

I've given some fairly concrete feedback about the increased allocation cost, which hopefully can make this clear. I'll defer to those more involved on the implementation side to say more.

Well, one issue with the above proposal is that it uses a type notation (TypeScript?) that implies type checking. This would necessitate creating Web IDL interfaces in order to get type checking so that you couldn't pass arbitrary values. It in fact uses a generics notation that implies we'd need (when converted to Web IDL) TextNodeToken, CommentNodeToken, ElementNodeToken, etc. So even if it's conceptually a simple internal value, it would need to be implemented as several wrappers + backing classes where the backing classes have those simple internal values.

The intent of the TypeScript notation was just to show clearly what kind of NodeToken I expect each part of the API to produce. The only time I expect any kind of checking to be mandatory is when applying the ChangeList, because for example it would be a bug to appendChild a Node to another Node or no node at all.

What I meant is that both of Dru's proposed APIs have minimal extra surface. For example they allow you to create Nodes and e.g. set their text data or attributes using the usual DOM APIs, whereas yours involves creating NodeTokens and using the parallel interface for such operations. In other words, instead of creating a parallel DOM API with a full parallel object hierarchy of NodeTokens and APIs that operate on them, Dru's proposal only duplicates the few APIs necessary for queue-building.

Thanks for the clarification. One of the problems I'm hoping to address is that not all operations are safe or reasonable to use inside a transaction, and certainly many operations are not safe if you want the resulting change list to be transferrable. By starting with a minimal API that nontheless covers mutations of the DOM as a data structure, we can build up an API that doesn't have surprising or problematic behavior.

I don't expect to need a much larger set of lowest-level APIs; Much of DOM1-4 is described in terms of a lower-level set of primitive DOM operations, and my intent is to flesh out the base layer of those APIs in a way that would both work across workers and support asynchronous application of the change list, smart scheduling by the engines, and avoid user-space interleaving of dangerous operations.

@wycats

I.e. we could get a simpler API if this wasn't a significant problem. For example just the asyncAppend APIs for (3) - (performing style/layout work async), and a "WorkerNode" API separately.
Are you able to get numbers for (2)? Or work with someone to get numbers for this?

I've spoken with Bill McCloskey at Mozilla, who has an intern looking into building an initial implementation of this proposal. Since I don't work at Mozilla, I obviously can't hold them to this, but hopefully we'll see some useful results from their work. But still, it doesn't seem like it should be necessary to implement a feature to discuss general performance implications of the design. Generally when we find ourselves getting close to a broad-strokes design that people find promising, that's when implementation work starts and we start getting more fine-grained performance feedback.

@wycats , you mentioned some experiments with cloneNode you did? Do you have data on this?

I can give more information later, but the TLDR is:

Instead of building up DOM and interleaving dynamic work, Ember has experimented with (and shipped, as part of Glimmer 1) an optimization that uses cloneNode for templates and fills in the dynamic content by doing an optimized walk to the dynamic nodes.

The entire benefit of this optimization is to avoid reifying static nodes in JavaScript, and we saw very significant improvements to templates with minimal dynamic content (and therefore shipped the optimization). We still need to walk through some static nodes to reach the dynamic ones, and the AppliedChanges API is intended to limit the number of reified nodes to precisely the dynamic ones that may need to be changed.

@wycats

@wycats To be specific, one thing that I'm really interested in, which this proposal does not cover, is event handling and I could really use your input on that if you have any thoughts.

@Gozala

@Gozala what's the easiest way to get in touch?

@wycats

@wycats I've being noticing you at MozPDX fairly often, maybe next time you're there we can chat ? Alternatively IRC, you can find me as @Gozala on both freenode and moz.

I looked into the concerns around NodeToken being an integer (or number). For the DOMTreeConstruction idea it can be an integer. The integers get returned as you use DOMTreeConstruction. The moment you turn those integers into nodes using getNode(), there's a reference to DOMTreeConstruction available and any lookup only happens within that object. An implementation could store a map of integers to nodes on DOMTreeConstruction the moment nodes are created as part of insertTreeBefore(). As these integers are therefore entirely self-contained, this even paves the path toward DOMTreeConstruction being serializable and network-transferable. To ensure we don't have to keep that map alive forever we could deterministically empty it by .then()'ing the returned promise from insertTreeBefore(). Those details can be fiddled with, this just shows it's viable.

DOMChangeList is trickier as the integers can also represent nodes in an existing tree (via getToken(), which is listed under DOMTreeConstruction in OP, but is not part of it as no method takes a NodeToken there), in a different thread. That means the integers for DOMChangeList need to be unique within an agent cluster and are probably not suitable for network-transfer, ever. It also means they need to be long-lived as they need to be able to transfer across threads. The fogeability problem I would address by when looking up the node corresponding to an integer, also ensuring that its node document is identical to the document upon which applyChanges() was invoked. And as said before for any instructions that are incorrect we'd abort, leaving you with a potentially broken tree as we cannot do transactions (see upthread).

(Given the nature of integers in DOMChangeList I suspect there would need to be some requirement for them to be random to avoid fingerprinting.)

So in conclusion I think both designs are viable.

I think it's worth pointing out this experimental library I just put together: https://github.com/AshleyScirra/via.js

This allows full access to all DOM APIs using Proxys. It effectively builds an internal list of DOM commands and posts them to the main thread to be carried out. It happens entirely in JS land. I think its main advantage over DOMChangeList is it allows you to use all APIs the same way you do in the DOM, rather than a limited tree-construction subset with its own API. For example you can do div.style.fontWeight = "bold" from a worker, or make use of mainthread-only APIs like the Web Audio API from a worker. Also the performance is actually kind of reasonable (it's not as terrible as I thought it might be, at least).

The main problem is that it leaks memory. GC is not observable so it's not possible to identify when the placeholder Proxy objects on the worker get collected and drop their corresponding references on the main thread. I think this can be solved with a special WeakKey object which still doesn't make GC observable: https://discourse.wicg.io/t/a-way-to-the-use-dom-in-a-web-worker/2483/2?u=ashleyscirra

If I read this proposal right, it sounds like this WeakKey idea is like NodeToken but generalised to represent any DOM object at all. This significantly broadens the use cases it covers. For example we want to move our entire HTML5 game engine in to a worker, but the lack of APIs like Web Audio is a much bigger problem than whether or not we can create nodes. Via.js lets you do both: build up lists of DOM commands, and access arbitrary APIs only present on the main thread.

Could I get some sort of status update on this concept in general? (Evolutions, meeting notes, etc.?) Haven't really heard or seen anything about it anywhere, either here or on the WICG discourse. (I'm not active on any of the W3C/WHATWG mailing lists, though.)

There's no active mailing list. There was a meeting at a Mozilla All Hands, but that wasn't really conclusive one way or another. The main problem here is lack of implementer interest.

I wrote a blog post that covers some of the options to better support implementing this entirely in a library: https://www.scirra.com/blog/ashley/38/why-javascript-needs-cross-heap-collection

@annevk

@annevk Sorry, I meant any of the W3C/WHATWG mailing lists. (I edited my comment accordingly.)

Also, I'm not a huge fan of the API proposed - it's a bit too verbose and too much of a shotgun for something that's really just performing transactions on nodes. I'd personally prefer there was a way to just force browsers to batch something without having changes exposed to the main thread until the next animation frame, and a way to run changes in the layout pass to reduce the impact of style recalcs (which account for 90% of the perf issues with DOM frameworks).

Edit: Hidden for easier scrolling

Here's my thought on such an API, one that's a bit less ambitious:

// `execute` runs after animation frames, after all previous transactions have been
// executed, but before intersection observers have been run. Any transactions started
// here are deferred to the *next* animation frame.
//
// When `execute` called, if any properties of a node all of these are true, then an
// `InvalidStateError` should be thrown:
// 1. The node being mutated is in the calling document.
// 2. The node is live, or would have been made live in the transaction.
// 3. UI-visible attributes of that node are read/modified, including ones like
//    `parentNode` and even if indirectly (like in a transaction).
// 4. The node *is not* in `read` (if read) or `write` (if modified).
dictionary LayoutOptions {
    AbortSignal? signal;
    sequence<Node> read = [];
    sequence<Node> write = [];
    // I know this is invalid syntax, but `this` is supposed to be the layout options object
    Promise<any>? execute();
}

// Transactions assume the state right after the animation frames are run *are* the
// initial state - they don't actually save anything first, and they act as if the
// operations work on the state after animation frame callbacks run.
[Exposed=Window, Constructor]
interface DOMTransaction {
    void insertBefore(ParentNode node, ChildNode? node, ChildNode next);
    void insertAfter(ParentNode node, ChildNode? node, ChildNode prev);
    void replace(ChildNode node, ChildNode? other);
    void setAttribute(Element elem, DOMString key, DOMString? value, DOMString? ns);
    void toggleClass(Element elem, DOMString classes, boolean force);
    void setStyle(HTMLElement elem, DOMString key, DOMString? value);
    void setNodeValue(Node node, DOMString value);
    // The tree is locked between when animation frames and intersection observers
    // would be run. The fulfillment value is that of `callback.execute()` or
    // `undefined` if the method wasn't passed.
    Promise<any> end(optional LayoutOptions? options);
}

There's a few specific omissions and design points with my proposal here that I thought I'd note:

Most DOM interactions can be reduced to these.
- Append: transaction.insertAfter(parent, null, node)
- Prepend: transaction.insertBefore(parent, null, node)
- Insert before: transaction.insertBefore(parent, next, node)
- Insert after: transaction.insertAfter(parent, prev, node)
- Replace: transaction.replace(node, other)
- Remove: transaction.replace(node, null)
- Set attribute: transaction.setAttribute(node, key, value, ns)
- Remove attribute: transaction.setAttribute((node, key, null, ns)
- Set class: transaction.toggleClass(node, classes, true)
- Remove class: transaction.toggleClass(node, classes, false)
- Set node value: transaction.setNodeValue(text, value)
- Set style: transaction.setStyle(elem, key, value)
- Remove style: transaction.setStyle(node, key, null)
- Set id/className/etc.: set that attribute
The few that can't could be handled in the LayoutCallback without having to spend an extra animation frame. (It also exists for the sake of refs, like what most vdom frameworks have some variant of.)
I chose to include both, and only, insertBefore and insertAfter as it's much simpler than the half dozen existing methods, and it works better with single-pass updates.
I chose to exclude properties that aren't available via normal DOM attributes because there's generally nothing left to do.
This is technically polyfillable without an explosion of code short of the throwing errors part. It would require wrapping requestAnimationFrame and cancelAnimationFrame to call the callbacks at the right time, but that's about it.
The reason I require explicit lists is so browsers can lock the others in that document to update them in parallel and be able to compute their layout without having to assume the prospect of interference with other code. (In practice, they only need one read/write lock to rule them all per document, and after that, a quick flag check whose value is initially calculated after animation frame callbacks are run to assert that the node is destined to become live.)
The choice of whether to fire an extra callback is deferred until the end because you might find while patching that you might not need to fire that layout callback (which would be potentially pretty expensive). If no layout callbacks are scheduled, the browser can compute layout immediately and exercise its normal magic, all off-thread.
The DOMTreeConstruction API is about 90% solved by innerHTML with <template>s, and in general, it looks to be solving a problem orthogonal to transactions (so I'm more neutral on it). You could still get very nice gains from using them in place of document.createElement(elem) with large trees, while still adding them via elem.appendChild(tree). (I've witnessed this in action already with template.content.cloneNode(true) + a few elem.querySelector calls being faster than the equivalent document.createElement + elem.appendChild sequence, and in some cases, even when dynamically created with innerHTML.)

It's not transactions. We cannot do transactions given iframe and such. And also, your API doesn't work in workers, which is rather big part of the value proposition. If you still wish to pursue it, please do so in a distinct issue.

Okay. 👍

Navigation Menu

Repository navigation

Proposal: DOMChangeList #270

`DOMChangeList` and `DOMTreeConstruction`

Motivation

Concepts

NodeToken

Applying a Change

Details

DOMTreeConstruction

DOMChangeList

Example

FAQ

Is this actually faster?

Isn't the real issue that people are interleaving DOM manipulation and layout?

Unresolved Questions

35 remaining items

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Proposal: DOMChangeList #270

Description

DOMChangeList and DOMTreeConstruction

Motivation

Concepts

NodeToken

Applying a Change

Details

DOMTreeConstruction

DOMChangeList

Example

FAQ

Is this actually faster?

Isn't the real issue that people are interleaving DOM manipulation and layout?

Unresolved Questions

Activity

KrisSiegel commented on Jun 20, 2016

wycats commented on Jun 20, 2016

domenic commented on Jun 20, 2016

KrisSiegel commented on Jun 20, 2016

annevk commented on Jun 20, 2016

KrisSiegel commented on Jun 20, 2016

annevk commented on Jun 20, 2016

bfgeek commented on Jun 20, 2016

wycats commented on Jun 20, 2016

domenic commented on Jun 20, 2016

wycats commented on Jun 20, 2016

bfgeek commented on Jun 20, 2016

domenic commented on Jun 20, 2016

wycats commented on Jun 20, 2016

wycats commented on Jun 20, 2016

35 remaining items

Gozala commented on Oct 25, 2017

wycats commented on Oct 25, 2017

Gozala commented on Oct 25, 2017

annevk commented on Nov 10, 2017

AshleyScirra commented on Dec 19, 2017

dead-claudia commented on Feb 18, 2018

annevk commented on Feb 18, 2018

AshleyScirra commented on Feb 18, 2018

dead-claudia commented on Feb 18, 2018

dead-claudia commented on Feb 19, 2018

annevk commented on Feb 19, 2018

dead-claudia commented on Feb 19, 2018

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

`DOMChangeList` and `DOMTreeConstruction`