Open Bug 97229 Opened 19 years ago Updated 2 years ago

Frame construction time explodes for elements with many children

Categories

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

defect

Tracking

()

ASSIGNED
Future

People

(Reporter: c, Assigned: dbaron)

References

Details

(Keywords: meta, perf, testcase)

Attachments

(2 files, 2 obsolete files)

575 bytes, text/plain
Details
1011 bytes, application/vnd.mozilla.xul+xml
Details
If an element contains thousands of childs, frame construction time seems to
grow exponentially. I've done some timings for the case with many <span>s
inside a <pre>. View-source with syntax highlighting uses such code and that
makes it very slow for large pages. I've examined the effects of dividing the
<pre> in multiple parts too.

Timings for a page consisting of 2^7 lines, each with 2^8 chars,
inside a <pre> element:

Base timing 0: Plain chars without additional markup
Series Ax: Each of first 2^x chars per line enclosed in <span></span>
Series Bx: Every single char enclosed in <span></span> (same as A8),
           but divided into 2^x <pre>...</pre>

   Content Reflow Style  Frame  Parse  Other   Total

0   0.001  0.056  0.017  0.089  0.016  0.088   0.267

A0  0.027  0.058  0.037  0.110  0.039  0.097   0.368
A1  0.038  0.054  0.053  0.127  0.043  0.113   0.428
A2  0.070  0.126  0.087  0.160  0.071  0.116   0.630
A3  0.132  0.115  0.144  0.218  0.134  0.149   0.892
A4  0.244  0.229  0.302  0.316  0.242  0.358   1.691
A5  0.525  0.792  0.565  0.670  0.460  0.758   3.770
A6  1.008  1.722  1.075  1.573  1.002  1.630   8.010
A7  2.098  3.602  2.122  4.178  1.946  2.510  16.456
A8  4.098  8.037  4.200 13.118  4.080  3.968  37.502

B0  4.098  8.037  4.200 13.118  4.080  3.968  37.502
B1  3.973  7.827  4.270  8.087  4.397  3.727  32.280
B2  4.197  7.290  4.250  5.703  4.130  3.640  29.210
B3  4.050  7.188  4.272  4.544  3.926  3.814  27.794
B4  4.275  6.918  4.303  3.813  3.822  3.680  26.810
B5  4.118  6.503  4.223  3.357  3.880  3.533  25.615
B6  4.170  6.480  4.356  3.094  3.758  3.438  25.296
B7  4.158  6.848  4.313  3.127  3.980  3.355  25.782

Times from MOZ_TIMERs (CP time in seconds, medium value of 3..10 passes):

Content = "Content creation time" (HTML content sink)
Reflow = "Reflow time"
Style = "Style resolution time"
Frame = "Frame construction plus style resolution time" - <Style>
Parse = "Parse Time" (Parser incl. tokenizer and DTD)
Other = <Total> - <Content> - <Reflow> - <Style> - <Frame> - <Parse>
Total = my own timer, started in parser constructor,
        stopped in parser destructor

Measured on Linux, 700 MHz Duron, today's CVS build, no debug,
no non-default optimization, with patch for bug 57724 in my tree.
Blocks: 84707
Keywords: perf
Can you upload your testcases?  I'll jprof them (though I suspect I know where
the cycles are going).
That looks more like quadratic growth than exponential, right?
a3->a4->a5->6->7->8 go up by 1.45->2.12->2.35->2.65->3.14

It's not O(n*n), but it's more than O(n), and the rate of increase is
increasing, not decreasing.  O(NlogN) or maybe worse (for large N values it may
approach O(n*n)) it looks like, and probably it's our pals,
GetNextSibling/AppendFrame/etc.
I don't want to attach some MB of stupid testcases, please use my script
to generate them yourself.

Line 0 was generated without parameters,
A<x> with -s<x>, B<x> with -s8 -p<x>.

