Bug 20180 – Matching :nth-child selectors is slow

• Status: RESOLVED
• Resolution: FIXED
• Component: DOM

[David Smith]

Firefox numbers (nightly build downloaded July 26th): 
div:nth-child(even)	25 ms | 106 found
div:nth-child(2n)	        26 ms | 106 found
div:nth-child(odd)	26 ms | 137 found
div:nth-child(2n+1)	26 ms | 137 found
div:nth-child(n)	        27 ms | 243 found

WebKit numbers (r35363 + patch to fix id optimization)
div:nth-child(even)	37 ms | 106 found
div:nth-child(2n)	        66 ms | 106 found
div:nth-child(odd)	38 ms | 137 found
div:nth-child(2n+1)	61 ms | 137 found
div:nth-child(n)	        54 ms | 243 found

[David Smith]

Created attachment 23244 [details]
Exploratory patch

This patch caches the results of parsing the an+b expression in CSSSelector. The upside is obvious, the downside is that it adds two ints and a 1 bit flag (which should fit in the leftover bit from the enums) to CSSSelector. Please ignore lack of changelog, tabs, etc... this is just a "hey it's 1 AM and this sounds interesting" patch.

Suggestions on ways to avoid increasing the size of CSSSelector are welcome, although the comments indicate that it may be tricky/impossible :/

New numbers (same machine, but now based on r36246)

div:nth-child(even)	36 ms | 106 found
div:nth-child(2n)	36 ms | 106 found
div:nth-child(odd)	37 ms | 137 found
div:nth-child(2n+1)	36 ms | 137 found
div:nth-child(n)	39 ms | 243 found

[David Smith]

Created attachment 23333 [details]
Another unsatisfactory but working patch

This is about a 10% speedup for :nth-child on slickspeed. Unfortunately, it's basically just manually inlining part of Node::renderStyle(). The correct solution is to make renderStyle() non-virtual and have it call a virtual function only in the uncommon case, but for reasons unknown that doesn't speed things up. Attempts to inline it (which presumably would speed things up as this does) have run into circular include issues.

[David Smith]

Created attachment 23336 [details]
Better patch

Thanks to some suggestions from Maciej, this avoids having to do the silly manual inlining thing.

[David Smith]

Oops, forgot to add this: http://dscoder.com/renderstylebenchmark.html is a tiny qsa benchmark that I've been using to check this.

[David Smith]

Created attachment 23337 [details]
Addresses a few pseudoreview comments

Ordered includes, and made a blind but hopefully correct attempt to update the windows project file

[David Smith]

Created attachment 23341 [details]
Cache an+b parsing

This avoids the size hit on CSSSelector by making an :nth-* specific subclass that handles the caching.

[Darin Adler]

Comment on attachment 23337 [details]
Addresses a few pseudoreview comments

This is a great fix!

+    virtual RenderStyle* privateRenderStyle() const;

In other places I've called this sort of function virtualXXX, such as virtualFirstChild. But also, this function isn't really just a private renderStyle() function. It's specifically renderStyle() when m_renderer is 0. I'd suggest a name more like nonRendererRenderStyle().

I'm a little sad that we have to add a whole header just for a single function. Is there a better name for that header that could allow us to use it for more things in the future? It's not scalable to have a separate header for each function.

+    virtual RenderStyle* privateRenderStyle() const { return m_style; }
     String m_value;

I'd like to see a blank line here between the functions and data members.

It's not so great to have these virtual functions defined in the class definition. There's no reason to inline them.

It's a little strange to have this 10% speedup be a patch on a bug saying "Firefox is faster". I'd prefer to not have bugs where the titles are are literally about competitive comparisons, although I think it's great to compare us with other engines to figure out what we should work on. Does this actually make WebKit faster than some version of Gecko? Could we retitle the bug or something.

r=me, but please consider my suggestions

[David Smith]

Bug title changed; I wasn't thinking in terms of it going on a changelog when I filed it ;)

privateRenderStyle() is definitely a lame name for it. mitzpettel and I have been tossing ideas back and forth on #webkit but hadn't come up with anything we liked. nonRendererRenderStyle() is... sorta awful, but at least it describes what it does.

The separate header is there to avoid a circular dependency problem. I'm really not sure how to improve that :/

I'll make the other changes before I commit. Sadly even the combination of these patches doesn't make us faster than Gecko :/ they're still 25-27ms to WebKit's 34-35.

[David Smith]

Committed the renderStyle() inlining patch with the suggested changes in r36339

[David Smith]

Created attachment 23417 [details]
Minor improvements

This gets rid of the copy-pasted headers from CSSSelector since this is a new file, and moves m_parsedNth to CSSSelector since it has a free bit.

[David Smith]

Created attachment 23432 [details]
Enable an existing optimization that wasn't being triggered

Slightly more than a 2x speedup (testing with the other patches applied).

[David Smith]

Comment on attachment 23432 [details]
Enable an existing optimization that wasn't being triggered

A better version of this was committed in http://trac.webkit.org/changeset/36432

[Sam Weinig]

Comment on attachment 23417 [details]
Minor improvements

r=me.  You need to make sure to update all the build systems before landing.  Nice work!

[David Smith]

Committed that change in http://trac.webkit.org/changeset/36485. That brings us to 15-17ms on all the relevant tests on my machine, significantly faster than Firefox :)