Large text document take 21X longer to load than in 4.x

RESOLVED INCOMPLETE

Status

()

--
major
RESOLVED INCOMPLETE
18 years ago
3 months ago

People

(Reporter: kmcclusk, Unassigned)

Tracking

(Depends on: 1 bug, 4 keywords)

Trunk
Future
hang, perf, testcase, topperf
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [reflow-refactor], URL)

Attachments

(2 attachments)

(Reporter)

Description

18 years ago
I created a 12Mb local file as a test case of the following form:

<HTML>
<BODY>
<P> Large text documents take too long to load
<P> Large text documents take too long to load
<P> Large text documents take too long to load
....
</BODY>
</HTML>

(I won't attach my test case since it's huge and it's easy to recreate)


This file takes about 15 seconds to load in Nav4.x. (While its loading the UI in
Nav is very responsive, you can scroll - select menus etc.)

This file takes about 18 seconds to load in I.E. 5.5 (While its loading the UI
is responsiveness is marginal.)

This file takes 317 seconds to load in 2001032004 trunk release build. (The UI
responsiveness is better than I.E but not as good at Nav4.x

With the user_pref for "content.notify.interval" set  2500000 instead of 1000000
it takes 650 seconds to load. (The UI responsiveness if good but not as good as
Nav4.x)

All of the time is being consumed in the processing of individual reflow
commands. I added printf's before and after processing each pending reflow in
nsPresShell.cpp. You can actually see it pause for several seconds for each reflow.

We need to run a profiler while loading this page to determine why it is
spending so much time in reflow.
(Reporter)

Updated

18 years ago
Keywords: topperf

Comment 1

18 years ago
Does it make any difference if you close all those <p> tags?

Comment 2

18 years ago
Shouldn't have to close <p> tags, that is optional.

I am testing this bazillions of <P> elements and with just bazillions of lines
of text in a single <p> to see the difference....
Status: NEW → ASSIGNED

Comment 3

18 years ago
isn't it a dupe of bug 67756 (File loads ~14X slower than NS4.76)?

Comment 4

18 years ago
kmike - yes, it sure looks like the same problem report. I'm gonna keep this
open thought, while I test it myself for a while. I'll report my findings in the
bug and dup this when I have somehting interesting. Thanks.
Depends on: 67756

Updated

18 years ago
Blocks: 71668

Comment 5

18 years ago
Reassigning to waterson and moving to m1.0.
Assignee: attinasi → waterson
Status: ASSIGNED → NEW
Target Milestone: --- → mozilla1.0

Updated

18 years ago
Status: NEW → ASSIGNED
(Reporter)

Comment 6

17 years ago
*** Bug 104429 has been marked as a duplicate of this bug. ***

Comment 7

17 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)
Target Milestone: mozilla1.0 → mozilla1.0.1

Comment 8

17 years ago
don't move bugs that are in the 1.0 dependency tree. sorry.

Target Milestone: mozilla1.0.1 → mozilla1.0

Updated

17 years ago
Target Milestone: mozilla1.0 → Future

Comment 9

17 years ago
I'm not sure is this the reason, but Mozilla basically locks
for ages (I watied at least 5 mins for the following link)
at 100% CPU load when loading:
http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/ChangeLog?cvsroot=glibc

Updated

17 years ago
Keywords: mozilla1.0+

Updated

17 years ago
Keywords: nsbeta1

Comment 10

17 years ago
Isn't it best to mark this bug a duplicate of bug 67756?

Updated

16 years ago
QA Contact: petersen → praveenqa

Comment 11

16 years ago
Created attachment 104042 [details]
Link to a 13.83 MB Document (text)

Tested on W2K Build ID:2002102108 trunk/
responsiveness better than I.E6.0 still slow

Updated

16 years ago
Keywords: testcase
Blocks: 168638
No longer blocks: 168638

Updated

16 years ago
QA Contact: praveenqa → dsirnapalli

Comment 12

16 years ago
adt: nsbeta1-
Keywords: nsbeta1 → nsbeta1-
On the testcase in comment 11, I see us taking most of our time on what I'd
expect -- style resolution, frame construction, reflow.  No obvious hotspots...

Comment 14

15 years ago
*** Bug 235022 has been marked as a duplicate of this bug. ***

Comment 15

15 years ago
Regarding the test case listed in 235022: there are multiple files available at
that site.  The two that I used to test it were
http://wso.williams.edu/~bchaffin/patersons_worms/worm_draw/hash062a-draw.gz and
http://wso.williams.edu/~bchaffin/patersons_worms/worm_draw/hash061-2.3e18-draw.gz.
 The former (which is about 11 MB uncompressed) takes about 9 minutes of CPU
time on my 1000 MHz system and the latter (about 15 minutes uncompressed) takes
about 17 minutes, suggesting quadratic behavior.  This test was conducted by
loading both files into a fresh browser on the command line via file: URL's and
immediately minimizing them to avoid issues with redraw requests from X.  I then
waited for them to stop accumulating CPU time.

These files are both ASCII text files consisting of a single very long line of
text.  The observed behavior is that the file very quickly starts to display,
with a horizontal scrollbar, but the throbber continues to move very slowly and
the browser otherwise doesn't respond while processing.

Again, since this is a text file, there are no frames, styles, or any other
layout elements involved.

Comment 16

15 years ago
I ran the same test on Netscape 4.8.  It was also quadratic, although the times
were 2:10 and 1:10 respectively for the large and small file (about 8x faster).
 The quadratic behavior was also evident in the status line as it displayed how
much of the document was loaded and the "download" speed, which was steadily
decreasing (slowing down) as more was loaded (this is a local file on my
filesystem, so download speed itself is on the order of 20 MB/sec at least,
probably more since the file would be in memory after a repeat).

Is something trying to realloc storage for some display element, and increasing
its storage by a fixed amount rather than e. g. doubling the request each time?
Bug 235022 is not a duplicate of this bug, so please disregard comment 15 and
comment 16....

Updated

15 years ago
Assignee: waterson → nobody
Status: ASSIGNED → NEW
QA Contact: dsirnapalli → core.layout
*** Bug 290166 has been marked as a duplicate of this bug. ***

Comment 19

14 years ago
Is it time to look at our plain text rendering perf? Try loading the URL.
Keywords: perf
Before I do anything else with the URL, that document is 109MB of text.  Given
that we try to render it incrementally, that would mean that it would take
forever pretty much no matter what as long as we have anything at all O(N) in
incremental rendering (which would make pageload O(N^2)).
So profiling that testcase (or rather part of pageload for that text file after
I saved it locally and gunzipped it) we have:

Total hit count: 568242
Count %Total  Function Name
94851   16.7     nsBlockFrame::ReflowDirtyLines(nsBlockReflowState&, int)
93864   16.5     nsBlockFrame::ComputeCombinedArea(nsHTMLReflowState const&,
nsHTMLReflowMetrics&)
78108   13.7     nsBlockFrame::BuildFloatList(nsBlockReflowState&)
29400   5.2     nsBlockReflowState::RecoverStateFrom(nsLineList_iterator, int)
20359   3.6     nsRect::UnionRect(nsRect const&, nsRect const&)
15689   2.8     nsFontMetricsGTK::GetTextDimensions(unsigned short const*,
unsigned, nsTextDimensions&, int*, nsRenderingContextGTK*)
13531   2.4     uMapCode
11539   2.0     LineHasClear(nsLineBox*)
10662   1.9     nsLineBox::CachedIsEmpty()
6946   1.2     nsUnicodeEncodeHelper::ConvertByTable(unsigned short const*,
int*, char*, int*, uShiftTableMutable const*, unsigned short const**)
6037   1.1     nsTextTransformer::ScanPreAsciiData_F(int*, int*)
5978   1.1     nsBlockFrame::PropagateFloatDamage(nsBlockReflowState&,
nsLineBox*, int)

The rest is below 1%.  All this is just standard block layout stuff.

So the fundamental problem is that we fully lay out the whole page.  This is
done because as far as we're concerned "plaintext" is just a special case of
HTML, and in HTML we need to do all the layout to get things like CSS
positioning right...

If we really want to make plaintext super-fast that would involve some sort of
evil a la nsListBoxBodyFrame where we only create layout objects for the
"currently visible" stuff... and then the question is whether it's worth the
large amount of work that would take.

Oh, note that BuildFloatList, ComputeCombinedArea, and ReflowDirtyLines are all
exactly O(N) in the number of lines the block has.  For incremental rendering
that means that we get O(N^2) overall growth.

Comment 22

14 years ago
In Camino we're spending a lot of time doing Unicode text conversions in Mac GFX
in order to measure text. I'm not sure why we're not going through the faster
ASCII code path in nsTextFrame (maybe some charset detector thing?).
Hmm.. maybe.  I have autodetect off, and the page ends up ISO-8859-1.... It's a
file list, so I wouldn't expect it to have non-ASCII chars exactly.

Maybe file a separate bug on that and see what's going on?
(In reply to comment #21)
> So the fundamental problem is that we fully lay out the whole page.  This is
> done because as far as we're concerned "plaintext" is just a special case of
> HTML, and in HTML we need to do all the layout to get things like CSS
> positioning right...

That testcase isn't actual 'plaintext' though, it is HTML, so we'd need
something fancier than just detecting text/plain.
 
> If we really want to make plaintext super-fast that would involve some sort of
> evil a la nsListBoxBodyFrame where we only create layout objects for the
> "currently visible" stuff... and then the question is whether it's worth the
> large amount of work that would take.

Maybe, if we could find the simplest possible way to do it. I think we'd do
something like this:
-- have the style system set flags to indicate whether certain "troublesome"
styles occur at all in a document (e.g. 'position' anything but static,
'line-height' (negative))
-- have the style system also set a 'tolerance' value on the document (e.g., the
maximum height of outlines)
-- when no troublesome styles are present, simply abort reflow when
nsBlockReflowState.mY is greater than the viewport's scrollport YMost plus the
tolerance.
-- Re-reflow whenever the viewport scrolls down
So we'd still do frame construction for all content, but lines below the bottom
of the viewport would not be reflowed so we wouldn't break them. I bet this
would crush pageload time for stuff like LXR.

> Oh, note that BuildFloatList, ComputeCombinedArea, and ReflowDirtyLines are
> all exactly O(N) in the number of lines the block has.  For incremental
> rendering that means that we get O(N^2) overall growth.

We could fix those with auxiliary persistent data structures (and just removing
BuildFloatList), but ReflowDirtyLines would be particularly difficult to get right.
> That testcase isn't actual 'plaintext' though, it is HTML

The testcase in the URL field isn't (served as gzipped text/plain).  The wonders
of mutating bugs... ;)

ReflowDirtyLines might work ok if we had a fast way to get to the first dirty
line....
for pure content appends, yeah, we could do something, as long as there aren't
too many floats. But if a dirty line changes height then we have to reposition
all lines below it.
(In reply to comment #24)

One problem with that plan is that we'd have to do something to estimate the
height of the window to get scrollbars to work.
Sure.  If something happens in mid-document, not much we can do about that...
but the common case for this sort of thing is in fact content appends.
Current data:

The testcase at http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/ChangeLog?cvsroot=glibc loads in about 85 seconds on trunk (about 75.6 seconds on the reflow branch).  For comparison, Opera 9 loads it in about 50 seconds.
Whiteboard: [reflow-refactor]
Loading of this page 
http://www.gnoware.org/Documents/intro-linux
on very slow PC ~250MHz and 64Mb RAM take ~35 sec.

For Opera loading time ~ 20 sec.

See gnu profile in attachment

Created attachment 244689 [details]
Gnu profile data for intro-linux page
Attachment #244689 - Attachment filename: result11.out.gz → result11.txt.gz
Last profile was created for REFLOW_BRANCH_20061031.

This bug is about text/plain files.  If your file is not text/plain, it's not this bug.
(In reply to comment #33)
> This bug is about text/plain files.  If your file is not text/plain, it's not
> this bug.
> 

Hum.... but this page "http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/ChangeLog?cvsroot=glibc" 
Also not text/[lain file..... I have checked this page also ... profile almost the same :(
(In reply to comment #34)
> (In reply to comment #33)
> > This bug is about text/plain files.  If your file is not text/plain, it's not
> > this bug.
> > 
> 
> Hum.... but this page
> "http://sources.redhat.com/cgi-bin/cvsweb.cgi/libc/ChangeLog?cvsroot=glibc" 
> Also not text/[lain file..... I have checked this page also ... profile almost
> the same :(
> 

But ok, I will try to find same  bug, for not only text pages... or will create fresh bug...

> Hum.... but this page

Was basically an attempt to hijack the bug.  See comment 25.  I'd forgotten that when I made comment 29...

And _please_ do not quote comments in their entirety.  Quote as little as you can.  Anything else makes the bug unreadable.
https://bugzilla.mozilla.org/attachment.cgi?id=104042 eventually hangs the UI for a good long time, on Vista anyway, pounding a 2.4GHz core duo
Mozilla/5.0 (Windows; U; Windows NT 6.0; en-US; rv:1.9.1b3) Gecko/20090305 Firefox/3.1b3
Severity: normal → major
Keywords: hang
(In reply to Wayne Mery (:wsmwk) from comment #37)
> https://bugzilla.mozilla.org/attachment.cgi?id=104042 eventually hangs the
> UI for a good long time

The first link or internal link in the attachment's fine.
The second link causes the hang.
Vista Basic, x86, FF 10.0.2

Updated

5 years ago
Duplicate of this bug: 419937
Second link points to https://sourceware.org/viewvc which IMO must have changed.
No other useful testcases that I can see
Status: NEW → RESOLVED
Last Resolved: 3 months ago
Resolution: --- → INCOMPLETE
You need to log in before you can comment on or make changes to this bug.