310848 - Lots of nested lists effectively make pageload O(N^2)

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Boris Zbarsky [:bzbarsky]]

This happens with attachment 157457 [details], which is on bug 256311 (the "minimal
testcase, 168 kb <DL> between body tags, hanging" attachment).  That page has
lots of nested <DL> tags.

The problem is that we have the following rule in html.css:

339 /* nested lists have no top/bottom margins */
340 ul ul,   ul ol,   ul dir,   ul menu,   ul dl,
341 ol ul,   ol ol,   ol dir,   ol menu,   ol dl,
342 dir ul,  dir ol,  dir dir,  dir menu,  dir dl,
343 menu ul, menu ol, menu dir, menu menu, menu dl,
344 dl ul,   dl ol,   dl dir,   dl menu,   dl dl {
345   margin-top: 0;
346   margin-bottom: 0;
347 }

So for each dl we walk every single ancestor (eg to see whether it matches |ul
dl|), constructing RuleProcessorData structs as we go.  Which makes the whole
thing O(N^2) in number of lists (in particular, the number of times
RuleProcessorData() is called is O(N^2)).

Granted, this is a pathological case, and perhaps lazy population of
RuleProcessorData (which I can't find the bug for) would help enough here.

Comment 1

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

I've always thought that margin rule could use something like li > ul, etc.

The list-style-type rules, though, require implementing -moz-cycle or something
like it: http://lists.w3.org/Archives/Public/www-style/1999May/0067

Comment 2

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

(And see also http://lists.w3.org/Archives/Public/www-style/1999Jun/0026 .)

Comment 3

[Boris Zbarsky [:bzbarsky]]

I just checked opera's impl, and it has zero margins for a list in a div in an
<li>...  So we might not be able to change this for compat reasons.  :(

Comment 4

[Cameron McCormack (:heycam)]

Bug 705877 should have fixed this.