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

My understanding is that you are correct, it's possible to get O(n^2)
behavior with the new flexbox.  Note that this is much better than the old
flexbox which could get O(m^2) where m is the number of flex items. In the
nested case, old flexbox would get O(m^(2n)).  It was pretty much impossible
to get decent performance with the old flexbox even with a single nesting.

Also, although it's possible to get O(n^2), it can be avoided by web
developers if you don't use auto for the preferred size.  You only have to
compute the hypothetical size for auto.  Since auto is not the default, I
think it'll be rare to end up in this case.

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/<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.  For example, I think we'd have O(N^2) behavior for content
> like this:
>
> <div style="display: flexbox; width: 200px">
>  <div style="display: flexbox; width: flex(1 0 auto)">
>    <div style="display: flexbox; width: flex(1 0 auto)">
>     ...[N of these, maybe with some text at the center]...
>    </div>
>  </div>
> </div>
>
> Am I getting this right?  And (if so), is it possible to avoid this
> problem?
>
> Thanks,
> ~Daniel
>
>