264839 - Column balancer doesn't perform well when there can be column breaks anywhere

Status: RESOLVED FIXED

(Core :: Layout, defect)

Description

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

The column balancer has a heuristic so that when the search window for the
column height is narrower than 600 twips, the balancer switches from binary
search to linear search by decreasing height. For normal content (e.g., text in
lines) this is effective because each time we decrease the height by one twip,
we wrap one or more lines from one column to the next, and the balancer can
generally determine that more than one twip's worth of space is now available at
the bottom of the columns, so it can advance the search by that amount instead
of just one twip.

I'll attach a testcase but it boils down to column set containing an empty DIV
with a specified height. The DIV can therefore be broken anywhere. Every time
the balancer decreases the height constraint by one twip, the DIV breaks just
one twip closer to the top, so the balancer proceeds in steps of one twip,
potentially requiring hundreds of reflows to close the 600 twip window.

I will solve this problem by having the balancer detect when it only made one
twip's worth of progress and reverting to binary search all the rest of the way.

Comment 1

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

Attachment: testcase

Demonstrates the problem ... when you resize the window, whenever the column
count changes there's a noticeable delay while we reflow the block a few
hundred times.

Comment 2

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

Attachment: fix

Fix, as described.

Comment 3

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

checked in