Closed
Bug 661746
Opened 13 years ago
Closed 6 years ago
Make selector matching work on const Element/Document/etc
Categories
(Core :: CSS Parsing and Computation, defect)
Core
CSS Parsing and Computation
Tracking
()
RESOLVED
INVALID
People
(Reporter: bzbarsky, Assigned: dzbarsky)
References
Details
Attachments
(5 files, 17 obsolete files)
9.43 KB,
patch
|
Details | Diff | Splinter Review | |
34.58 KB,
patch
|
Details | Diff | Splinter Review | |
11.56 KB,
patch
|
Details | Diff | Splinter Review | |
4.62 KB,
patch
|
Details | Diff | Splinter Review | |
13.46 KB,
patch
|
Details | Diff | Splinter Review |
This might end up being a metabug depending on how much work there is here, but to parallelize selector matching we need to make sure we're not mutating things as we go. This definitely means doing something about the places where we add bits to elements in selector matching.... I'm just not sure yet what that "something" should be.
Assignee | ||
Updated•13 years ago
|
Assignee: nobody → dzbarsky
Assignee | ||
Comment 1•13 years ago
|
||
Attachment #541033 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 2•13 years ago
|
||
Comment on attachment 541033 [details] [diff] [review] Store slow selector flags and set them later Might be worth doing this in a separate bug blocking this one... but anyway. 1) No need to have the explicit PushUpdates() calls; just doing it in the destructor is good enough. Then you can make it private as well. 2) s/AddUpdateFlags/RecordFlagsToAdd/ perhaps? 3) s/PushUpdate/AddRecordedFlags/ perhaps? 4) s/UpdateStyleFlags/FlagsToAdd/. Is there a reason this can't be an inner class of TreeMatchcontext? 5) FlagsToAdd constructor should take const nsINode*, I would think. AddRecordedFlags should const_cast as needed. 6) You don't need the |flag| and |update| temporaries, right?
Assignee | ||
Comment 3•13 years ago
|
||
Attachment #541033 -
Attachment is obsolete: true
Attachment #541033 -
Flags: review?(bzbarsky)
Attachment #541376 -
Flags: review?(bzbarsky)
Assignee | ||
Comment 4•13 years ago
|
||
Attachment #541463 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 5•13 years ago
|
||
Comment on attachment 541376 [details] [diff] [review] Patch addressing comments s/mToUpdate/mFlagsToAdd And you don't need the explicit Clear() call. You also don't need the |public:| bit for a struct. r=me with those nits.
Attachment #541376 -
Flags: review?(bzbarsky) → review+
Reporter | ||
Comment 6•13 years ago
|
||
Comment on attachment 541463 [details] [diff] [review] Part 2: Make selector matching const-correct >+ const nsPseudoClassList* pseudoClass, Why that change? It's probably fine, but if the idea is to make the selectors const too (which is a good idea), I suggest a separate patch for that. IndexOf() is sadly not const-safe: it uses a shared mutable cache. The fact that it claims to be a const method is a lie. :( Why are we calling IndexOf() in this code anyway? Why can't you use const in the NthIndexCache? For our purposes here const_cast is really bad, since it can let bugs through. Did you go through and look for const_cast and mutable in node implementations? We want to eliminate both or make sure we don't hit it...
Attachment #541463 -
Flags: review?(bzbarsky) → review-
Assignee | ||
Comment 7•13 years ago
|
||
I checked node implementations for const_cast and mutable, and the only use I found was http://mxr.mozilla.org/mozilla-central/source/content/base/src/nsGenericElement.cpp#1250, but I don't think we end up hitting that from selector matching.
Attachment #541463 -
Attachment is obsolete: true
Attachment #542145 -
Flags: review?(bzbarsky)
Assignee | ||
Comment 8•13 years ago
|
||
Attachment #542146 -
Flags: review?(bzbarsky)
Comment 9•13 years ago
|
||
Comment on attachment 542145 [details] [diff] [review] Part 2: Make selector matching work with const Element, etc. >--- a/layout/style/nsCSSRuleProcessor.cpp >+++ b/layout/style/nsCSSRuleProcessor.cpp >+static PRBool SelectorMatchesTree(const Element* aPrevElement, >+ const nsIContent* prevSibling = nsnull; >+ const nsIContent* curr = parent->GetFirstChild(); >+ while (curr && curr != prevElement) { >+ if (curr->IsElement()) { >+ prevSibling = curr; > } >+ curr = curr->GetNextSibling(); >+ } >+ >+ if (prevSibling) { >+ element = prevSibling->AsElement(); > } Seems like this can be written as const nsIContent* cur = prevElement->GetPreviousSibling(); while (cur && !cur->IsElement()) { cur = cur->GetPreviousSibling(); } if (cur) { element = cur->AsElement(); } or am I missing something here?
Updated•13 years ago
|
OS: Mac OS X → All
Hardware: x86 → All
Reporter | ||
Comment 10•13 years ago
|
||
> I checked node implementations for const_cast and mutable, and the only use I
> found was
Link has a mutable mCachedURI. Do your link changes take care of that? What about editor state? Not relevant?
nsHTMLOptionElement has a bunch of const_cast. So does nsHTMLInputElement, nsHTMLMediaElement, etc. Did you look over all of those?
Reporter | ||
Comment 11•13 years ago
|
||
Comment on attachment 542145 [details] [diff] [review] Part 2: Make selector matching work with const Element, etc. For the SelectorMatchesTree code, Ms2ger is right. You want to walk backwards from the current node, because usually you'll find another element pretty quickly. How about this: for (const nsIContent* curr = prevElement->GetPreviousSibling(); curr; curr = curr->GetPreviousSibling()) { if (curr->IsElement()) { element = curr->AsElement(); break; } } r=me with that.
Attachment #542145 -
Flags: review?(bzbarsky) → review+
Reporter | ||
Comment 12•13 years ago
|
||
Comment on attachment 542146 [details] [diff] [review] Part 3: Use const selectors >+ const PRBool docIsRTL = That part is silly; its just a local. r=me with that taken out.
Attachment #542146 -
Flags: review?(bzbarsky) → review+
Assignee | ||
Comment 13•13 years ago
|
||
Assignee | ||
Comment 14•13 years ago
|
||
Assignee | ||
Comment 15•13 years ago
|
||
Assignee | ||
Updated•13 years ago
|
Keywords: checkin-needed
Reporter | ||
Updated•13 years ago
|
Attachment #541376 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #542145 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #542146 -
Attachment is obsolete: true
Reporter | ||
Comment 16•13 years ago
|
||
I just realized something about the flags patch.... Say you have a <div> with N <p> children, and some selectors like "p + p" and "p:nth-child(even)" and "p:nth-child(odd)". How many times is the <div> added to the array? Seems like it would be N*(number of selectors), which seems unfortunate. Would a hashtable make more sense there?
Assignee | ||
Updated•13 years ago
|
Keywords: checkin-needed
Assignee | ||
Comment 17•13 years ago
|
||
Attachment #542340 -
Attachment is obsolete: true
Attachment #542543 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 18•13 years ago
|
||
David, have you done any performance testing with these patches? In an opt build with and without, what do numbers for the last column of http://www.webkit.org/perf/slickspeed/ look like, for example? You'll need to run it a few times, because of the noise.
Reporter | ||
Comment 19•13 years ago
|
||
Comment on attachment 542543 [details] [diff] [review] Part 1 using a hashtable This is identical to "Part 1 for checkin", as far as I can tell.
Assignee | ||
Comment 20•13 years ago
|
||
Timing results for http://www.webkit.org/perf/slickspeed/: Unpatched: 300, 351, 345, 316, 339, 325, 344, 319, 351, 346, 336, 325 Average: 333.1 With these patches and bug 660959: 288, 373, 405, 346, 359, 363, 362, 364, 364, 363, 324, 401 Average: 359.3 This is a 7.9% slowdown, which is coming from the hashing, since the rest of the changes should make it faster.
Attachment #542543 -
Attachment is obsolete: true
Attachment #542543 -
Flags: review?(bzbarsky)
Attachment #542700 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 21•13 years ago
|
||
> This is a 7.9% slowdown, which is coming from the hashing
Does that mean it goes away if you take out just the hashing patch?
Reporter | ||
Comment 22•13 years ago
|
||
And if so, we can probably do better on the hashtable (e.g. you end up with two hashtable ops on every add right now, where we could use just one, if we use nsBaseHashtable or the jshashtable). If you can confirm that the hashtable is the cause of the slowdown, can we try one of those solutions?
Assignee | ||
Comment 23•13 years ago
|
||
So some of the slowdown was coming from link stuff, but I've fixed that. The rest of it is hashing overhead. unpatched: 108, 107, 107, 106, 107, 107, 107, 107, 107, 106, 107, 107, 88, 106, 107, 107, 107, 107, 106, 107, 107, 107, 107, 88, 107, 107, 107, 107, 106, 107, 107, 107, 107, 107, 107, 89, 107, 107, 107, 107, 106, 107, 107, 107, 107, 106, 89, 107, 106, 107, 108, 107, 107, 107, 107, 107, 107, 106, 89, 107 Average: 105.35 with original patch for bug 660959: 120, 110, 110, 110, 110, 109, 110, 110, 110, 110, 110, 110, 87, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 86, 110, 110, 110, 111, 110, 110, 109, 110, 110, 110, 110, 110, 110, 85, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 111, 110, 110, 85, 110, 110, 110, 110, 111 Average: 108.56666666666666 with new patch for bug 660959: 109, 108, 107, 107, 106, 108, 107, 85, 107, 107, 107, 107, 107, 107, 106, 108, 107, 107, 107, 89, 107, 107, 107, 107, 107, 107, 106, 107, 107, 107, 108, 88, 107, 107, 108, 107, 107, 107, 107, 107, 108, 106, 107, 88, 107, 107, 107, 108, 107, 106, 107, 107, 107, 107, 107, 89, 107, 107, 106, 107 Average: 105.45 The following numbers are all with bug 660959 patch with datahashtable: 114, 113, 112, 113, 113, 113, 113, 113, 112, 95, 112, 114, 113, 112, 114, 112, 113, 113, 112, 113, 113, 113, 112, 96, 113, 113, 113, 113, 113, 113, 113, 113, 96, 113, 113, 113, 113, 113, 113, 113, 112, 97, 113, 113, 113, 113, 112, 113, 113, 112, 113, 95, 112, 113, 112, 113, 113, 112, 112, 113 Average: 111.38333333333334 with datahashtable that avoid redundant puts: 112, 112, 111, 111, 112, 112, 94, 112, 111, 112, 111, 112, 112, 111, 112, 111, 111, 112, 111, 112, 111, 95, 111, 112, 111, 112, 112, 111, 112, 112, 111, 112, 111, 112, 112, 95, 113, 112, 111, 113, 111, 112, 112, 111, 112, 112, 111, 111, 96, 112, 111, 112, 111, 112, 112, 111, 112, 112, 112, 111 Average: 110.51666666666667 with nsTHashtable: 111, 111, 111, 111, 111, 111, 111, 111, 110, 111, 110, 111, 86, 111, 111, 111, 111, 111, 111, 111, 112, 110, 95, 112, 110, 111, 111, 111, 111, 112, 111, 95, 111, 111, 111, 111, 111, 111, 111, 111, 111, 95, 112, 111, 111, 111, 111, 111, 111, 112, 111, 93, 111, 112, 112, 110, 111, 112, 111, 111 Average: 109.53333333333333 with Part 2: 112, 111, 111, 112, 112, 111, 110, 112, 110, 111, 111, 111, 110, 112, 95, 111, 111, 110, 112, 111, 111, 110, 111, 111, 111, 94, 112, 111, 111, 111, 111, 112, 111, 111, 112, 112, 112, 112, 112, 113, 94, 111, 112, 112, 112, 112, 114, 112, 112, 112, 112, 113, 94, 111, 111, 112, 113, 112, 112, 112 Average: 110.36666666666666 with Part 3: 112, 112, 111, 111, 111, 112, 112, 112, 110, 112, 111, 110, 95, 111, 111, 112, 112, 112, 111, 111, 112, 112, 111, 111, 112, 111, 112, 95, 111, 111, 112, 111, 112, 110, 111, 112, 111, 93, 111, 111, 112, 112, 110, 112, 112, 112, 110, 112, 112, 111, 111, 111, 111, 111, 94, 111, 111, 112, 110, 112 Average: 110.2 This is now a 4.6% slowdown.
Assignee | ||
Comment 24•13 years ago
|
||
Attachment #542700 -
Attachment is obsolete: true
Attachment #542700 -
Flags: review?(bzbarsky)
Attachment #543005 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 25•13 years ago
|
||
Can you try jshashtable too, just so we have those numbers?
Assignee | ||
Comment 26•13 years ago
|
||
With jshashtable and parts 2 and 3 we have 112, 112, 111, 111, 112, 111, 112, 94, 112, 112, 111, 111, 112, 111, 112, 112, 111, 112, 111, 112, 111, 111, 111, 94, 111, 111, 111, 111, 111, 111, 111, 111, 111, 95, 111, 112, 111, 111, 112, 112, 111, 112, 111, 111, 112, 111, 112, 111, 111, 94, 112, 111, 111, 111, 112, 111, 112, 112, 111, 112 Average: 110.25 I guess we should just use the nsTHashtable?
Reporter | ||
Comment 27•13 years ago
|
||
> I guess we should just use the nsTHashtable?
Looks like it, yes.
Reporter | ||
Comment 28•13 years ago
|
||
Comment on attachment 543005 [details] [diff] [review] Part 1 using nsTHashtable >+++ b/layout/style/nsRuleProcessorData.h >+ NodeFlagEntry(const nsINode* aNode) : nsPtrHashKey(aNode), mNode(aNode) {} >+ >+ const nsINode* mNode; You don't need the mNode member. On the other hand, you _do_ need to initialize mFlags to 0, I think. >+ RecordFlags(NodeFlagEntry* aEntry, void* aData) { >+ const_cast<nsINode*>(aEntry->mNode)->SetFlags(aEntry->mFlags); Here you'd use aEntry->GetKey() instead of aEntry->mNode. And maybe call this function AddFlagsToNode? >+ void RecordFlagsToAdd(const nsINode* aNode, PRUint32 aFlag) { aFlags, right? r=me with that. Thanks for doing the performance testing.
Attachment #543005 -
Flags: review?(bzbarsky) → review+
Assignee | ||
Comment 29•13 years ago
|
||
Attachment #543005 -
Attachment is obsolete: true
Assignee | ||
Comment 30•13 years ago
|
||
with Part 4: 111, 111, 110, 110, 110, 111, 110, 110, 110, 110, 109, 110, 87, 110, 109, 110, 110, 109, 110, 110, 109, 112, 109, 90, 110, 110, 109, 109, 109, 110, 109, 110, 109, 93, 110, 109, 110, 110, 110, 110, 111, 109, 110, 109, 110, 89, 110, 109, 110, 110, 109, 110, 109, 110, 110, 110, 111, 111, 111, 112 Average: 108.56666666666666
Attachment #543169 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 31•13 years ago
|
||
Comment on attachment 543169 [details] [diff] [review] Part 4: const nsIDocument >- nsIDocument* aDocument) >+ const nsIDocument* aDocument) This can stay non-const. The initialization will happen on the main thread, after all. That would remove the need for those const_cast too. Speaking of which, could you add an assert to TreeMatchContext ctor/dtor that they happen on the main thread? That should make it clear why the const_cast in the destructor is safe too.
Reporter | ||
Comment 32•13 years ago
|
||
Comment on attachment 543169 [details] [diff] [review] Part 4: const nsIDocument Oh, and r=me with those nits.
Attachment #543169 -
Flags: review?(bzbarsky) → review+
Assignee | ||
Comment 33•13 years ago
|
||
Attachment #543169 -
Attachment is obsolete: true
Assignee | ||
Comment 34•13 years ago
|
||
Previous patch didn't build on OSX.
Attachment #543168 -
Attachment is obsolete: true
Assignee | ||
Comment 35•13 years ago
|
||
Attachment #547518 -
Flags: review?(bzbarsky)
Reporter | ||
Comment 36•13 years ago
|
||
Comment on attachment 547518 [details] [diff] [review] PArt 5 - avoid creating atoms during selector matching >@@ -767,18 +772,20 @@ nsCSSSelector::AppendToStringWithoutComb >+ nsAutoString string; >+ list->u.mAtom->ToString(string); > nsStyleUtil::AppendEscapedCSSIdent( >+ nsDependentString(string), aString); You want to use nsDependentAtomString here. >+++ b/layout/style/StyleRule.h >+ nsIAtom* mAtom; Document that this is a strong ref, please? That said, can the string-type pseudoclasses ever have a null atom here? I guess it's not obvious as things stand, but worth a followup to figure that out and if so document it here and hoist the "is string" check in the dtor outside the mMemory null-check. Just don't do that in this bug, please. ;) >+++ b/layout/style/nsCSSRuleProcessor.cpp >+ nsAutoString langString; >+ pseudoClass->u.mAtom->ToString(langString); nsDependentAtomString. r=me with those nits.
Attachment #547518 -
Flags: review?(bzbarsky) → review+
Assignee | ||
Comment 37•13 years ago
|
||
Attachment #547518 -
Attachment is obsolete: true
Assignee | ||
Comment 38•13 years ago
|
||
Filed bug 673510 for followup
Reporter | ||
Comment 39•13 years ago
|
||
Reporter | ||
Comment 40•13 years ago
|
||
Reporter | ||
Updated•13 years ago
|
Attachment #543916 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #542341 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #542342 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #543219 -
Attachment is obsolete: true
Reporter | ||
Updated•13 years ago
|
Attachment #548088 -
Attachment is obsolete: true
Reporter | ||
Comment 41•13 years ago
|
||
Reporter | ||
Comment 42•13 years ago
|
||
Reporter | ||
Comment 43•13 years ago
|
||
Reporter | ||
Comment 44•13 years ago
|
||
https://hg.mozilla.org/integration/mozilla-inbound/rev/03970d1fc919 https://hg.mozilla.org/integration/mozilla-inbound/rev/1cb3705557d9 https://hg.mozilla.org/integration/mozilla-inbound/rev/61534874aed7 https://hg.mozilla.org/integration/mozilla-inbound/rev/2f403e4c42c8 https://hg.mozilla.org/integration/mozilla-inbound/rev/15cf68a3c027
Flags: in-testsuite-
Target Milestone: --- → mozilla11
Comment 45•13 years ago
|
||
Unfortunately PGO builds (and therefore obviously nightlies) on Windows are failing after this landed, with: { e:\builds\moz2_slave\m-in-w32-pgo\build\layout\style\nsruleprocessordata.h(172) : fatal error C1001: An internal error has occurred in the compiler. } https://tbpl.mozilla.org/php/getParsedLog.php?id=7383696&tree=Mozilla-Inbound#error0
Comment 46•13 years ago
|
||
Backed out of inbound, at bz's request: https://hg.mozilla.org/integration/mozilla-inbound/rev/add05f884131
Target Milestone: mozilla11 → ---
Reporter | ||
Comment 47•12 years ago
|
||
Nicholas, the patches here replace the mString in nsPseudoClassList with an mAtom. How should I adjust nsPseudoClassList::SizeOfIncludingThis? Just remove the part that measures the string, since now it's interned and can be shared and whatnot?
Reporter | ||
Comment 48•12 years ago
|
||
I tried pushing this to try with PGO on. The result is at https://tbpl.mozilla.org/?tree=Try&rev=cd2dfa804461 The bad news is that now even with VS 2010 the PGO build ends up with an ICE. :( Kyle said he'd try to get together a bug report to Microsoft, now that we're at least on a supported compiler version...
Comment 49•12 years ago
|
||
(In reply to Boris Zbarsky (:bz) from comment #47) > Nicholas, the patches here replace the mString in nsPseudoClassList with an > mAtom. How should I adjust nsPseudoClassList::SizeOfIncludingThis? Just > remove the part that measures the string, since now it's interned and can be > shared and whatnot? I think so? If it ends up in the atom table implemented by nsAtomTable.{h,cpp} it'll be measured by the "explicit/atom-table" memory reporter.
Reporter | ||
Comment 50•12 years ago
|
||
Tes, that's where it ends up. OK, good. Now if only this compiled.... ;)
Comment 51•12 years ago
|
||
Comment on attachment 574223 [details] [diff] [review] Part 2 updated to tip Landed the const AsElement() for mozilla16 because I needed it: https://hg.mozilla.org/mozilla-central/rev/b93768181dd0
Reporter | ||
Comment 52•6 years ago
|
||
Not relevant anymore, with stylo.
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → INVALID
You need to log in
before you can comment on or make changes to this bug.
Description
•