77066 - CSS cascade uses O(N^2) array insertion

Status: VERIFIED FIXED

(Core :: CSS Parsing and Computation, defect, P1)

Description

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

The CSS cascade uses O(N^2) array insertion.  At least I sure think it does. 
Have a look at InsertRuleByWeight in nsCSSStyleSheet.cpp.  InsertRuleByWeight
shows up as 30/960 hits on a profile of opening new windows.

I'm assigning this to myself, but if someone else wants to fix it, feel free to
take it, since I probably won't get around to it for a while.

Comment 1

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

Actually, I changed my mind.  Working on this right now...

Comment 2

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

Attachment: fixes O(N^2) insertion

Comment 3

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

Oops, that leaks.  New patch coming soon...

Comment 4

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

Attachment: non-leaky fix

Comment 5

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

In my tree I just changed
  nsCOMPtr<nsISupportsArray> mRuleArray;
to
  nsISupportsArray* mRuleArray;
since it doesn't need to be a strong reference (which adds performance cost)
since the hashtable already owns it.

Comment 6

[Brendan Eich [:brendan]]

Oh no, yet another nsHashKey subclass for me to whack in fixing bug 72722!  Hey
dbaron, any chance I could persuade you to use pldhash.h directly?  S'ok either
way (I'll fix up the patch in 72722 and land it for 0.9.1), just thought I'd
ask.

/be

Comment 7

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

It would be nice to have an nsIntKey :-).  (I tried using nsVoidKey, but I
couldn't get the compiler to accept the cast.  I now realize a two-step cast
might have worked, but it's annoying...)

Comment 8

[Brendan Eich [:brendan]]

I'll do an nsInt32Key in bug 72722 and switch this code to use it, if it's in by
the time I fix 72722.

/be

Comment 9

[Marc Attinasi]

[s]r=attinasi

Comment 10

[Marc Attinasi]

BTW: here is some informationj David sent me via email. Others may find this
useful too.

>  > I started looking over your patch. Can you give me a brief overview of what
> is going on? I think I understand it but...

 The old cascade algorithm got the weight of each rule (e.g., the 1-2-3
for p#foo[title="b"][lang|="en"]), found the first rule of that weight
in a huge array sorted from highest weight to lowest (FindEndOfWeight
should have been called FindStartOfWeight), and inserted the rule.

The new approach creates a hashtable of arrays, one for each weight,
and for each rule appends the rule to the appropriate array (creating
the array if it doesn't already exist).  It then appends these arrays
into one big array (which requires reversing them) that is equivalent
to the old one that was generated.


> Also, What is the actual savings? Does this significantly change the amount
> of time we spend opening a window?

 I think it saves about 2% of the time we spent opening a new window (I
think it was 19 / 960 hits).  (Opening a new window is an extreme case,
since we cascade all the rules in all the stylesheets that apply to the
main browser window!)

-David

Comment 11

[Chris Waterson]

sr=waterson, although it makes me silently scream that nsISupportsArray is the
de facto collection interface for the style system.

Comment 12

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

Fix checked in 2001-04-27 19:16 PDT.

Comment 13

[Pierre Saslawsky]

*** Bug 74906 has been marked as a duplicate of this bug. ***

Comment 14

[Madhur Bhatia]

verified as per developers comments