Here's an idea for how to leverage the leaf-set-removal proposal to optimize
this algorithm:
1. When assigning widths for parents, don't enqueue absolutely positioned kids
to have their widths assigned.
2. Absolutely positioned kids of a node should not be counted as outstanding
children-to-be-reflowed for the purposes of height assignment. The effect of
this is that height may be computed for a node once all of its in-flow children
have had their heights computed; it need not wait on absolutely positioned
children.
3. After assigning heights for parents that have absolutely positioned kids,
don't store overflow for them (or their ancestors) right away, because their
overflow regions *do* depend on the overflow regions of their absolutely
positioned kids. Instead, for each such parent, store an atomic count X of
absolutely positioned kids inside it, and enqueue assign-*widths* for all of
the parent's absolutely positioned kids.
4. After assigning widths for a leaf, start assigning heights for it
immediately. (This is the leaf-set removal proposal.)
5. After assigning heights for an absolutely positioned frame, do *not*
decrement its parent's count of outstanding children-to-be-reflowed (as that
number should be zero). Instead decrement X (the atomic count of
absolutely-positioned kids) on the parent. If zero, then compute overflow for
the parent and all of its ancestors.
I believe this algorithm or something like it can achieve the goal of
performing layout for absolutely positioned frames after all of the frames it
could possibly depend on, without the subtle invariants of my first proposal.
It's essentially the same as bz's algorithm but without the explicit list;
rather it uses the parallel work queue as the list. It also avoids the O(n^2)
hazard by computing overflow for each frame exactly once.
How does this sound?
Patrick
Patrick Walton <pwal...@mozilla.com> wrote:
>For the first concern, I realized that pages like that are going to be
>sequential no matter what we do, of course, because of the way parallel
>tree traversals work. So never mind there. The O(n^2) update of
>overflow areas still concerns me though.
>
>Patrick Walton <pcwal...@mozilla.com> wrote:
>>On 2/13/14 2:42 PM, Boris Zbarsky wrote:
>>> Then you go through this list (this part should parallelize pretty
>>> nicely, btw, except for the overflow area updates on parents) and
>>reflow
>>> them all, since now you know their containing block sizes, and you
>>> update overflow areas. Again, if there are abs pos kids you add to
>a
>>> list, etc.
>>
>>I have a couple of concerns about this from a performance point of
>>view.
>>
>>1. This creates multiple sequential barriers, which can result in a
>>parallelism hazard. As an extreme case, consider:
>>
>> <style>div { position: absolute; }</style>
>>
>> <div><div><div><div><div>...
>>
>>This will effectively result in fully sequential layout because you
>>have
>>to wait until layout to finish to start working on the new absolutely
>>positioned kids you found, and so on.
>>
>>2. The overhead of updating parents' overflow areas over and over
>>again.
>>In fact a page like above will result in O(n^2) updates of parents'
>>overflow areas where n is the number of nodes, unless I'm missing
>>something.
>>
>>Can we tweak the algorithm in some way to avoid these hazards?
>>
>>Patrick
>>
>>_______________________________________________
>>dev-servo mailing list
>>dev-servo@lists.mozilla.org
>>https://lists.mozilla.org/listinfo/dev-servo
>
>--
>Sent from my Android phone with K-9 Mail. Please excuse my brevity.
--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
_______________________________________________
dev-servo mailing list
dev-servo@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-servo
