Parallelizing layout and graphics

[Boris Zbarsky]

A few of us got together this morning with a whiteboard and talked about
parallelism opportunities in layout and graphics. This post is a
summary of the discussion; I would appreciate comments about anything we
missed. I would also appreciate it if people would step up to file and
fix bugs on code they are familiar with as needed to help out with this;
some of the issues that can be done in bite-sized chunks are described
below.

The whiteboard image involved is at
https://bug702160.bugzilla.mozilla.org/attachment.cgi?id=574198

The big tangle of arrows and boxes in the middle is the current data
flow from DOM changes to getting pixels on the screen. This all happens
on the main thread right now, modulo e10s in Fennec.

There was discussion of two kinds of parallelism we can attack: data
parallelism within each box in the diagram and sequential parallelism of
the pipeline. The goal is to improve both responsiveness and throughput
(frame rates).

We more or less agreed that the two have one important thing in common:
code implementing a particular box in the diagram needs to be able to
assume that the data in all previous boxes is immutable while that code
executes. That means some combination of const APIs (really const; no
const_cast or use of mutable or other cheating) and caching of all the
data you need from the previous parts of the data flow.

This part is something that can in fact happen piecemeal. It's worth
starting on it now, and also worth making sure we don't add new
non-const APIs or APIs that claim to be const that cheat. Note that not
mutating the particular object the call is made on is not enough; the
call must also not mutate global caches of any sort (e.g. no do_GetAtom
calls).

Pipeline parallelism:

We agreed that trying to pipeline style resolution and frame
construction across threads was likely pretty hard; probably likewise
for reflow. There seem to be three main opportunities for pipeline
parallelization, of which two are probably worth it:

* Once a display list is constructed (but not yet optimized), all work
to optimize and paint that display list can probably happen off the UI
thread. This requires at the very least that display lists cache
whatever frame geometry information they need, that they precache some
style data, and that we deal with whatever SVG issues arise. The style
data angle of this is not too bad; the others are of somewhat unknown
scope at this time, but seem doable.
* Once a display list has been created and optimized, construction of
the layer tree could probably happen in parallel with construction of
the next display list. This is likely not that worthwhile, at first glance.
* Once a layer tree has been constructed, painting it could happen in
parallel with construction of the next display list and layer tree.
This seems worthwhile.

The first and third of those thread boundaries are indicated by the
vertical red lines in the diagram at the bottom of the whiteboard photo.
That diagram in general represents how things would work in the
pipeline-parallelized world.

Data parallelism:

The top-right part of the whiteboard image lists the areas that we think
can be data parallelized without going insane. These are:

1) Selector matching.
https://bugzilla.mozilla.org/show_bug.cgi?id=631527 is a good first step
there
2) Frame construction. This would involve precaching style data,
because GetStyle* are clearly not const in a useful way.
3) Intrinsic width computations. Again, we'd need to handle style data
up front.
4) Textrun construction and shaping. For example, we could kick off
some code to prime the textrun word cache on a background thread.
5) Display list construction and maybe layer tree construction.
6) DrawThebesLayer (if nothing else, parallelized across layers by just
chunking up the z-ordered list of content during layer tree
construction). This depends on Azure; our current gfx code isn't
threadsafe enough.

Conclusion:

In the short term we're going to work on landing the selector matching
parallelization and obviously keep working on Azure. We're also going
to try to avoid the cheating on const anti-pattern and see how much we
can make things const.

Medium term, DrawThebesLayer depends on Azure being available, but we
should be able to make some progress on the others starting immediately.

Long term, we want to do all of these, probably. Any others we should
be doing?

If you feel like something mentioned above is in your area of expertise,
please file bugs blocking
https://bugzilla.mozilla.org/show_bug.cgi?id=702160 as needed.

Thanks,
Boris

[smaug]

We need to probably think how event handling maps to this all.
There has been bugs filed when layout (and even painting?)
hasn't been flushed when user moves the mouse. Not flushing is ofc
faster, but causes problems when the page has some mousemove-dependent
dhtml menus or similar.
When we parallelize things, it would be rather unfortunate if mouse move
would need to wait for other threads to do something.


-Olli

[Boris Zbarsky]

On 11/14/11 8:06 PM, smaug wrote:
> We need to probably think how event handling maps to this all.
> There has been bugs filed when layout (and even painting?)
> hasn't been flushed when user moves the mouse. Not flushing is ofc
> faster, but causes problems when the page has some mousemove-dependent
> dhtml menus or similar.
> When we parallelize things, it would be rather unfortunate if mouse move
> would need to wait for other threads to do something.

In the setup I'm envisioning so far, as long as only layout flushes are
needed there is no problem: layout and the parts that happen before it
happen either on the main thread or on several threads in parallel but
with all threads completing before the main thread continues. The
pipeline parallelism that looks feasible so far is all on the painting
end of things.

-Boris