W3C home > Mailing lists > Public > www-style@w3.org > October 2011

[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>
To: www-style@w3.org
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 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 17:20:45 GMT