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

Status: RESOLVED FIXED

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

Description

[Boris Zbarsky [:bzbarsky]]

Attachment: 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.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Attachment: like so

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Merged to bug 667520

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Better comments, per Olli's request

Comment 4

[Olli Pettay [:smaug][[e-mail]]]

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.

Comment 5

[Boris Zbarsky [:bzbarsky]]

> Space before and after *

Done.

Pushed http://hg.mozilla.org/integration/mozilla-inbound/rev/dc94c4eb9e40

Comment 6

[Marco Bonardo [:mak]]

https://hg.mozilla.org/mozilla-central/rev/dc94c4eb9e40