19051 - {ib} extremely slow layout of page with many inline tags (<PRE> involved?)

Status: VERIFIED FIXED

(Core :: Layout, defect, P1)

Description

[barath]

I'm using Milestone 11 on a standard Redhat Linux 6.1 box, and viewing an image
that has been turned into a graphic such as the url provided, mozilla goes
extremely slow and becomes unresponsive for a long time.  This is in contrast to
netscape communicator or IE, which render and scroll with such an image
(text-image) rather quickly.

Thanks.

Comment 1

[tbutter]

the page is not there anymore

Comment 2

[Eli Goldberg]

Reassigning all of leger's unscreened Browser-General bugs to [e-mail]
for pre-screening and triage.

Comment 3

[John Morrison]

[e-mail] : can you check the URL for this bug report. I
don't understand the problem from the description, and the URL provided is
404 Not Found.

Comment 4

[John Morrison]

From [e-mail], by email to [e-mail]:

  "Try using the program png2html to create a html based image and then view
  it in mozilla."

So, as an example page already on the web, we can just use the png2html home
page : http://www.engr.mun.ca/~holden/png2html.html [Barath : is this a good
example of what you are seeing? (Add comments to this bug report).]

Using WinNT 1999122208, this takes roughly twice the time to render, as compared
to Nav4.7 on WinNT. However, I note that this bug report is specifically for
Linux, so the display may be even slower on Linux (based on the original
description [barath: can you quantify how much slower vs. Nav4.7 on Linux]).

Setting to 'Style System'/pierre for a further look (but maybe this is a
painting issue). (It's a fairly degenerate example, of course, but may point
out some possible areas to tune up.)

Comment 5

[Pierre Saslawsky]

It's slow on all 3 platforms. It is especially slow when:

- loading the page

- scrolling

- selecting several lines of text at once



Running with MOZ_PERF shows an unusally long reflow time. Reassigned to Troy.

Comment 6

[troy]

On my machine running NT and with the latest build it loads in a very reasonable
time.

However, it could be faster and so since it's all done with preformatted text
this is the known issue that the block code needs to be optimized for
preformatted text

Comment 7

[buster]

mass-moving bugs to M15

Comment 8

[buster]

this is actually pretty darn fast now.  acceptable for beta, moving to M16, 
lowering priority.  won't close out yet, this is still an interesting test case 
to profile.  If anybody wants to run a quantify profile of this, it would be 
VERy helpful!

Comment 9

[Dan Mosedale (:dmosedale, :dmose)]

*** Bug 24766 has been marked as a duplicate of this bug. ***

Comment 10

[Dan Mosedale (:dmosedale, :dmose)]

Upping the severity of this, as it makes mozilla completely unusable for viewing
large files in lxr such as:

http://lxr.mozilla.org/seamonkey/source/include/allxpstr.h#7570

Comment 11

[buster]

kipp is very unlikely to fix these, since he's not working ont he project any 
longer.  so I'll take a look.

Comment 12

[Kevin Puetz]

Now that we are post-beta, is there anyone actively working with this? It really
hurts LXR, and I have a gut feeling (but no data) that it's probably hard on
xmlterm too.

Comment 13

[Kevin Puetz]

well, post-beta branch anyway. I submitted too quickly :-)

Comment 14

[buster]

I doubt anyone will work on this before M17

Comment 15

[buster]

performance issues are high priority now.  Will try to look at this for M16.

Comment 16

[buster]

changed the summary.  It's a layout issue, not rendering. And <PRE> may or may 
not be involved at all.  It may be the sheer number of inline tags, in this 
case, <FONT>.  Trying to get quantify to play nice...

Comment 17

[buster]

one thing I noticed in quantify is the {ib} code to find "special" frames is 
killing us on large documents with long text runs.  Nisheeth is scheduled to fix 
this soon.  Nisheeth, when this part of the problem is fixed, please re-assign 
this back to me so I can find the next problem.

basically, the {ib} 'special' frame code is killing us, even though no inline 
element contains a block element.  ugg!

Comment 18

[Nisheeth Ranjan]

Accepting bug...

