Last Comment Bug 662489 - Reorganize the nth-index cache to have a better chance of O(1) hits and less branching
: Reorganize the nth-index cache to have a better chance of O(1) hits and less ...
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: CSS Parsing and Computation (show other bugs)
: Trunk
: All All
: P2 normal (vote)
: mozilla10
Assigned To: Boris Zbarsky [:bz] (TPAC)
:
Mentors:
Depends on:
Blocks: 696233
  Show dependency treegraph
 
Reported: 2011-06-07 01:19 PDT by Boris Zbarsky [:bz] (TPAC)
Modified: 2011-10-27 01:45 PDT (History)
2 users (show)
bzbarsky: in‑testsuite-
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Testcase (668 bytes, text/html)
2011-06-07 01:19 PDT, Boris Zbarsky [:bz] (TPAC)
no flags Details
like so (6.52 KB, patch)
2011-06-07 01:27 PDT, Boris Zbarsky [:bz] (TPAC)
no flags Details | Diff | Splinter Review
Merged to bug 667520 (6.94 KB, patch)
2011-06-27 12:10 PDT, Boris Zbarsky [:bz] (TPAC)
no flags Details | Diff | Splinter Review
Better comments, per Olli's request (7.38 KB, patch)
2011-10-26 06:59 PDT, Boris Zbarsky [:bz] (TPAC)
bugs: review+
Details | Diff | Splinter Review

Description Boris Zbarsky [:bz] (TPAC) 2011-06-07 01:19:59 PDT
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.
Comment 1 Boris Zbarsky [:bz] (TPAC) 2011-06-07 01:27:37 PDT
Created attachment 537750 [details] [diff] [review]
like so
Comment 2 Boris Zbarsky [:bz] (TPAC) 2011-06-27 12:10:34 PDT
Created attachment 542225 [details] [diff] [review]
Merged to bug 667520
Comment 3 Boris Zbarsky [:bz] (TPAC) 2011-10-26 06:59:25 PDT
Created attachment 569662 [details] [diff] [review]
Better comments, per Olli's request
Comment 4 Olli Pettay [:smaug] (TPAC) 2011-10-26 10:30:23 PDT
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 [:bz] (TPAC) 2011-10-26 12:35:48 PDT
> Space before and after *

Done.

Pushed http://hg.mozilla.org/integration/mozilla-inbound/rev/dc94c4eb9e40
Comment 6 Marco Bonardo [::mak] 2011-10-27 01:45:06 PDT
https://hg.mozilla.org/mozilla-central/rev/dc94c4eb9e40

Note You need to log in before you can comment on or make changes to this bug.