While I wanted to add data for 2^16 childs of <pre> I came across a even
worse testcase. If all childs are on the same line, reflow is the most
serious problem. A 900 kB testcase took over 2.5 hours to render on my
700 MHz Duron (memory (128 MB) was no problem). Timings of testcases
generated by my script with parameters -l0 -c16 -s<x> for line C<x>:

    Content  Reflow  Style  Frame  Parse  Other   Total

C0   0.010    0.100  0.010  0.070  0.020  0.120    0.330
C1   0.010    0.100  0.020  0.070  0.030  0.100    0.330
C2   0.010    0.100  0.020  0.060  0.030  0.110    0.330
C3   0.020    0.090  0.020  0.070  0.000  0.140    0.340
C4   0.010    0.100  0.030  0.050  0.030  0.130    0.350
C5   0.030    0.110  0.040  0.040  0.030  0.110    0.360
C6   0.020    0.110  0.020  0.070  0.020  0.150    0.390
C7   0.040    0.110  0.020  0.090  0.040  0.140    0.440
C8   0.020    0.200  0.010  0.140  0.050  0.160    0.580
C9   0.030    0.240  0.110  0.100  0.090  0.190    0.760
C10  0.130    0.480  0.130  0.190  0.120  0.240    1.290
C11  0.260    2.310  0.250  0.360  0.220  0.390    3.790
C12  0.540    4.540  0.580  0.570  0.440  0.720    7.390
C13  0.920   17.000  1.040  1.500  1.000  1.360   22.820
C14  1.980  103.680  2.190  4.020  1.900  2.470  116.240
C15  4.140  888.250  4.310 13.350  4.120  3.580  917.750
C16  8.250 9094.710  8.510 62.620  9.460 16.390 9199.940

In C14, 75.5% of the time was spent in nsJISx4501LineBreaker::Next

In A10, 18.2% of the time was spent in nsCheapVoidArray::IndexOf, called from
nsGenericHTMLContainerElement::IndexOf, called from
FrameManager::GetPrimaryFrameFor, which I'm pretty sure there's already a bug
on.  But I should try A12...
Oh, wait, A10 is the same as A8.  I better modify the script...
A profile of the testcase generated with -c10 -s10 raises that 18.2% to 65.6%.
The bug on GetPrimaryFrameFor is bug 77114.
Content, style, parse appear to be O(n).
Other is probably O(n), though the last datapoint points to O(n*n).
Frame appears to be O(n*n), again probably the stuff dbaron is working on.
Reflow appears to be worse than O(n*n) : a doubling produces 8-10x increase past
a certain point of complexity.

Bug 77114 definitely needs some attention; this has shown up before on large
pages, and the commentary in the source code implies that it's only needed for
history reasons - there's probably a better solution to those.
dbaron, if you don't want this, please reassign to waterson or attinasi.
Assignee: karnaze → dbaron
Adding dependancy for the reflow portion of this
Blocks: 114584
This has become a meta-bug.
Status: NEW → ASSIGNED
Keywords: meta
Priority: -- → P5
Target Milestone: --- → Future
remove self
still an issue?
Attached file Test case (obsolete) —
Once this has loaded just click in the window. The script will clone the
existing nodes to tile the content. This takes absolutely ages. I've tried
temporarily removing the vbox from the document and attaching it at the end, or
hiding the vbox and showing it at the end and all this does is move the delay.
In fact, once the nodes are constructed, use the DOM inspector to add and
remove the hidden attribute from the vbox and you'll observe a similar delay.
Once the nodes are created collapsing and uncollapsing the vbox is virtually
instant.
Keywords: testcase
Component: Layout → Layout: Block & Inline
dbaron, is that covered by your arch rewrite plans?
Attached file Test case (obsolete) —
Attachment #91501 - Attachment is obsolete: true
Attached file Test case
Attachment #127180 - Attachment is obsolete: true
OS: Linux → All
Hardware: PC → All
Summary: Frame construction time explodes for elements with many childs → Frame construction time explodes for elements with many children
Blocks: 203448
QA Contact: chrispetersen → layout.block-and-inline
You need to log in before you can comment on or make changes to this bug.