Reorganize the nth-index cache to have a better chance of O(1) hits and less branching

RESOLVED FIXED in mozilla10

Status

()

Core
CSS Parsing and Computation
P2
normal
RESOLVED FIXED
6 years ago
6 years ago

People

(Reporter: bz, Assigned: bz)

Tracking

Trunk
mozilla10
Points:
---
Bug Flags:
in-testsuite -

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(2 attachments, 2 obsolete attachments)

Created attachment 537747 [details]
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.
Created attachment 537750 [details] [diff] [review]
like so
Priority: -- → P2
Whiteboard: [need review]
Attachment #537750 - Flags: review?(dbaron)
Created attachment 542225 [details] [diff] [review]
Merged to bug 667520
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
Created attachment 569662 [details] [diff] [review]
Better comments, per Olli's request
Attachment #569662 - Flags: review?(Olli.Pettay)
Attachment #542225 - Attachment is obsolete: true
Attachment #542225 - Flags: review?(dbaron)

Comment 4

6 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+
> 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
Last Resolved: 6 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.