Closed
Bug 662489
Opened 13 years ago
Closed 13 years ago
Reorganize the nth-index cache to have a better chance of O(1) hits and less branching
Categories
(Core :: CSS Parsing and Computation, defect, P2)
Core
CSS Parsing and Computation
Tracking
()
RESOLVED
FIXED
mozilla10
People
(Reporter: bzbarsky, Assigned: bzbarsky)
References
Details
Attachments
(2 files, 2 obsolete files)
668 bytes,
text/html
|
Details | |
7.38 KB,
patch
|
smaug
:
review+
|
Details | Diff | Splinter Review |
The attached testcase shows the sort of problem that can arise with the current nth-index cache: when doing aIsFromEnd matching, we end up with O(N^2) behavior.
Assignee | ||
Comment 1•13 years ago
|
||
Assignee | ||
Updated•13 years ago
|
Priority: -- → P2
Whiteboard: [need review]
Assignee | ||
Updated•13 years ago
|
Attachment #537750 -
Flags: review?(dbaron)
Assignee | ||
Comment 2•13 years ago
|
||
Attachment #542225 -
Flags: review?(dbaron)
Assignee | ||
Updated•13 years ago
|
Attachment #537750 -
Attachment is obsolete: true
Attachment #537750 -
Flags: review?(dbaron)
Assignee | ||
Updated•13 years ago
|
Attachment #542225 -
Attachment description: Merged to → Merged to bug 667520
Assignee | ||
Comment 3•13 years ago
|
||
Attachment #569662 -
Flags: review?(Olli.Pettay)
Assignee | ||
Updated•13 years ago
|
Attachment #542225 -
Attachment is obsolete: true
Attachment #542225 -
Flags: review?(dbaron)
Comment 4•13 years ago
|
||
Comment on attachment 569662 [details] [diff] [review] Better comments, per Olli's request >+nsNthIndexCache::IndexDeterminedFromPreviousSibling(nsIContent* aSibling, >+ Element* aChild, >+ bool aIsOfType, >+ bool aIsFromEnd, >+ PRInt32& aResult) ... > Cache::Ptr siblingEntry = mCache.lookup(aSibling); > if (siblingEntry) { > PRInt32 siblingIndex = siblingEntry->value.mNthIndices[aIsOfType][aIsFromEnd]; > NS_ASSERTION(siblingIndex != 0, > "How can a non-anonymous node have an anonymous sibling?"); > if (siblingIndex > 0) { > // At this point, aResult is a count of how many elements matching >- // aChild we have seen after aSibling, including aChild itself. So if >- // |siblingIndex| is the index of aSibling, we need to add aResult to >- // get the right answer here. >- aResult = siblingIndex + aResult; >+ // aChild we have seen after aSibling, including aChild itself. >+ // |siblingIndex| is the index of aSibling. >+ // So if aIsFromEnd, we want |aResult = siblingIndex - aResult| and >+ // otherwise we want |aResult = siblingIndex + aResult|. >+ NS_ABORT_IF_FALSE(aIsFromEnd == 0 || aIsFromEnd == 1, >+ "Bogus bool value"); >+ aResult = siblingIndex + aResult * (1 - 2*aIsFromEnd); Space before and after * I somehow managed to guess wrong first the meaning of aIsFromEnd.
Attachment #569662 -
Flags: review?(Olli.Pettay) → review+
Assignee | ||
Comment 5•13 years ago
|
||
> Space before and after * Done. Pushed http://hg.mozilla.org/integration/mozilla-inbound/rev/dc94c4eb9e40
Flags: in-testsuite-
OS: Mac OS X → All
Hardware: x86 → All
Whiteboard: [need review]
Target Milestone: --- → mozilla10
Comment 6•13 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/dc94c4eb9e40
Status: NEW → RESOLVED
Closed: 13 years ago
Resolution: --- → FIXED
You need to log in
before you can comment on or make changes to this bug.
Description
•