Closed
Bug 97229
Opened 23 years ago
Closed 5 years ago
[meta] Frame construction time explodes for elements with many children
Categories
(Core :: Layout: Block and Inline, defect, P5)
Core
Layout: Block and Inline
Tracking
()
RESOLVED
INACTIVE
Future
People
(Reporter: c, Assigned: dbaron)
References
Details
(Keywords: meta, perf, testcase)
Attachments
(2 files, 2 obsolete files)
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.
Reporter | ||
Updated•23 years ago
|
Comment 1•23 years ago
|
||
Can you upload your testcases? I'll jprof them (though I suspect I know where
the cycles are going).
Assignee | ||
Comment 2•23 years ago
|
||
That looks more like quadratic growth than exponential, right?
Comment 3•23 years ago
|
||
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.
Reporter | ||
Comment 4•23 years ago
|
||
Reporter | ||
Comment 5•23 years ago
|
||
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
Assignee | ||
Comment 6•23 years ago
|
||
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...
Assignee | ||
Comment 7•23 years ago
|
||
Oh, wait, A10 is the same as A8. I better modify the script...
Assignee | ||
Comment 8•23 years ago
|
||
A profile of the testcase generated with -c10 -s10 raises that 18.2% to 65.6%.
Comment 10•23 years ago
|
||
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.
Comment 11•23 years ago
|
||
dbaron, if you don't want this, please reassign to waterson or attinasi.
Assignee: karnaze → dbaron
Assignee | ||
Comment 13•23 years ago
|
||
This has become a meta-bug.
Comment 14•23 years ago
|
||
remove self
Comment 15•23 years ago
|
||
still an issue?
Comment 16•23 years ago
|
||
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.
Assignee | ||
Updated•22 years ago
|
Component: Layout → Layout: Block & Inline
Comment 17•22 years ago
|
||
dbaron, is that covered by your arch rewrite plans?
Comment 18•22 years ago
|
||
Attachment #91501 -
Attachment is obsolete: true
Comment 19•22 years ago
|
||
Attachment #127180 -
Attachment is obsolete: true
Updated•22 years ago
|
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
Updated•15 years ago
|
QA Contact: chrispetersen → layout.block-and-inline
Comment 20•5 years ago
|
||
No activity for 17 years, closing
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Updated•5 years ago
|
Summary: Frame construction time explodes for elements with many children → [meta] Frame construction time explodes for elements with many children
Assignee | ||
Updated•5 years ago
|
Resolution: FIXED → INACTIVE
You need to log in
before you can comment on or make changes to this bug.
Description
•