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

From: Daniel Holbert <dholbert@mozilla.com>
Date: Tue, 11 Oct 2011 15:04:31 -0700
Message-ID: <4E94BD6F.9040004@mozilla.com>

```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.  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
```
Received on Tuesday, 11 October 2011 22:05:11 UTC

This archive was generated by hypermail 2.3.1 : Monday, 2 May 2016 14:38:51 UTC