Hi everyone,
I had an idea for how to handle block formatting contexts impacted by
floats in a way that doesn't sacrifice parallelism, with some
speculation. I'd like to get feedback on people's intuitions as to (a)
whether this is likely to pay off; (b) whether this works :)
Recall that block formatting contexts are a special kind of block whose
*actual width* (not the width of individual *lines* as is normally done)
depends on floats next to it. The most common way to create a block
formatting context is to use the property `overflow: hidden`. This is
commonly used to create sidebar layouts, which I first noticed on this
page [1]. It causes a problem for Servo because Servo wants to assign
widths before assigning heights, but block formatting contexts make
width assignment possibly depend on height assignment. Consider this page:
<div style="float: right">float1</div>
<div>blah blah blah</div>
<div style="float: right">float2</div>
<div style="overflow: hidden; border: solid black 1px"></div>
Depending on the heights of the floats, we have no idea if this renders as:
blah blah float1
blah
float2
+--------------+
| |
+--------------+
Or:
blah blah float1
blah float2
+-------+
| |
+-------+
We only know the positions of the heights after performing height
assignment, so this causes a problem.
What I did in my previous pull request [2] is to have the notion of
"suspended height computation" and "deferred width computation". This
intertwines the two passes in a tricky way: we compute beforehand
whether a block formatting context was potentially impacted by floats,
and delay its width computation until the heights of floats next to it
and the heights of preceding blocks are known. This requires that the
parent of the block formatting context be able to *suspend* and *resume*
its height computation once the width of the block formatting context
has been computed, which adds quite a bit of complexity because now we
have to save and restore state and so forth.
I realized, however, that with some speculation we may be able to
eliminate this complexity, as well as gain the more parallelism back if
the speculation pays off. What we do is to *speculate that a block
formatting context will be impacted by the minimum number of floats that
it possibly could be, assuming the floats' height is nonzero*. In other
words, we speculate that the width of a block formatting context that
was impacted by floats is the width of its container minus the width of
the float that immediately precedes it, if any (correctly accounting for
borders/padding/margins of course). Layout proceeds as normal; in
particular, we need not perform sequential traversals for the block
formatting context and can lay it out in parallel.
When we go to compute assign-heights for the parent block of the block
formatting context, we verify that our width guess was correct. If it
was incorrect, we record the correct width and perform assign-widths and
assign-heights again for the subtree rooted at the parent of the block
formatting context.
This will correctly predict the layout on that subreddit, and I imagine
it correctly predicts the layout on most pages that are using block
formatting contexts for sidebars. It also allows for a large degree of
parallelism even in the presence of floats; all blocks on that page can
be laid out in parallel assuming the speculation guessed correctly. (In
fact, I can imagine that even if the speculation failed, we might still
barely win due to the parallelism, though this is of course risky.) The
code simplification that this affords—allowing width assignment and
height assignment to stay separate and avoiding complicated logic to
suspend and resume height assignment—is attractive as well from a
maintainability point of view (and possibly performance as well in cases
that don't involve block formatting contexts).
Any thoughts?
Patrick
[1]:
http://www.reddit.com/r/Bitcoin/comments/23flcn/bits_instead_of_%CE%BCbtc/
[2]: https://github.com/mozilla/servo/pull/1734
_______________________________________________
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
