Last Comment Bug 631529 - Need a better strategy for handling :nth-* index caching
: Need a better strategy for handling :nth-* index caching
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: CSS Parsing and Computation (show other bugs)
: Trunk
: All All
: P1 normal (vote)
: mozilla7
Assigned To: Boris Zbarsky [:bz]
:
Mentors:
Depends on: 598832
Blocks: 630480
  Show dependency treegraph
 
Reported: 2011-02-04 07:18 PST by Boris Zbarsky [:bz]
Modified: 2011-05-30 06:05 PDT (History)
13 users (show)
bzbarsky: in‑testsuite?
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Testcase to exercise the patch I'm about to attach (658 bytes, text/html)
2011-05-03 19:09 PDT, Boris Zbarsky [:bz]
no flags Details
Proposed fix (11.70 KB, patch)
2011-05-03 19:20 PDT, Boris Zbarsky [:bz]
dbaron: review+
Details | Diff | Splinter Review

Description Boris Zbarsky [:bz] 2011-02-04 07:18:11 PST
See the testcase in bug 630480, where we end up walking the whole DOM over and over.  

Right now we cache for a single node, for the duration of style resolution, which helps some if there are multiple :nth-* rules.  But we still end up doing lots of work.

A simple solution, implemented in Webkit, is to store an index just for :nth-child in each node (17 bits in their case; it shares space with some flags) and have the others be slow.  The problem with this approach is that we reresolve style on the frame tree, and frame tree order doesn't necessarily match DOM order, esp. with XBL.  So we can't rely on our previous sibling already having its style reresolved and hence having a correct cached index.  I suppose we could deal with this by not using the cache if the parent has a binding....

Another approach, given lazy frame construction, is to only cache things for the duration of the style resolution or reresolution pass (so until we exit the frame constructor or exit the toplevel style reresolution entrypoint, or querySelector* or matchesSelector call).  So basically a hashtable hanging off the document or something like that.

Another option is to have such a hashtable hanging off the document and clear it on mutation.  The drawback to this is that we might have a bunch of data hanging around if we insert a big DOM and selectors like this are present and then do no mutations.  We could get rid of it on a timer, of course.

Thoughts?
Comment 1 Boris Zbarsky [:bz] 2011-02-04 07:20:17 PST
Oh, and a single shared hashtable is not so great for bug 631527.  So another question is how to handle that.... perhaps a hashtable on the document for the DOM APIs and maybe style reresolution and per-thread hashtables for initial frame construction or something?
Comment 2 Boris Zbarsky [:bz] 2011-02-05 18:42:40 PST
So one possibility would be to just hang the data off a TreeMatchContext (which is usable across multiple style resolution calls with my patches in bug 598832) and then push the TreeMatchContext creation up further into the frame constructor and such.
Comment 3 Boris Zbarsky [:bz] 2011-02-08 07:32:48 PST
In fact, I plan to do just that.  It certainly works pretty well on bug 630480, in my measurements.
Comment 4 Boris Zbarsky [:bz] 2011-03-17 21:35:27 PDT
And in fact, the patches in bug 598832 do that for frame construction (in particular, part 16).

Once those land, I'll look at pushing a TreeMatchContext up higher in style reresolution.
Comment 5 Boris Zbarsky [:bz] 2011-05-03 19:09:47 PDT
Created attachment 529912 [details]
Testcase to exercise the patch I'm about to attach

Without the patch, my browser takes about 1600ms to run this testcase.  With the patch, it takes 30ms.
Comment 6 Boris Zbarsky [:bz] 2011-05-03 19:12:14 PDT
Oh, WebKit trunk takes about 1000ms on that testcase.  Opera 11 takes about 2500ms.  If I use :nth-child instead of :nth-of-type, then Opera takes about 2200ms, while WebKit takes about 120ms.
Comment 7 Boris Zbarsky [:bz] 2011-05-03 19:20:14 PDT
Created attachment 529914 [details] [diff] [review]
Proposed fix

I wonder whether we should remove combine the various pass-through arguments here into a single struct or something.....
Comment 8 David Baron :dbaron: ⌚️UTC-7 (review requests must explain patch) 2011-05-21 22:21:16 PDT
Comment on attachment 529914 [details] [diff] [review]
Proposed fix

r=dbaron
Comment 9 Boris Zbarsky [:bz] 2011-05-24 22:37:17 PDT
http://hg.mozilla.org/projects/cedar/rev/f6fbc63f12a1
Comment 10 Mounir Lamouri (:mounir) 2011-05-25 01:07:03 PDT
Pushed:
http://hg.mozilla.org/mozilla-central/rev/f6fbc63f12a1

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