Hi everyone,
Just wanted to weigh in about the algorithm mentioned by Boris and Patrick
above:
I think it won't work for calculating height for absolutely positioned elements
because we aren't calculating the static position y-coordinate anywhere. This
needs to be done by adding up the heights of all the "frames" between the
hypothetical box and the actual Containing Block.
The dependency is like
(assign-height for in-flow frames) ->
(calculate static position y-coordinate for hypothetical boxes) ->
(assign-height for absolutely positioned elements) ->
(send back overflow from absolutely positioned elements)
This seems to suggest that we need some sort of a traversal after the normal
assign-heights traversal.
Proposal: If it is safe to keep track of the absolute containing blocks,
absolute frames, and hypothetical frames separately (similar to what Boris
suggested), then we could:
+ (1) Run assign-width and assign-height on the whole flow tree exactly as
usual, just not assigning the height for absolute frames.
+ (2) Traverse back to the containing block from each hypothetical frame to
calculate the static position y-coordinate
+ (3) Calculate height for each absolute frame - this would not need a further
traversal. You can just look up the containing block height and static y
position. The content height would be calculated during normal layout.
+ (4) For each absolute frame, calculate overflow and propagate it up
efficiently using Patrick's absolute_children count method.
Note that nested absolute frames would need to be handled sequentially cos the
kid depends on the parent's calculated height. This is basically a top-down
traversal of the "absolute-frame-tree".
If the above algo is safe and doable, then we can optimize it further by
starting step (3) on an absolute frame as soon as we are done with the static
y-coordinate for its hypothetical frame. And step (4) can follow immediately
after step (3).
What do you think?
On Friday, February 14, 2014 9:17:38 AM UTC+9, Patrick Walton wrote:
> 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
