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)

defect

Tracking

()

RESOLVED FIXED
mozilla10

People

(Reporter: bzbarsky, Assigned: bzbarsky)

References

Details

Attachments

(2 files, 2 obsolete files)

Attached file Testcase
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.
Attached patch like so (obsolete) — Splinter Review
Priority: -- → P2
Whiteboard: [need review]
Attachment #537750 - Flags: review?(dbaron)
Attached patch Merged to bug 667520 (obsolete) — Splinter Review
Attachment #542225 - Flags: review?(dbaron)
Attachment #537750 - Attachment is obsolete: true
Attachment #537750 - Flags: review?(dbaron)
Attachment #542225 - Attachment description: Merged to → Merged to bug 667520
Blocks: 696233
Attachment #569662 - Flags: review?(Olli.Pettay)
Attachment #542225 - Attachment is obsolete: true
Attachment #542225 - Flags: review?(dbaron)
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+
> 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
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.