61962 - O(N^2) use of nsBlockFrame::PropogateReflowDamage

Status: RESOLVED FIXED

(Core :: Layout, defect, P3)

Description

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

In a profile of loading a particularly large version of
http://www.mozilla.org/projects/seamonkey/reports/ns6analysis.html , I saw that
nsBlockFrame::PropogateReflowDamage and its immediate children took about 50% of
the time.

It seems to me that there's an O(N^2) mess going on here.
nsBlockFrame::ReflowDirtyLines can call nsBlockFrame::PropogateReflowDamage for
each line, and then nsBlockFrame::PropogateReflowDamage loops over all the lines.

While we're here, we should also correct the spelling of propagate if we don't
remove the function entirely...

Comment 1

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

This doesn't look too hard to fix, although the math will be a little fun.
(I'll probably write a little class for ranges on a number line to handle the
first half of PropagateReflowDamage as we go.)

One thing I don't understand is the |return| about halfway through
PropogateReflowDamage -- I wonder what would happen if there's an aDeltaY.  It
seems to me like a bug, and one that I would be hard pressed not to fix with a
different solution.  But could it be intentional?

Comment 2

[Hixie (not reading bugmail)]

Marking donttest to get this off the managerial radar. David: If you want a test
case for this, remove 'donttest', mark it qawanted, and set me as the QA contact.
Thanks!

Comment 3

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

Reality check.  Moving out to 0.9.1.

Comment 4

[Randell Jesup [:jesup] (needinfo me)]

Looks like a worthwhile win for large pages.  Would this have any effect on
DHTML pages?

Comment 5

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

This is fixed in my patch on bug 86947.

Comment 6

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

Fixed by checkin of bug 86947 at 2001-10-24 18:08 PDT.