Closed Bug 78911 Opened 24 years ago Closed 2 years ago

block reflow state recovery is O(n) (making big text pages O(n^2))


(Core :: Layout: Block and Inline, defect, P5)






(Reporter: waterson, Unassigned)


(Depends on 1 open bug, Blocks 1 open bug)


(Keywords: perf)


(1 file)

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.
Blocks: 56854
Keywords: donttest, perf
Priority: -- → P3
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.
20% on big pages is also a great win and a fix to this will remove that noise 
from the quantify runs too.
Summary: block reflow state recovery is O(n) → block reflow state recovery is O(n) (making big text pages O(n^2))
dbaron is fixing this, and should probably just mark it as a dup of the bug
where he's putting the patches.
Assignee: waterson → dbaron
Well, right now it's more of a meta-bug.
Severity: normal → major
Keywords: meta
Priority: P3 → P5
Target Milestone: --- → mozilla1.0
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 
Target Milestone: mozilla1.0 → mozilla1.0.1
Target Milestone: mozilla1.0.1 → mozilla0.9.9
Blocks: 114584
Comments from bug 116437, which is about a 24MB file taking forever to layout.
The jprof is at
  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()
Target Milestone: mozilla0.9.9 → Future
Attachment #33191 - Flags: needs-work+
Keywords: mozilla1.0+
remove self
Keywords: patch
Is this still valid?
Yes, although you'll notice that (the more serious) one of the two dependencies
(the two parts of the problem) is fixed.
Component: Layout → Layout: Block & Inline
dbaron, is that covered by your layout architecture rewrite-plans?
Flags: blocking1.4?
Flags: blocking1.4? → blocking1.4-
Blocks: 116437
Blocks: 203448
QA Contact: chrispetersen → layout.block-and-inline
Target Milestone: Future → mozilla14
Version: Trunk → Other Branch
Target Milestone: mozilla14 → ---
Version: Other Branch → Trunk
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.
Assignee: dbaron → nobody
Summary: block reflow state recovery is O(n) (making big text pages O(n^2)) → [meta] block reflow state recovery is O(n) (making big text pages O(n^2))

Meta bug with no activity for years (18 in this case), closing.

... only sort of a meta-bug, and I think still a real performance problem.

Looks like I didn't click on fixed anyway :)
Meta bug info removed.

Daniel, do you think we should spend on it?

Flags: needinfo?(dholbert)
Keywords: meta
Summary: [meta] block reflow state recovery is O(n) (making big text pages O(n^2)) → block reflow state recovery is O(n) (making big text pages O(n^2))

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.)

Flags: needinfo?(dholbert) → needinfo?(dbaron)

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.

Flags: needinfo?(dbaron) → needinfo?(jfkthame)
Flags: needinfo?(jfkthame)

Let's just dupe this to bug 86950, per comment 17.

Closed: 2 years ago
Resolution: --- → DUPLICATE
You need to log in before you can comment on or make changes to this bug.