Issue 18732004: Add fast path for querySelector(All)

Issue 18732004: Add fast path for querySelector(All) (Closed)

Created:
7 years, 5 months ago by tasak

Modified:
7 years, 4 months ago

Reviewers:
haraken, esprehn

CC:
blink-reviews, dglazkov+blink, eae+blinkwatch, adamk+blink_chromium.org

Base URL:
svn://svn.chromium.org/blink/trunk

Visibility:
Public.

More Reviews

Description

Add fast path for querySelector(All) with id selector, class selector and tag selector. Adding class selector in the same manner as id selector. So I implemented offline (not live node list) getElementsByClassName in SelectorQuery.cpp. However, this also affects performance regressions of Parser/query-selector-*.html. So added more fast path for querySelector(All) with one simple selector (only id selector, class selector or tag selector). BUG=253425 Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=155068

Patch Set 1 #

Total comments: 7

Patch Set 2 : #

Total comments: 1

Patch Set 3 : #

Patch Set 4 : #

Total comments: 22

Patch Set 5 : #

Total comments: 2

Patch Set 6 : Patch for landing #

Patch Set 7 : Fix mac build failure #

Patch Set 8 : Patch for landing (rebased) #

Created: 7 years, 4 months ago

Download [raw] [tar.bz2]

	Unified diffs	Side-by-side diffs	Delta from patch set	Stats (+416 lines, -79 lines)			Patch
A	LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html	View	1 2 3 4 5	1 chunk	+48 lines, -0 lines	0 comments	Download
A	LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2-expected.txt	View	1	1 chunk	+11 lines, -0 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-class-deep.html	View	1 2 3 4	1 chunk	+2 lines, -2 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-class-first.html	View	1 2 3 4	1 chunk	+2 lines, -4 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-class-last.html	View	1 2 3 4	1 chunk	+2 lines, -2 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-deep.html	View	1 2 3 4	1 chunk	+4 lines, -2 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-first.html	View	1 2 3 4	1 chunk	+4 lines, -4 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-id-deep.html	View	1 2 3 4	1 chunk	+2 lines, -2 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-id-first.html	View	1 2 3 4	1 chunk	+2 lines, -4 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-id-last.html	View	1 2 3 4	1 chunk	+2 lines, -2 lines	0 comments	Download
A +	PerformanceTests/Parser/query-selector-all-last.html	View	1 2 3 4	1 chunk	+4 lines, -4 lines	0 comments	Download
M	Source/core/dom/SelectorQuery.h	View	1 2 3 4 5 6 7	2 chunks	+13 lines, -3 lines	0 comments	Download
M	Source/core/dom/SelectorQuery.cpp	View	1 2 3 4 5 6 7	3 chunks	+320 lines, -50 lines	0 comments	Download

Messages

Total messages: 23 (0 generated)

Expand Messages | Collapse Messages

haraken

The change looks OK. Do you have any performance number about the original bug? https://codereview.chromium.org/18732004/diff/1/LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html ...

7 years, 5 months ago (2013-07-08 06:13:16 UTC) #2

tasak

> Do you have any performance number about the original bug? before applying this patch: ...

7 years, 5 months ago (2013-07-08 09:46:17 UTC) #3

haraken

https://codereview.chromium.org/18732004/diff/8005/Source/core/dom/SelectorQuery.cpp File Source/core/dom/SelectorQuery.cpp (right): https://codereview.chromium.org/18732004/diff/8005/Source/core/dom/SelectorQuery.cpp#newcode169 Source/core/dom/SelectorQuery.cpp:169: RefPtr<NodeList> nodeList = rootNode->getElementsByClassName(selector->value()); oh, this will create unexpected ...

7 years, 5 months ago (2013-07-08 11:33:46 UTC) #5

tasak

On 2013/07/08 11:33:46, haraken wrote: > https://codereview.chromium.org/18732004/diff/8005/Source/core/dom/SelectorQuery.cpp > File Source/core/dom/SelectorQuery.cpp (right): > > https://codereview.chromium.org/18732004/diff/8005/Source/core/dom/SelectorQuery.cpp#newcode169 > ...

7 years, 5 months ago (2013-07-09 03:24:06 UTC) #6

tasak

Since ClassNodeList uses ElementTraversal, added ElementTraversal for class selector to findTraverseRoot. Now 129,280±3.40% 13% slower ...

7 years, 5 months ago (2013-07-11 08:41:44 UTC) #7

esprehn

On 2013/07/11 11:02:06, haraken wrote: > +esprehn: would you take a look? This is going ...

7 years, 5 months ago (2013-07-12 00:55:10 UTC) #9

tasak

On 2013/07/12 00:55:10, esprehn wrote: > On 2013/07/11 11:02:06, haraken wrote: > > +esprehn: would ...

7 years, 5 months ago (2013-07-12 05:11:27 UTC) #10

tasak

> What do you think about this idea? The Patch Set 4 shows my idea.

7 years, 5 months ago (2013-07-12 06:19:46 UTC) #11

esprehn

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQuery.cpp File Source/core/dom/SelectorQuery.cpp (right): https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQuery.cpp#newcode107 Source/core/dom/SelectorQuery.cpp:107: if (firstMatchOnly) I'd rather you just created two methods. ...

7 years, 5 months ago (2013-07-12 07:17:16 UTC) #12

tasak

