Ben Lerner

[Niko Matsakis]

Hello,

I wanted to share an e-mail I received from Ben Lerner. What I wrote to
him (after some discussion) was the following:

> The initial design was going to be a sort of shadow DOM where the
> master DOM nodes were maintained by a JavaScript library dom.js [2]
> which would then fire messages off to a separate actor, implemented in
> Rust, which would maintain a shadow DOM. However, we are now becoming
> quite concerned about the impact of this on performance—especially
> startup time.
>
> To be honest, we haven't thought as hard about issues like the
> "cross-compartment" (to use the mozilla terminology) security concerns
> that you brought up. It's an interesting angle that could indeed be
> very relevant.
>
> At the moment, we are discussing using an RCU- or COW-like system,
> where the main thread makes changes to the DOM but layout can be
> provided a kind of cheap snapshot. But in general this architecture
> is very much in the air---any kind of experience reports or
> suggestions you have would be most welcome.
to which he responded as shown below.

I thought his comments would be of interest to everyone.


regards,
Niko

-------- Original Message --------
Subject: Re: parallel browser impl and the dom
Date: Wed, 14 Mar 2012 00:36:13 -0400
From: Ben Lerner <ble...@cs.brown.edu>
To: Niko Matsakis <nmat...@mozilla.com>



Hi Niko,

It's taken me a couple days to get time to catch up with the mailing
list, and what follows are my current, rough thoughts. I'll start
posting to the list soon, probably... :)

> The initial design was going to be a sort of shadow DOM where the
> master DOM nodes were maintained by a JavaScript library dom.js [2]
> which would then fire messages off to a separate actor, implemented in
> Rust, which would maintain a shadow DOM. However, we are now becoming
> quite concerned about the impact of this on performance—especially
> startup time.
>
Let me separate out four facets of tree-like structures that exist in a
browser: 1) the tree of objects in the JS heap representing the page
structure; 2) the tree of native objects implementing the DOM
functionality of those objects; 3) the tree of mostly-nested 2d boxes to
be drawn on screen; and 4) any intermediate structures needed to get
from #2 to #3. (I'm ignoring any scene-graph issues for how to actually
render #4 to graphics hardware.)

In Gecko, #1 and #2 can be separate -- XPCNativeWrappers (or whatever
they've morphed into in recent builds) mean that the JS object you hold
may not be directly implemented by a bunch of C code. In Chrome, #1 and
#2 are likewise separate, due to the "separate worlds" or
cross-compartment wrappers. In C3, #1 and #2 were one and the same set
of objects in memory; the C# implementations of DOM methods were made
available to JS, and each DOM class ultimately inherited from the class
that implemented basic Objects. (Leo's post, claiming JS -> DOM ->
cascade -> layout, was wrong by one layer.)

To get from #2 to #3, we took as a guiding principle that layout should
know nothing whatsoever about JS objects -- in theory, it only needs to
know the tree structure (and a few attributes, which we could
serialize). To enforce this, the layout module didn't even import the
DOM module, and didn't even know about the DOM types. In return,
because layout was so kindly oblivious, we could simply fire out
asynchronous, lock-free messages from the DOM to whoever was listening
(which included the layout engine, and a rudimentary DOM Inspector, and
never worry about deadlock or race conditions. This should have
resulted in complete parallelism between DOM and layout, except for
blocking calls like getOffsetX() that depend on the results of layout.

The problem with this is that ultimately the tree structure of the DOM
is serialized *three* times: once in the JS heap, once in the
representation that layout used to compute the box model, and then once
more in the message queue describing the mutations to the tree. This
was appalling for performance, particularly the queue, because that data
structure was so evanescent that it was a waste to have to write it in
memory. A reworking of the design eliminated the queue, but IIRC we
never managed to eliminate the other, because we were trying to maintain
as much of the DOM/layout decoupling as we could.

So when you describe maintaining a shadow DOM in Rust, and the "real"
DOM in JS, I'm a little worried, for two reasons. First, I suspect
DOM.js will only pan out if you can implement *all* of the DOM methods
in JS, and *never* have to drop down to native platform code. Otherwise
your choice of having the "true" DOM be (proxied, somewhat special) JS
objects may prevent you from having the data you need at a lower level.
And second, creating a shadow DOM just so you can transform it into a
box tree and then (mostly) discard it is very wasteful. On the other
hand, a Rust DOM with convenient, auto-generated bindings into JS (like
XPCOM but *much* cleaner :-p) avoids both these issues.

A final point -- Boris and Patrick's point about DOM.js "making certain
DOM operations fast by keeping them in JS so they could be jitted" never
came up in C3, because C3's jit operated on .Net IL, to which we
compiled JS. So in theory we could jit runtime and script code
together. (In practice we didn't get it working in time, because the
platform on which the jit ran didn't support winforms, so we couldn't
have a jit and a renderer simultaneously :-\)
> To be honest, we haven't thought as hard about issues like the
> "cross-compartment" (to use the mozilla terminology) security concerns
> that you brought up. It's an interesting angle that could indeed be
> very relevant.
>
If your DOM objects are "truly" Rust objects whose internal state is
richer than the interface that's reflected up into JS, then you can use
Rust's type system to try to enforce static guarantees that a DOM.js
solution can't. As a very-rough example, suppose you had an abstract
type Origin. and suppose all your DOM classes were parameterized with a
phantom type that was a subtype of Origin:

class DOMNode<o extends Origin> {
void appendChild(DOMNode<o> newChild);
DOMNode<o> importNode(DOMNode<other extends Origin> remoteNode);
}

There is simply no way, statically, to call this appendChild with a node
from another origin, and the type signature of importNode highlights
exactly what it does. So type-correct Rust code cannot cause DOM
exceptions, and if JS clients call Rust methods incorrectly, the type
errors are easily and naturally surfaces as "Wrong Document" errors.
Similarly, an event loop could be parameterized, and then you're
guaranteed events for one page never get dispatched internally to the
wrong pages... There's a lot of rough edges to this proposal
(cross-site scripts& images spring to mind), but this could be a means
to actually verifying the correctness of the DOM invariants. It's an
angle I really wanted to pursue in C3, but needed to finish my thesis
and get done... :) If it comes up in Servo, I'd be keen to work on it.

> At the moment, we are discussing using an RCU- or COW-like system,
> where the main thread makes changes to the DOM but layout can be
> provided a kind of cheap snapshot. But in general this architecture
> is very much in the air---any kind of experience reports or
> suggestions you have would be most welcome.
>
Snapshotting sounds terrific; getting it to work is hard :) We managed
to version our box model, but not the DOM itself. (Some specialty
objects, like live-updating collections, held version numbers, but we
never could say "this whole tree is v1; after these changes it becomes
v2". I've wondered if some functional structure like a zipper might
work, but I suspect the overhead of chasing pointers up to the root and
back down would swamp any COW efficiency gains...