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:
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]...

Am I getting this right?  And (if so), is it possible to avoid this problem?

Received on Tuesday, 11 October 2011 22:05:11 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 11 February 2015 12:34:58 UTC