Re: [css3-flexbox] Computing "hypothetical size" of nested flexboxes might require O(n^2) algorithm?

Sorry for the delay - I was wanting to finish the first draft of the
layout algorithm before I commented, but that's taking longer than
expected due to other things cropping up.

On Tue, Oct 11, 2011 at 3:04 PM, Daniel Holbert <dholbert@mozilla.com> wrote:
> Hi www-style,
>
> I'm worried about the performance impacts of computing the "hypothetical
> size" of flexbox items -- this "hypothetical size" was  hinted at in one of
> the recent updates to Section 7 of http://dev.w3.org/csswg/css3-flexbox/
>
> In particular, I think it might require an O(n^2) algorithm. (n = depth)
>
> Quoting a snippet of that section:
> ====
> ISSUE 11
> Here I'll outline the general structure of the layout algorithm, before I go
> into the ugly details below.
> [...]
> 2. Pretend that the flexbox is display:block, and still establishes a BFC.
> Pretend that the flexbox item is the only child of the flexbox (and also
> establishes a BFC). Resolve flexible widths/heights into their preferred
> sizes. Resolve ‘auto’ widths/heights by shrinkwrapping them. Using all this
> pretend knowledge, resolve the width and height.
> [...]
> 4. Based on both of these, linebreak the flexbox if it's multiline.
> 5. Resolve any flexible lengths. All items now have a real main size.
> ====
>
> If I understand correctly, this means we have to do 2 reflows for each
> flexbox item that has a flexible width:
>  (1) one where we pretend to be a block (to compute the hypothetical size of
> our items, for the preferred-size input to flexbox algorithm)
>  (2) another after we've broken into lines and resolved flexible widths.
>
> This means that if we have N nested flexboxes, it'll require O(N^2) work to
> lay them out.

As Tony says, this is only true if the flexboxes and the flexbox items
are all auto-sized.  If they have a definite size, the layout is
simple and doesn't depend on the size of descendants.  Items defined
simply with "width: flex(1)" or similar have a preferred size of 0px,
so that hits the fast track.  You do still have to do a layout for the
hypothetical height, but you'd have to do that at some point anyway,
and if the width is a definite size, I don't think you'll need to
recalculate it.

As well, commonly "width: auto" will just compute as "fill" (or
whatever we end up calling the "whatever blocks do by default" value),
which just takes the width of the flexbox itself, and so is also fast.

~TJ

Received on Tuesday, 18 October 2011 23:52:05 UTC