Incremental layout in 2020

[SimonSapin]

The inputs of rendering includes the DOM tree, stylesheets, form data, input state (:hover, …), scroll positions, etc. When any of these inputs changes, we need to re-render a push a new bunch of pixels to the screen. It order to make this cheap, we want to reuse as much as possible of the previous rendering and skip re-computing intermediate results that haven’t changed. For layout in particular, this means reusing parts of the CSS box tree and fragment tree.

At the same time, we want fine-grained parallelism during layout to take advantage of available CPU cores. Avoiding data races requires either avoiding or synchronizing any shared mutability.

During our explorations last spring, I settled on trying the following approach to reconcile these goals:

• The box tree and fragment tree are each thread-safe and made of atomically reference-counted nodes.

• Nodes are mostly read-only after construction. Some pieces of data may be in AtomicRefCells (if the algorithm structure is such that concurrent access would be a bug) or Mutexes or RwLocks, but most data can be read without synchronization.

• The trees are persistent: updates are done by creating a new tree that share existing nodes for some sub-trees. "Modifying" a single node involves creating new nodes for it and its ancestors up to the root. This overhead is hopefully viable since HTML trees (which box trees and fragment trees are based on) tend not to be very deep, although they can get wide.

• Currently the child nodes of a given node are kept in a Vec. So creating a new node that is similar except with one different child node requires creating a new Vec, which takes O(n) time where n is the number of direct child nodes. It’s not uncommon for that number to grow large, so switching to im::Vector could help: clone is O(1) and get_mut is O(log(n)).

I think we could start with some conservative reuse in cases where we can easily determined that a subtree definitely hasn’t changed, and make it more fine-grained over time.

@nox, you mentioned an idea for reuse around block-in-inline splits?

[nox]

Yes, basically my idea lets us keep the children of a display: contents element in the box stored in that element itself, same for split inline boxes. That requires quite heavy changes to the DOM traversal code (but those changes would be local to it), and me figuring out the best way to represent a split inline box.

