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

Status: RESOLVED DUPLICATE of bug 86950

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

Description

[Chris Waterson]

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.

Comment 1

[Chris Waterson]

Attachment: cache last line's state (work in progress)

Comment 2

[Chris Waterson]

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

[Daniel Bratell]

20% on big pages is also a great win and a fix to this will remove that noise 
from the quantify runs too.

Comment 4

[Chris Waterson]

dbaron is fixing this, and should probably just mark it as a dup of the bug
where he's putting the patches.

Comment 5

[David Baron :dbaron:]

Well, right now it's more of a meta-bug.

Comment 6

[Asa Dotzler [:asa]]

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)

Comment 7

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

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

Comment 8

[basic]

remove self

Comment 9

[Markus Hübner]

Is this still valid?

Comment 10

[David Baron :dbaron:]

Yes, although you'll notice that (the more serious) one of the two dependencies
(the two parts of the problem) is fixed.

Comment 11

[Markus Hübner]

dbaron, is that covered by your layout architecture rewrite-plans?

Comment 12

[David Baron :dbaron:]

No.

Comment 13

[Marco Castelluccio [:marco]]

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.

Comment 14

[Sylvestre Ledru [:Sylvestre]]

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

Comment 15

[David Baron :dbaron:]

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

Comment 16

[Sylvestre Ledru [:Sylvestre]]

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

Daniel, do you think we should spend on it?

Comment 17

[Daniel Holbert [:dholbert]]

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

[Release mgmt bot [:suhaib / :marco/ :calixte]]

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.

Comment 19

[Daniel Holbert [:dholbert]]

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