David Baron :dbaron: Assignee
	Description • 23 years ago

I think there are probably some significant performance benefits we could gain
by tweaking the RuleHash.  One thought I've had is incorporating namespace
information into the tag matching (which would probably be a bigger impromevent
after bug 35847 is fixed), although there are probably other improvements.  (I
still don't completely understand the pseudo stuff.)

I just wrote a little logging code so we can see how it's doing.  I'll attach
the code and the results when opening a new browser window.

	David Baron :dbaron: Assignee
	Comment 4 • 23 years ago

I dug into the pseudos a little, and I don't understand why we match the
universal rules against them.  (Ian -- is there a bug that we match universal
selectors against pseudo-elements when we shouldn't?  Or do these calls to
SelectorMatches never match?)  It seems like we shouldn't even need to be doing
this, although I might not fully understand the weird way we handle
pseudo-elements in the style system.  (I think all the pseudos here are
pseudo-elements, and never pseudo-classes.)

Anyway, the pseudos tested (in EnumerateTagRules) when I took the above log were:

     22	pseudo-tag: :scrolled-content
     12	pseudo-tag: :first-letter
     11	pseudo-tag: :before
     11	pseudo-tag: :after
      7	pseudo-tag: :-moz-outliner-row
      7	pseudo-tag: :first-line
      6	pseudo-tag: :canvas
      4	pseudo-tag: :viewport
      2	pseudo-tag: :viewport-scroll

	David Baron :dbaron: Assignee
	Comment 5 • 23 years ago

Moved pseudos issue into bug 83506 -- see comments there.

	David Baron :dbaron: Assignee
	Comment 9 • 23 years ago

With both of the above patches I saw the number of stacks within SelectorMatches
in opening new windows for 30 seconds drop from 90 stacks to 33 out of about
3000 total (i.e., drop from 3% to 1%).  We should really fix bug 35847.

	David Baron :dbaron: Assignee
	Comment 10 • 23 years ago

Here's the total time within StyleSetImpl::WalkRuleProcessors (2 runs each)
(times are relative to g_main_dispatch which excludes g_main_poll):

with neither patch:  289/2734, 381/2943
with only the first patch: 329/2932, 294/2928
with both patches: 226/2845, 284/2919

(In the first run I opened 25 windows, paused, and opened 5 more (which probably
missed the 30 second profile, and in the second run on each I just opened 30 new
windows.)

I think that's definitely a gain, although it's hard to tell how big it is.

Not all the gains are within SelectorMatches -- in particular bug 83506 and bug
83511 are not.  Just the SelectorMatches times in each of those profiles are:
63 110
85 76
44 46

	rbs
	Comment 11 • 23 years ago

Looks like you have been doing an interesting investigation here. Perhaps, you 
might get more comments/r/sr if you now propose a patch in which you leave your 
local logging stuff out, as it obscures the reading.

	David Baron :dbaron: Assignee
	Comment 12 • 23 years ago

I guess I am looking reviews for attachment 36790 [details] [diff] [review], since I'd like to try to get
it checked in before continuing so that I don't accumulate too many separate
changes at once.  That patch contains (in the order the changes start):

 * the fix for bug 83484, which halves the number of selectors needed for the
   :link and :visited rules in html.css by implementing :-moz-all-link, since
   those selectors are hashed as universal and thus expensive
 * the last of the patches in bug 65469, which I've had in my tree for ages and
   already has one review
 * the fix for bug 83511, which avoids the refcounting of atoms for the
   stack-based keys
 * the logging code that I added, which I expect others may find useful too
 * the fix for bug 83497, which adds a namespace hash.  This doesn't help that
   much now (if at all) but will help a lot once bug 35847 is fixed.
 * a minor change to avoid repeated reallocation of mEnumList by setting the
   initial length to a minimum of 8
 * the fix for bug 83506 - remove most of EnumerateTagRules since most of it
   does no useful work
 * a minor tweak to the beginning of SelectorMatches - removal of an unneeded
   variable and an unneeded test by moving one if statement inside another

	David Baron :dbaron: Assignee
	Comment 13 • 23 years ago

...and I ran Daniel's selectors tests, and the relevant parts of the CSS1 test
suite and my own tests, with no regressions.

	rbs
	Comment 14 • 23 years ago

> * :-moz-all-link
What about :-moz-any-link?  This will make reading the back-end code easier,
e.g., "if (nsCSSAtoms::anyLinkPseudo == aAtom)" is easier to understand than
"if (nsCSSAtoms::allLinkPseudo == aAtom)" ...

> * the last of the patches in bug 65469, which I've had in my tree for ages and
>   already has one review
No opinion here... apart from noting that bug 65469 could pursue its course...

> * the fix for bug 83511, which avoids the refcounting of atoms for the
>   stack-based keys
This one looks interesting.

> * the logging code that I added, which I expect others may find useful too
Not sure what the others think about this particular logging stuff though.
But after the recent round of cleanup, I am suspicious seeing these #ifdef
creeping back. It takes effort to understand the code, and the #ifdef makes
life even harder. Plus they have an associated maintenance cost. 

> * the fix for bug 83497, which adds a namespace hash.  This doesn't help that
>   much now (if at all) but will help a lot once bug 35847 is fixed.
I am looking forward for bug 35847 to be fixed. It is wasteful to consider
universal rules scoped under a namespace everywhere.

> * a minor change to avoid repeated reallocation of mEnumList by setting the
>   initial length to a minimum of 8
Nice litte gem.

> * the fix for bug 83506 - remove most of EnumerateTagRules since most of it
>   does no useful work
This one takes an effort to convince oneself that it is not regressing
anything... Your change amounts to saying that there are no cases where a
RuleEnumFunc will be designed to apply to universal pseudo-rules (not
sure if this is the right terminology, but you see what I mean). Is that
true that a RuleEnumFunc will never apply to '*:pseudo-something'?
If that's true, then your change is is a worthwhile optimization.

> * a minor tweak to the beginning of SelectorMatches - removal of an unneeded
>   variable and an unneeded test by moving one if statement inside another
I verified that the logic was the same.

	David Baron :dbaron: Assignee
	Comment 15 • 23 years ago

>> * the fix for bug 83506 - remove most of EnumerateTagRules since most of it
>> does no useful work
>This one takes an effort to convince oneself that it is not regressing
>anything... Your change amounts to saying that there are no cases where a

The easy way to convince yourself is to look at the first few lines of
PseudoEnumFunc -- they fail unless (selector->mTag == data->mPseudoTag), so the
tags must match.  (The only existing comparitor also fails in that case.)

And believe it or not, we were spending a lot of time in that little loop.


I think the debugging code is worth having in the tree -- I'd rather not have to
rewrite it every time I want to use it.  If you think it's necessary, I'm
willing to try to reduce the number of lines it takes up with some additional
|#ifdef|s.


I'm planning on working on landing bug 35847 once I get this in, although maybe
I should just make all the changes in my tree at once and land everything.


I'll make the change in my tree from :moz-all-link to :moz-any-link and
allLinkPseudo to anyLinkPseudo.  I agree that it sounds better.

	rbs
	Comment 16 • 23 years ago

>The easy way to convince yourself is to look at the first few lines of
>PseudoEnumFunc -- they fail unless (selector->mTag == data->mPseudoTag), so the
>tags must match.  (The only existing comparitor also fails in that case.)

Had a look at PseudoEnumFunc and saw the test that you are referring to.
Can this test (mTag vs. mPseudoTag) ever match?!

And while you are there, why not make the following
change (to avoid making an unnecessary trip to PseudoMatches()):

  PRBool matches = (selector->mTag == data->mPseudoTag);
- if (data->mComparator)
+ if (!matches && data->mComparator)
    data->mComparator->PseudoMatches(data->mPseudoTag, selector, &matches);

>And believe it or not, we were spending a lot of time in that little loop.

Yep, that's understandable. For a function like SelectorMatches() which 
is called over a million times, simple things can add up (ctor/dtor,
unnecessary function calls, etc). Also, when following one of the links
that you listed, I saw the mention of the loop somewhere re: perf radars. 

>I think the debugging code is worth having in the tree -- I'd rather not have 
to
>rewrite it every time I want to use it.  If you think it's necessary, I'm
>willing to try to reduce the number of lines it takes up with some additional
>|#ifdef|s.

I do not have any particular interest in this logging stuff. I would have
thought that they have served their purpose while conducting this investigation, 
or that you could keep them in one of your trees. I doubt I will be using it. 
Let's agree to disagree on this one.

>I'm planning on working on landing bug 35847 once I get this in

Yep, if this patch lands, that will be an incentive to get rid of
the other bug...

Some other things (actually only one nit) as I was reading your patch again: 
===================
-class nsWeightKey: public nsHashKey {
+class nsInt32Key: public nsHashKey {
 public:
-  nsWeightKey(PRInt32 aWeight);
-  nsWeightKey(const nsWeightKey& aKey);
-  virtual ~nsWeightKey(void);
+  nsInt32Key(PRInt32 aWeight);  <---- aInt32 ?

And this is _really_ a nit...
+  void EnumerateAllRules(nsIAtom* aTag, nsIAtom* aID,
+                         const nsVoidArray& aClassList, PRInt32 aNameSpace,
                          RuleEnumFunc aFunc, void* aData);
re-ordered to:
+  void EnumerateAllRules(PRInt32 aNameSpace, nsIAtom* aTag, nsIAtom* aID,
+                         const nsVoidArray& aClassList,
                          RuleEnumFunc aFunc, void* aData);

	rbs
	Comment 17 • 23 years ago

Err... now that I have confused myself, not very sure if it is "if (!matches && 
data->mComparator)" or "if (matches && data->mComparator)" ...

	David Baron :dbaron: Assignee
	Comment 18 • 23 years ago

Really we should get rid of |matches| and just make it an assertion since the
hash will take care of it.

	rbs
	Comment 19 • 23 years ago

double-checking:
   if (mEnumListSize < testCount) {
     delete [] mEnumList;
-    mEnumList = new RuleValue*[testCount];
-    mEnumListSize = testCount;
+    mEnumListSize = PR_MIN(testCount, MIN_ENUM_LIST_SIZE); <--- PR_MAX
+    mEnumList = new RuleValue*[mEnumListSize];
   }

	rbs
	Comment 21 • 23 years ago

No more issues from my end. Applied the patch and it is baking in my tree now...
Passing the ball to attinasi & waterson/hyatt for the honor of r= & sr= if they 
have no concerns and are happy too.

	Chris Waterson
	Comment 22 • 23 years ago

These changes look fine to me. I'm not sure what the impact of the namespace
changes might be; I think marc is pretty familiar with the issues there and can
sanity check. r=waterson

	Marc Attinasi
	Comment 23 • 23 years ago

The patch looks great to me. sr=attinasi

Are you seeing the same general performance improvements that you mentioned in
---Additional Comments From David Baron 2001-06-01 08:26--- ?

	Asa Dotzler [:asa]
	Comment 24 • 23 years ago

a= asa@mozilla.org for checkin to the trunk.
(on behalf of drivers)

	David Baron :dbaron: Assignee
	Comment 25 • 23 years ago

Above patch was checked in 2001-06-04 18:00 PDT.

	David Baron :dbaron: Assignee
	Comment 26 • 23 years ago

Marking as fixed -- the performance problems in all dependencies except bug
56117 are fixed, and we don't need a meta-bug to track one bug.

I filed a few bugs on improving SelectorMatchesData construction as well, but
I'm not sure if they'll help much since most of the time we spend (at least for
HTML) is time spent determining visited link state, which is already cached in
the content and therefore wouldn't be reduced by lazily constructing SMData and
constructing SMData at a higher level.

	Madhur Bhatia
	Comment 27 • 22 years ago

verified as per comments