The end result of what I have in mind is that we incremental box generation would then be able to start from a list of root elements which were modified since last layout, and parents would only need to be reconstructed in a limited set of circumstances (for example, a previously-unsplit inline box in which a block box is inserted would trigger reconstructing its parent boxes until the nearest enclosing block box, but further edits to the split inline box wouldn't reconstruct parents anymore), AFAIK that gives us amortised O(n) incremental box construction, where n is the amount of nodes which changed.

[SimonSapin]

keep the children of a display: contents element in the box stored in that element itself, same for split inline boxes

I don’t understand this part, could you rephrase?

[nox]

Some things straight out of my mind:

An element that generates an unsplit inline-level box would be handled just as currently, storing an Arc<AtomicRefCell<InlineLevelBox>> as its layout box, and when its parent constructs its own box, it will do the following:

• if the parent generates a block box, store the Arc<AtomicRefCell<InlineLevelBox>> as part of an anonymous inline formatting context.
• if the parent generates an inline box, store the Arc<AtomicRefCell<InlineLevelBox>> as a simple child of the parent's inline box.

Note how the inline-level child generates exactly one Arc<AtomicRefCell<_>> which can then be incrementally modified later without changing any parent inline formatting context or inline box.

On the other end, if that eleement generates a split inline-level box, we would store a value of a type like this instead:

struct SplitInlineLevelBox {
    leading_inline_level_box: Arc<AtomicRefCell<InlineLevelBox>>,
    inner_block_level_box: Arc<AtomicRefCell<BlockLevelBox>>,
    trailing_inline_level_box: Arc<AtomicRefCell<InlineLevelBox>>,
}

And on creating the box for the parent, two different things can happen again:

Either the parent is a block box, and we need to do three things:

• append leading_inline_level_box to the current ongoing inline formatting context and end it
• append the block-level box inner_block_level_box just as we would currently
• start a new inline formatting context and put trailing_inline_level_box in it

The resulting layout box once every child has been handled is an Arc<AtomicRefCell<BlockLevelBox>>.

Or the parent is an inline-level box, and we need to do three things:

• wrap leading_inline_level_box in its own inline-level box with the parent's style
• wrap trailing_inline_level_box in its own inline-level box with the parent's style
• create a SplitInlineLevelBox with the two wrapped inline-level boxes, passing inner_block_level_box as is.

The resulting layout box is a SplitInlineLevelBox, and that box's parent box will need to take care of putting the leading and trailing inline-level boxes in the appropriate inline formatting contexts as usual, but no change to the leading and trailing inline-level boxes will require rebuilding the parent box, once again.

[pcwalton]

Do we actually need reference counting here?

When we go down the box tree to perform layout, we could keep the old render tree from the previous layout around and follow the links down through clean nodes with dirty descendants. Then when we get to a clean node with a clean descendant subtree, we just extract the old render subtree and use that instead of recreating it. Everything remains singly-owned at all times.

[nox]

We need reference counting whether or not there is incremental layout going on. Each box points to its children boxes, and each DOM element points to its layout box(es) too.

[pcwalton]

What about using Arc::make_mut() to perform persistent in-place updates of nodes? I noticed we already use it in a couple of places in layout, and going with the strategy we've already naturally evolved toward (and are paying the costs for) seems attractive. This does have some overhead, but not for newly-created nodes, only existing ones. We could optimize it with hardware lock elision on CPUs that support it. We could also try to ensure that the reference count is one so as to hit the Arc::make_mut fast path, perhaps by nulling out references to the box tree from the DOM.

A fallback plan if the Arc::make_mut() approach doesn't pan out could be to switch between parallel or single-threaded-but-incremental layout depending on whether we're laying out a large subtree. This may seem disappointing, and I don't quite know what the details would be, but it may not sacrifice that much performance. I suspect that typical incremental-layout scenarios like appending text to a text field may not benefit that much from parallel layout to begin with, and that parallel layout is mainly a win when we have a large number of nodes to build or rebuild from scratch. The canonical workloads I can think of that really benefit from parallel layout are things like initial page load of news sites, scrolling down on Facebook Timeline, or loading the Gmail inbox, all of which are of the form "a whole bunch of new nodes in a subtree appeared and we need to get them laid out as quickly as possible".

[nox]

We still own those from 2 different places at once, so Arc::make_mut won't help us. I really doubt removing the refcounting is important here.

[nox]

So when you have 2 references to the same layout tree box from its DOM element and from its parent layout tree box, you have two choices.

Either you call Arc::make_mut on the DOM element's reference, which means the parent's reference is now wrong.

Or you call Arc::make_mut on the parent's reference, which means you have been calling Arc::make_mut recursively from the root of the layout tree, somehow managing to correlate it fully with the DOM tree it was generated from. I don't see how you can do that, and I don't automatically believe those recursive Arc::make_mut calls help either readability or performance.

[pcwalton]

I don't automatically believe those recursive Arc::make_mut calls help either readability or performance.

As compared to R/W locks around every box?

[nox]

I don't think anyone of us expect to use R/W locks, just AtomicRefCell values.

[nox]

Note also that Arc::make_mut in the best case does just as much work as AtomicRefCell::borrow_mut.

[pcwalton]

You still think pervasive use of AtomicRefCell is feasible? (I don't disagree, by the way, but I was under the impression that for some reason you and Simon thought it was infeasible.)

[nox]

AFAIK no, we never said it was infeasible. My comment just before yours mentions AtomicRefCell.

[pcwalton]

Well, that's good news then :) My understanding per jdm was that there were doubts about it, but if not then carry on. AtomicRefCell seems like a good solution.

[pcwalton]

As a potential backup plan if AtomicRefCell is too slow, I propose something similar to https://bugzilla.mozilla.org/show_bug.cgi?id=1335941#c8 — make a special token that allows using unsynchronized writes to borrow AtomicRefCells. We can use this token to perform sequential incremental reflow if we decide based on heuristics that parallel layout isn't worth it.

Another interesting avenue to consider is lock elision/hardware transactional memory. I could imagine something like "if hardware lock elision is available, then always do layout in parallel; otherwise, sometimes perform sequential incremental layout based on heuristics."

[pcwalton]

Started a branch for AtomicRefCell: https://github.com/pcwalton/servo/tree/layout-2020-atomic-refcell

[nox]

So are you working on this Patrick? The last thing I want is to duplicate efforts.

[nox]

A very first step towards incremental layout would be to skip box tree construction when none of position/display/float properties changed.

We need various things for that:

1. Check that the style damage system already has bits for that, and if it doesn't, change it.
2. Wrap the ServoArc<ComputedValues> from the various box tree types into its own AtomicRefCell<_> so that we can update those without trashing the entire box tree.
3. Change box tree construction so that elements point to all the boxes they generated, even split inline elements.
4. Don't rebuild the box tree when the damage system says it won't have changes, and instead update the style values in the boxes.

[nox]

(Also of course, we can't skip it if the document tree itself changed, e.g. when elements were added or removed.)

[pcwalton]

So are you working on this Patrick? The last thing I want is to duplicate efforts.

I'm not really intending to work in depth on incremental layout right now. I did #25957 primarily for performance testing. I submitted it because the perf results are positive and it's a fair bit of work so I wanted to save y'all the time of having to make those changes :)

[pcwalton]

A very first step towards incremental layout would be to skip box tree construction when none of position/display/float properties changed.

Another good one is to skip layout entirely if only paint-relevant properties have changed. This covers a lot of common situations; e.g. mousing over links and selecting text.

[nox]

So I've looked into the current damage system.

The stuff in style::restyle_damage is pretty straightforwards: each property define what kind of damage it induces, and then all the various damages are checked to decide what should be reran and what should be reused.

The problem is that this system is really dependent on how layout is done, and thus the different categories of damages correspond to layout 2013 so much that I don't think it can be leveraged for layout 2020.

Do we want a new damage system that is specific to which layout system we are using instead? Like, does ServoRestyleDamage::BUBBLE_ISIZES make sense for layout 2020?

[pcwalton]

I agree with that; let's make a new damage system. I don't have a lot of love for the old one anyway.

[pcwalton]

@nox Do you envision needing more AtomicRefCells in layout past the ones I introduced in #25957?

[nox]

Good question! One thing I'm not sure about is how we update the styles of the trees we keep to regenerate the later trees that we don't keep. Do we just mutably borrow each box and fragment to change their style field, or do we store the Arc<ComputedValues> itself in an Arc<AtomicRefCell<_>> so we don't have to traverse trees just to update those? Arc<AtomicRefCell<Arc<ComputedValues>>> sounds a bit too much.

[nox]

ArcSwap<Arc<ComputedValues>> is also something we should look at if we go this way.

[nox]

In our Mako files, servo_restyle_damage="rebuild_and_reflow" means the box tree should change in layout 2020. We can reuse that.

[nox]

And "reflow" is more or less what corresponds to things that need to change the fragment tree.