Closed Bug 83482 Opened 24 years ago Closed 24 years ago

investigate performance optimizations in RuleHash

Categories

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

Product:
Core
Component:
CSS Parsing and Computation
Type:
defect

Tracking

()

Status:
VERIFIED FIXED
Milestone:
mozilla0.9.2

People

(Reporter: dbaron, Assigned: dbaron)

References

Details

(Keywords: meta, perf)

Attachments

(7 files)

logging code
6.96 KB, patch
Details | Diff | Splinter Review
stats logged starting browser and exiting
10.99 KB, text/plain
Details
same thing, but loading about:blank instead of my homepage
8.73 KB, text/plain
Details
the logging plus fixes for bug 83506 and bug 83511
11.41 KB, patch
Details | Diff | Splinter Review
the logging plus fixes for bug 83484, bug 83497, bug 83506, and bug 83511
21.61 KB, patch
Details | Diff | Splinter Review
hack that shows performance gain from fixing bug 35847
4.00 KB, patch
Details | Diff | Splinter Review
attachment 36790 modified based on rbs's comments
22.15 KB, patch
Details | Diff | Splinter Review
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.
Status: NEW → ASSIGNED
Priority: -- → P1
Target Milestone: --- → mozilla0.9.2
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
Moved pseudos issue into bug 83506 -- see comments there.
Depends on: 83506
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.
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
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.
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
...and I ran Daniel's selectors tests, and the relevant parts of the CSS1 test suite and my own tests, with no regressions.
> * :-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.
>> * 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.
>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);
Err... now that I have confused myself, not very sure if it is "if (!matches && data->mComparator)" or "if (matches && data->mComparator)" ...
Really we should get rid of |matches| and just make it an assertion since the hash will take care of it.
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]; }
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.
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
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--- ?
Blocks: 83989
a= asa@mozilla.org for checkin to the trunk. (on behalf of drivers)
Above patch was checked in 2001-06-04 18:00 PDT.
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.
Status: ASSIGNED → RESOLVED
Closed: 24 years ago
Resolution: --- → FIXED
verified as per comments
Status: RESOLVED → VERIFIED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: