462307 - Speed up columns case hit by HTML5 spec

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: fix

I noticed that the HTML5 spec uses -moz-column-width. That's applied to a really big table (the table of all HTML entities). Unfortunately we don't break tables across column boundaries, so it doesn't do anything useful. Even more unfortunately, it slows down our layout *a lot* because when we reflow the column set, we do a binary search for the correct balanced column height; in my testing it reflows the table 15 times to find that height (and each reflow is quite expensive since the table is huge and we're adjusting the available height, so we can't optimize it very well).

I'm attaching a patch. The idea is to observe that when a column doesn't fit in its available height, that means there's no break opportunity inside the content of that column. So, no height less than that column's height is a feasible height for the balanced column set. Using that fact, we can reflow a column set containing a single non-breakable element (like a table) in just three iterations:
-- First, we reflow with unconstrained height to find the single-column height of the table (which gives us a feasible height)
-- Then we reflow with some reduced height to try to balance the columns. It fails to fit, and returns the same desired height as the first iteration; we learn that no smaller height than the desired height will work
-- So we reflow again with that desired height, and we're done.

Comment 1

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: testcase

Load the testcase, wait for the load to finish, then zoom. The relayout does 11 iterations of the column balance algorithm, for me on trunk. With the patch, it's only 3.

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 345455 [details] [diff] [review]
fix

>+        // If the first column's available height was constrained, and
>+        // it didn't fit, its current height must be its minimum height
>+        // and therefore no smaller height can be feasible.

Doesn't this statement apply to any column?  Shouldn't we also apply this fix to:

<div style="column stuff">
  <p>caption</p>
  <table>really big table</table>
</div>

?

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Yes. In fact, I had a patch to do that, but I seem to have attached the old patch (and lost the new one) :-(.

Comment 4

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Attachment: fix v2

Correct patch

Comment 5

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Comment on attachment 346183 [details] [diff] [review]
fix v2

r+sr=dbaron

Comment 6

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Changeset 469a48d37280