block reflow state recovery is O(n) (making big text pages O(n^2))
Categories
(Core :: Layout: Block and Inline, defect, P5)
Tracking
()
People
(Reporter: waterson, Unassigned)
References
(Depends on 1 open bug, Blocks 1 open bug)
Details
(Keywords: perf)
Attachments
(1 file)
63.04 KB,
patch
|
Details | Diff | Splinter Review |
Spinning this off from bug 56854. From that bug: When we last left Our Heroes, they'd made the assumption that the O(n**2) behavior of RecoverStateFrom() was the culprit. Well, it is and it isn't. I've put together an atrocious hack that avoids doing _any_ state recovery by caching the nsBlockReflowState object's per-line data stuff. On my fast machine, it doesn't make a white of difference. Well, maybe a whit: page load time dropped from about 11s to about 9s -- regardless, a far cry from the ~55% win I was expecting. So I thought about this a bit, and realized that on a fast machine, the layout reflow timers don't fire often enough to exacerbate the O(n**2) behavior of state recovery. In other words, the fast machine slurps up enough data that we don't need to do very many reflows. Unfortunately, when we're running under Quantify, the timers fire at the same rate, but the ``crippled'' binary does much less work per unit of time. This leads to more incremental reflows, which makes the O(n**2) algorithm jump out. To justify my self-worth, I moved my build over to a very, very slow machine (166MHz running Win98). On this machine, it drops the layout time from over 70s to about 50s. (On this machine, IE5 loads the page in 11s.) I'll attach the patches I used. I'd like to discuss whether this is an approach worth pursuing or not.
Reporter | ||
Updated•23 years ago
|
Reporter | ||
Comment 1•23 years ago
|
||
Reporter | ||
Comment 2•23 years ago
|
||
The basic idea of the above patch is to - break the per-line state from nsBlockReflowState into its own struct - cache the accumulated per-line state for the next-to-last line, so that we don't need to RecoverStateFrom() in ReflowDirtyLines() The patch as it stands is a proof-of-concept, and doesn't work in the general case. (For example, it always ``fast-forwards'' to the next-to-last line's state, skipping any dirty lines before the last line.) All that it's good for, really, is testing long, simple web pages to see if load performance improves.
Comment 3•23 years ago
|
||
20% on big pages is also a great win and a fix to this will remove that noise from the quantify runs too.
Updated•23 years ago
|
Updated•23 years ago
|
Reporter | ||
Comment 4•23 years ago
|
||
dbaron is fixing this, and should probably just mark it as a dup of the bug where he's putting the patches.
Comment 5•22 years ago
|
||
Well, right now it's more of a meta-bug.
Comment 6•22 years ago
|
||
Bugs targeted at mozilla1.0 without the mozilla1.0 keyword moved to mozilla1.0.1 (you can query for this string to delete spam or retrieve the list of bugs I've moved)
Updated•22 years ago
|
Comment 7•22 years ago
|
||
Comments from bug 116437, which is about a 24MB file taking forever to layout. The jprof is at http://bugzilla.mozilla.org/showattachment.cgi?attach_id=65191 Typical: Mostly Reflowing lines: 12% direct (90% total) in ReflowDirtyLines() 4% total in nsFontCache::GetMetricsFor() 6% direct in nsBlockReflowState::RecoverStateFrom() 2% direct in nsBlockFrame::PropagateFloaterDamage() 3% total in nsFrame::Invalidate() 10% direct in nsLineBox::GetCombinedArea() 4% direct, 13% total in nsBlockFrame::ComputeFinalSize() 6% direct in nsBlockFrame::BuildFloaterList() 8% total in nsBlockFrame::PlaceLine() 1.5% total in nsCSSRendering::FindBackground 3% total in nsHTMLReflowState::nsHTMLReflowState 5% direct in nsFrameList::LastChild 10% total in nsRenderingContextGTK::GetTextDimensions()
Updated•22 years ago
|
Updated•22 years ago
|
Updated•22 years ago
|
Comment 9•22 years ago
|
||
Is this still valid?
Comment 10•22 years ago
|
||
Yes, although you'll notice that (the more serious) one of the two dependencies (the two parts of the problem) is fixed.
Updated•21 years ago
|
Comment 11•21 years ago
|
||
dbaron, is that covered by your layout architecture rewrite-plans?
Updated•21 years ago
|
Updated•21 years ago
|
Comment 12•20 years ago
|
||
No.
Updated•14 years ago
|
![]() |
||
Updated•14 years ago
|
Updated•12 years ago
|
Updated•12 years ago
|
Comment 13•12 years ago
|
||
Sorry, I've just added myself to the CC list, I don't know why here and in the other bug "Version" and "Target Milestone" got changed.
Updated•3 years ago
|
Updated•3 years ago
|
Comment 14•2 years ago
|
||
Meta bug with no activity for years (18 in this case), closing.
Comment 15•2 years ago
|
||
... only sort of a meta-bug, and I think still a real performance problem.
Comment 16•2 years ago
|
||
Looks like I didn't click on fixed anyway :)
Meta bug info removed.
Daniel, do you think we should spend on it?
Comment 17•2 years ago
|
||
I'm not clear on precisely what was tracked here and what still remained to be done.
I do see bug 86950 as an open dependency (one of two, per comment 10). dbaron, do you know if that was the only remaining thing here, or was there more being tracked here that was distinct from bug 86950?
(If it's just bug 86950, then I lean towards just duping this over to that bug at this point. I also don't know our float-manager code well enough to know offhand whether bug 86950 is still valid, but I assume it could be.)
Comment 18•1 year ago
|
||
Redirect a needinfo that is pending on an inactive user to the triage owner.
:jfkthame, since the bug has high severity and recent activity, could you have a look please?
For more information, please visit auto_nag documentation.
Updated•1 year ago
|
Comment 19•1 year ago
|
||
Let's just dupe this to bug 86950, per comment 17.
Description
•