Comment 19

[Chris Waterson]

taking

Comment 20

[Chris Waterson]

Discovered a couple of things.

1. Long text runs with inlines get hosed because nsTextRun stores the run in a 
void array. Each span ends up as an entry here.

2. <pre>-formatted text with markup in it gets royally screwed here: generally 
the preformatted text is long, and for some reason we don't break the text run 
at the newline. It seems like we should probably do that. Any reason not to?

3. FindNextText() is called after measuring each new word: when the nsTextRun 
gets long, this becomes geometric and blows up.

Comment 21

[buster]

You'll have to experiment with suggestion (2).  Off-hand, it sounds like it 
should be ok.

Comment 22

[Blake Ross]

*spam* changing qa contact from [e-mail] to me ([e-mail]) 
on 121 open or resolved (but not verified) bugs.  sorry for the spam everybody, 
but most of these bugs would just remain dormant and not checked by QA 
otherwise.  I'm not sure how so many bugs have nobody as their QA contact, but 
I suspect this is the fault of some sort of bugzilla corruption that happened 
at some point (most of these bugs are in the 20000-26000 range, and I don't see 
where in the activity log that QA contact explicitly changed to 
[e-mail])

Anyways, sorry again for spam.  If you really get annoyed, I'm usually 
available in #mozilla on IRC for torture.

Comment 23

[Chris Waterson]

Attachment: use JS's double-hashtable to maintain the framelist in nsTextRun

Comment 24

[Chris Waterson]

Attachment: Better patch: get rid of nsTextRun altogether.

Comment 25

[Chris Waterson]

So I think the second patch is a better approach. Namely, get rid of nsTextRun 
altogether, and make nsLineLayout::FindNextText() grovel over the frame tree to 
find the next text frame.

The only concern that I have with this patch is that I undid the lazy parent 
pointer fixup stuff that troy did to fix bug 5588. Specifically, when overflow 
frames are pulled to newly created line boxes, troy had it set up s.t. their 
parent pointers would continue to refer to their original frames until reflow 
occurred. This makes it difficult to walk the frame tree :-).

