97229 - [meta] Frame construction time explodes for elements with many children

Status: RESOLVED INACTIVE

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

Description

[Andreas M. "Clarence" Schneider]

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.

Comment 1

[Randell Jesup [:jesup] (needinfo me)]

Can you upload your testcases?  I'll jprof them (though I suspect I know where
the cycles are going).

Comment 2

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

That looks more like quadratic growth than exponential, right?

Comment 3

[Randell Jesup [:jesup] (needinfo me)]

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.

Comment 4

[Andreas M. "Clarence" Schneider]

Attachment: Perl script to generate testcases

Comment 5

[Andreas M. "Clarence" Schneider]

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

Comment 6

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

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...

Comment 7

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

Oh, wait, A10 is the same as A8.  I better modify the script...

Comment 8

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

A profile of the testcase generated with -c10 -s10 raises that 18.2% to 65.6%.

Comment 9

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

The bug on GetPrimaryFrameFor is bug 77114.

Comment 10

[Randell Jesup [:jesup] (needinfo me)]

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

[karnaze (gone)]

dbaron, if you don't want this, please reassign to waterson or attinasi.

Comment 12

[Randell Jesup [:jesup] (needinfo me)]

Adding dependancy for the reflow portion of this

Comment 13

[David Baron :dbaron: (⌚️UTC-4, no longer working on Mozilla)]

This has become a meta-bug.

Comment 14

[basic]

remove self

Comment 15

[basic]

still an issue?

Comment 16

[[e-mail]]

Attachment: Test case

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.

Comment 17

[Markus Hübner]

dbaron, is that covered by your arch rewrite plans?

Comment 18

[[e-mail]]

Attachment: Test case

Comment 19

[[e-mail]]

Attachment: Test case

Comment 20

[Sylvestre Ledru [:Sylvestre]]

No activity for 17 years, closing