Thank you for reviewing. I found performance regressions of Parser/query-selector-first (existing one) and Parser/query-selector-all-first (newly ...

7 years, 5 months ago (2013-07-16 07:46:59 UTC) #13

Thank you for reviewing.

I found performance regressions of Parser/query-selector-first (existing one)
and Parser/query-selector-all-first (newly added one).

So I added fast path for a simple selector, i.e. just id selector (e.g. #id),
class selector (e.g. .class) or tag selector (e.g. div).

Now querySelectorAll('.class') score in
http://jsperf.com/attribute-versus-class-querying is almost the same as jquery's
one.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:107: if (firstMatchOnly)
On 2013/07/12 07:17:17, esprehn wrote:
> I'd rather you just created two methods.
> 
> Element* findElementByClassName(...);
> void findElementsByClassName(..., Vector&);

I see.
Done.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:115: return m_selectors.size() == 1 &&
rootNode->inDocument() && !rootNode->document()->inQuirksMode();
On 2013/07/12 07:17:17, esprehn wrote:
> Why does the root need to be inDocument?

To use treeScope()->getElementById.

I guess, we have smaller nodes if rootNode is not in document.
So we could probably use slow path...

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:123: // The travseralRoots may be empty,
regardless of the returned bool value, if this method finds that the selectors
won't
On 2013/07/12 07:17:17, esprehn wrote:
> It seems like you're trying to do too much inside this one method.

I see. I moved the codes for finding elements with a given class name to
ClassElementList and ClassRootNodeList.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:137: for (const CSSSelector* selector =
m_selectors[0].selector; selector; selector = selector->tagHistory()) {
On 2013/07/12 07:17:17, esprehn wrote:
> Do you need an ASSERT at the start of this method? [0] seems like out of bound
> access :)

I see.
Done.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:148: }
On 2013/07/12 07:17:17, esprehn wrote:
> This loop is confusing, what is it doing?

This loop is:
- looking at each selector from right to left, e.g. if we have ".foo > div", we
will check firstly "> div". Next, we will check ".foo".

- if the rightmost selector (except subselectors) is "#id" or ".class",
matchTraverseRoots is true. This means, we can only see elements with the id or
with the class name.

- if we have "#id" or ".class" selector, but the selector is not rightmost one
(e.g. #id > div or .class > div), we don't need to check elements with the id or
with the class name. We need all descendants of the elements. matchTraverseRoots
is false.

- If we find "~" or "+", e.g. #id + div, we don't need to see all descendants of
#id element. Instead, we have to see all descendants of #id element's siblings.
In this case, startFromParent is true.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:166: element =
ElementTraversal::nextSkippingChildren(element, rootNode);
On 2013/07/12 07:17:17, esprehn wrote:
> Why doesn't this need to be recursive?

Because this is for finding traversal roots (e.g. ".foo > div" is given.
Elements with ".foo" are traversal roots in executeQueryAll.

> If this element is ".foo" and there's
> another ".foo" inside it don't we need to find it?

In executeQueryAll, we will use ElementTraversal::firstWithin and
ElementTraversal::next by using the element as root node.

So another ".foo" will be found.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:195: if (matchTraverseRoots) {
On 2013/07/12 07:17:17, esprehn wrote:
> This is weird, even if matchTraverseRoots is false you still use traverseRoots
> below. I think you need to break up findTraverseRoots in to several steps, the
> algorithm inside is complicated and appears to be doing a lot of steps at the
> same time.

The matchTraverseRoots means whether elements found by "findTraverseRoots" can
be results of querySelectorAll or not.

So if matchTraverseRoots is true, we can only check elements in traverseRoots.
Otherwise, we will see all descendants of elements in traverseRoots and check if
each descendant matches a given selector.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:205: unsigned selectorCount =
m_selectors.size();
On 2013/07/12 07:17:17, esprehn wrote:
> No need to cache this in a local

Done.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:273: return element &&
(isTreeScopeRoot(rootNode) || element->isDescendantOf(rootNode)) ? element : 0;
On 2013/07/12 07:17:17, esprehn wrote:
> Remove the isTreeScopeRoot checks, isDescendantOf already knows how to handle
> that with a fast path.

We need this check, because this doesn't use findTraverseRoot.
This is a fast path for querySelector('#id') or querySelector('.class').

The reason why I added the code is that I found performance regression of
PerformanceTests/Parser/query-selector-first.

Now findTraverseRoot code is a fast path for querySelector('div > #id') or
querySelector('#id > div') or ...

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:279: return nodes.size() > 0 ?
toElement(nodes.at(0)) : 0;
On 2013/07/12 07:17:17, esprehn wrote:
> nodes.isEmpty() ? 0 : nodes.first();

I added findElementByClassName and removed this code.

https://codereview.chromium.org/18732004/diff/24001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:283: std::pair<bool, Node*> traverseRoot =
findTraverseRoot(rootNode);
On 2013/07/12 07:17:17, esprehn wrote:
> I think you want to return a Node* and have an out param you pass in. What's
> this boolean here?

Done.

tasak

I ran performance tests and obtained the results: Result Test Unit before after /Parser/query-selector-all-class-deep:Runs runs/s ...

7 years, 5 months ago (2013-07-16 09:01:42 UTC) #14

esprehn

LGTM. This looks much better. It's unfortunate we need to add so much code for ...

7 years, 5 months ago (2013-07-25 23:11:26 UTC) #16

tasak

Thank you, esprehn. https://codereview.chromium.org/18732004/diff/29001/LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html File LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html (right): https://codereview.chromium.org/18732004/diff/29001/LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html#newcode24 LayoutTests/fast/dom/SelectorAPI/dumpNodeList-2.html:24: return this; On 2013/07/25 23:11:27, esprehn ...

7 years, 5 months ago (2013-07-26 04:38:52 UTC) #17