I experimented with the test cast in 5588. Specifically, I backed troy's 
changes out of an otherwise clean tree. I was not able to observe a significant 
difference in performance (using the ultra-scientific "one mississippi, two 
mississippi" method).

Comment 26

[Chris Waterson]

     Subject: Re: nsTextRun
        Date: Thu, 13 Jul 2000 08:28:47 -0700
        From: Troy Chevalier <[e-mail]>
Organization: Tellme
          To: Chris Waterson <[e-mail]>

Chris Waterson wrote: 

  There is a fly in the ointment, though. I needed to undo the change that 
  you made to lazily set the overflow frames' parent pointers when 
  reflowing new lineboxes that get created on resize reflows. (I suppose I 
  could leave the change in, and add another eager detection case, but...) 

  I went back to the original test case (that big javadoc thing), and 
  honestly couldn't see a visible difference in layout speed after 
  removing the lazy parent pointer stuff. Was there another, better test 
  case I should look at?

That's an interesting issue. The main reason you don't see a layout change is 
because of this code in nsInlineFrame::Reflow(): 

  // When pushing and pulling frames we need to check for whether any 
  // views need to be reparented. 
  nsHTMLContainerFrame::ReparentFrameViewList(aPresContext, prevOverflowFrames, 
                                              prevInFlow, this); 

That's a new function that I added. Previously what happened is that in a loop 
we would call ReparentFrameView() once for each frame in the overflow list. That 
was the major performance problem, because each call did the exact same [very
expensive] check to see whether we needed to reparent the view or not 

Now that we make just the one call we only do that work once. Note that there is 
lots of layout code that is still using the old way, and it doesn't matter in 
galley mode but it's a performance problem in page mode 

There was a second reason performance was suffering, and that was because 
nsFrameList::InsertFrames() was walking the child list twice. The first time 
through it was calling SetParent() for each frame, and then it was calling 
LastChild() to get the last frame in the list. I changed the code that sets the 
parent frame to remember the last frame, and that made in O(n) instead
of O(2n) 

That may not seem like a big deal, but the scenario that was causing problems 
was something like this: 

<body> 
<span> 
everything in this span (100,000 elements) 
</span> 
</body> 

That's the worst case scenario, because we reflow the first line and only five 
word fit. So we push 99,995 elements to the next line, and for each one we 
called ReparentFrameView() and did the O(99,995 * 2) InsertFrames() operation. 
Then we fit five frames on the next line and pushed 99,990 frames to the next 
line, ... 

You get the idea. 

So skipping setting of the parent frame pointer if possible is still a good 
idea, because it saves us O(n). It's only an issue for large documents, but 
that's always been the problem area for us 

-Troy 
  

Comment 27

[Chris Waterson]

I tried the test case that troy described (1Mb of text in a span), and saw no 
measurable difference with and without my patch. I *did* see a small difference 
on the original test case from bug 5588:

  http://java.sun.com/products/jdk/1.3/docs/api/allclasses-frame.html

On my machine, 4.1s without the patch, 5.4s with the patch (that's a degradation  
of over 20%). I'm profiling now to see what I can find. That test case has a 
long run of formatted HTML inside a table cell.

Comment 28

[Chris Waterson]

In a subsequent email, troy pointed out that my test case was invalid because it 
only contained a single, long text frame. I tried it on a much larger test case 
(an LXR page contained inside of a <span> instead of a <pre>), and noticed 
marginal differences: 29s without the patch, 32s with the patch (10% 
degradation).

On LXR *with* a <pre> tag, the patch is a bigger win: from 35s without the patch 
do 25s with the patch (28% improvement).

At this point, my feeling is that removing the lazy parenting, and doing frame 
crawling is a net win:

1. (+) we avoid updating nsTextRun during incremental reflows
2. (+) we avoid storage overhead of the nsTextRun data (which saves us an 
nsVoidArray and its contents per block frame)
3. (-) we need to keep the parent pointers in sync eagerly to support frame 
walking during line wrapping.

I'll update my patch to leave the mSetParentPointer in mInlineFrame, and will 
experiment with this later to see if it's possible to do both lazy parent 
setting and frame crawling.

Comment 29

[Chris Waterson]

Attachment: Even better patch, do it without messing with lazy-parent-setting

Comment 30

[Chris Waterson]

Attachment: ok, one more time. this patch isn't edited by hand.

Comment 31

[Chris Waterson]

Attachment: use nsStyleDisplay to detect outermost block frame, not nsLayoutAtoms::blockFrame

Comment 32

[ekrock's old account (dead)]

[HAVE FIX] for perf issue. PDT please approve.

Comment 33

[Andrew Thompson]

Add self to CC

In an attempt to say something useful in this spam, this bug:
http://bugzilla.mozilla.org/show_bug.cgi?id=2611
has some performance numbers on Mac for JDK 1.1 JavaDoc, which may be of 
interest.

Comment 34

[Chris Waterson]

fix checked in. bye bye, nsTextRun.

Comment 35

[Andrew Thompson]

Can you let us know which nightlies have this in, so I can check whether the 
Javaoc loading issues have been solved?

Comment 36

[Chris Waterson]

M18 builds from 2000-07-28 and later have the fix.

Comment 37

[Andrew Thompson]

Doing the same test on the JavaDoc file AllNames.html that I was talking about in 
bug 2611, the 28 Jul M18 build performs as follows:

Loading from network @ java.sun.com: 26.4 seconds
Loading from local disk:29.8 seconds

Conversley the M17 28 July build (which doesn't have this fix)

Loading from network: 60 secons
Loaing from disk: 90 seconds

So congrats - this fix is a huge improvement!

Still doesn't match Nav4 at 15 seconds from the local disk, but its pretty good.

I'm still curious as to how loading a file from disk can be *slower* than from 
the network. Should I file a bug on this?

Comment 38

[Chris Waterson]

cc'ing gagan: what do you think of the above comments? (re: network faster than 
file)

Comment 39

[Blake Ross]

QA assigning to petersen to verify

Comment 40

[Chris Petersen]

Marking verified in the 2001010203 build.