Dynamically switch to sequential layout if only a small amount of reflow needs to happen

[pcwalton]

Parallel layout overhead is overkill if only a small number of nodes need to be reflowed. In the extreme case, if one chain of nodes from parent to child needs to be reflowed, then parallel layout cannot help at all since it's sequentialized, and all of the traversal code is pure overhead!

The easiest way to solve this, I think, would be to have an atomic counter of the number of nodes that were discovered to be dirty (incremental.rs can compute this, perhaps) and have the layout thread consult that number. If below a threshold (8? wild guess) then parallel layout will not be spawned. Note that we don't want this to regress performance on pages that have a small number of nodes but lots of reflow to do: consider four paragraphs of 10,000 words each, for instance, which has a small number of nodes but is the ideal case for parallel layout. So we'll probably need a couple of heuristics here and tune appropriately.

cc @paulrouget

[larsbergstrom]

@rzambre has been doing a bunch of predictive work here (for more than just the size of the DOM tree, but also metrics around its width at each height) to predict whether parallelism is a payoff.

So far, we've definitely seen that this is a per-architecture decision, but he has a framework and some testing that is gathering a lot of info here. Integrating this into Servo is the planned topic of his RA/internship this summer!

[pcwalton]

Nice! Paul's work isolating performance issues in browser.html has shown that there should be a real benefit from this area. :)

[larsbergstrom]

One of the things I'm most excited about here is also just making those gobs of tiny iframes (tracker icons, just a navpane, etc.) only take one thread. We might get CNN.com under 250 threads in one swoop! :-)

[paulrouget]

Is that a thing that could be done by June?

[larsbergstrom]

I'll talk to @rzambre. We could probably get some very simple heuristics in place pretty quickly based on some of the numbers he's gathered around cutoff points for this metric.

[paulrouget]

I'll talk to @rzambre. We could probably get some very simple heuristics in place pretty quickly based on some of the numbers he's gathered around cutoff points for this metric.

That would be awesome! I'd like to see how much this could improve browserhtml performance.

[rzambre]

I am quite confident about the influence of the following DOM-tree features on the amount of parallel work available: DOM-size (total number of DOM nodes), average width of the DOM tree, number of leaves in the DOM tree.

[paulrouget]

I am quite confident about the influence of the following DOM-tree features on the amount of parallel work available: DOM-size (total number of DOM nodes), average width of the DOM tree, number of leaves in the DOM tree.

@rzambre are you working on this?

[rzambre]

@paulrouget Yes! Our group here at UC Irvine has been working on creating a predictive classification model for the parallel styling/layout performance of Servo using DOM tree characteristics as the predictive features. Using 8 DOM tree characteristics, we have some simple models that achieve an accuracy of up to 80%. Those were based on performance numbers on a laptop platform. We are now looking at doing the same with an embedded/mobile platform. We are expecting to see higher distinctions between performance numbers for different kinds of DOMs. But as far as incorporating these results into Servo, we haven't done any of that yet. We'd like to see higher accuracies from our embedded system data set. Also, we'd like to dig a little deeper into the inner working of Servo's parallel styling/layout to possibly capture new predictive features. But we can definitely begin incorporating heuristics that we feel confident about!

[rzambre]

After going through our labeled classification data, here are some raw cut-off numbers for parallelization of overall layout (styling + primary layout passes).

If we are looking at only one feature to decide whether or not to parallelize, these would be the threshold values:

• DOM-size: parallelize if greater than 750
• Number of leaves: parallelize if greater than 385
• Average tree width: parallelize if greater than 45

If we are looking at a combination of features then I would suggest the following:

Parallelize only if (DOM-size > 600 AND num-of-leaves > 300 AND avg-tree-width > 45). Otherwise, perform overall layout sequentially.

[paulrouget]

Parallelize only if (DOM-size > 600 AND num-of-leaves > 300 AND avg-tree-width > 45). Otherwise, perform overall layout sequentially.

Is there an easy way to test if my page fits in there?

[rzambre]

We'll have to collect these numbers for each page that is being loaded. I'm thinking DOM-size and num-of-leaves can be easily computed by incrementing counters when the HTML parser works on new/incremental HTML content. avg-tree-width could be trickier to collect since we might have to wait until the whole DOM tree of the page is constructed; the width at each height-level of the tree needs to be collected.
I had used a BFS traversal on the DOM trees built from saved HTML files to collect these numbers on the pages that I was working with.

[metajack]

You can test how this affects browser.html by running with -y 1. I'm not sure why this is a P2 bhtml bug though. It seems like this would have minimal impact.

Note that we can start layout before the whole DOM is loaded. Specifically we start layout after N milliseconds where N is some small constant like 12 or so. So whatever heuristics we want will be applied to whatever DOM we get in that timeframe, although as we get more we can obviously run layout with different numbers of threads on subsequent passes.

A first pass implementation of this could just wait until the DOM is fully realized, do the calculation and just make further layouts single threaded. Then in later improvements we can start trying to make this decision earlier.

[metajack]

Diane and I discussed this. I think the first step will be to implement the @rzambre's DOM-size metric first, which should be easy to calculate earlier in the pipeline.

[avadacatavra]

I'm thinking that I'll stick a counter in the ServoHTMLParser and keep track when create_element is called.

Is that reasonable? Or is there a better place to stick the counting?

[larsbergstrom]

@dd0x68 That seems reasonable to me. @jdm, will that capture all of the DOM element creations and be available by the time we want to perform layout?

[jdm]

Yes and yes, depending on where the count is stored.

[avadacatavra]

@jdm That's what I'm trying to figure out now

[metajack]

Do we want to update the count on element removal as well? Or just assume that once we switch to parallel mode for a layout we stay in parallel mode?

@rzambre @larsbergstrom it occurs to me that relayout will be some subset of the flow tree. I assume your results were just for full layout passes? Maybe later we need to be smarter and make this based on dirty flow tree nodes.

[avadacatavra]

@metajack From what I see, the parallel/sequential determination is made when the LayoutThread is created. I guess to go to sequential we would just terminate the workers and set parallel_traversal to None. It seems like we would end up either losing state or redoing work in that case.

Currently, I'm just assuming that once we switch to parallel mode, we stay in parallel mode.

[metajack]

Yes, that is how it works now and I think we should constrain the first pass at this.

In the future, it may make sense to make this more dynamic. Baby steps :)

[jdm]

The LayoutThread is created before the page content is available, so the decision will need to be made later than that.