Closed Bug 61962 Opened 21 years ago Closed 20 years ago

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

Categories

(Core :: Layout, defect, P3)

x86
Linux
defect

Tracking

()

RESOLVED FIXED
mozilla0.9.6

People

(Reporter: dbaron, Assigned: dbaron)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

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...
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?
Priority: P3 → P1
Status: NEW → ASSIGNED
Target Milestone: --- → mozilla0.9
Keywords: perf
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!
Keywords: donttest
Reality check.  Moving out to 0.9.1.
Target Milestone: mozilla0.9 → mozilla0.9.1
Target Milestone: mozilla0.9.1 → mozilla0.9.2
Summary: O(N^2) usage of nsBlockFrame::PropogateReflowDamage → O(N^2) use of nsBlockFrame::PropogateReflowDamage
Target Milestone: mozilla0.9.2 → mozilla0.9.3
Blocks: 86952
Priority: P1 → P3
Target Milestone: mozilla0.9.3 → mozilla0.9.4
Target Milestone: mozilla0.9.4 → mozilla0.9.5
Looks like a worthwhile win for large pages.  Would this have any effect on
DHTML pages?
This is fixed in my patch on bug 86947.
Depends on: 86947
Target Milestone: mozilla0.9.5 → mozilla0.9.6
Fixed by checkin of bug 86947 at 2001-10-24 18:08 PDT.
Status: ASSIGNED → RESOLVED
Closed: 20 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.