Tuesday 25 September 2007
Suppose we want to exploit parallelism to load and run an existing Web application faster. How might that be done?
Here's a very high level diagram of the data flow inside the browser. I believe it's reasonably accurate for Webkit as well as Gecko.
There are some missing edges in some cases; for example, the style system can affect the DOM via XBL. I'm going to gloss over those for now.
Observe that the DOM is really the center of the universe. It's a big blob of mutable state that everything else depends on. Any parallelization of single-page applications is going to have to carefully manage access to the DOM.
For performance reasons, changes to the DOM are lazily propagated to the style system, layout and rendering. The goal is to batch changes so that these phases are not reexecuted too often --- they're expensive, even when incremental. DOM updates make method calls to registered listeners. Listeners record which styles might have been affected and post a restyle event (if one hasn't already been queued) to be processed later. Similarly, they set dirty bits in the frame tree and then post a reflow event. On the other side, the parser batches its appends to the DOM as well. It's primarily only script execution that makes many fine-grained, interleaved reads and writes.
[There are times when scripts need access to up-to-date style and layout data. In Gecko, at those times we invoke FlushPendingNotifications to force synchronous restyling and layout. Because this is already a significant performance hit, Web developers should already be trying to avoid triggering it (e.g., by accessing DOM offset* properties).]
I think we could leverage these access patterns to help parallelize browser execution:
- Parsing can be mostly asynchronous; it should only need to synchronize with the DOM when it's ready to append a bunch of elements.
- Styling, layout and rendering can take a snapshot of the DOM and use it while the real DOM is being updated by other tasks. It's OK for the display of a page to lag slightly behind; it already does today. The snapshot will be refreshed each time we need to update the window again, or when layout results must be return synchronously to scripts.
- To run scripts, such as JS event handlers, in parallel, we could use optimistic concurrency via transactions. The idea is that we run a script speculatively against a snapshot of the DOM, recording which parts of the DOM it reads and suppressing its changes to the state of the DOM and other parts of the world. When the script has completed, we synchronize with the real DOM and check whether anything the script depended on has changed. If not, then we can commit the script's global changes. Otherwise, its execution is invalid; we throw out its changes and reexecute it all over again.
None of this is easy to implement. Making real snapshots of the DOM would be prohibitively expensive, so some kind of versioning or copy-on-write scheme is required. Which state constitutes "the DOM" that needs versioning is actually a little nebulous; for example, would we version the state of <canvas> elements? How about DOM Storage or the proposed DOM SQL API? However, the good news is that some of this can be done incrementally. For example, we could start with a limited slice of DOM state that is versioned, and decree that speculative script accessing any other state is aborted, and then gradually increase the scope of versioning.
There's a lot more to think and talk about in this area.