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)

defect

Tracking

()

RESOLVED INACTIVE
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

No activity for 17 years, closing

Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Summary: Frame construction time explodes for elements with many children → [meta] Frame construction time explodes for elements with many children
Resolution: FIXED → INACTIVE
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: