Add fast path for tag#id selector queries

Add fast path for #id / tag#id selector queries

Add fast path for #id / tag#id selector queries, even in the cases where the
case where the document contains multiple elements with the same id.

DocumentOrderedMap was updated so that the hash table values contain the
ordered vector of all matching Elements (lazily populated).

DocumentOrderedMap now supports getAllElementsById() operation in addition
to the pre-existing getElementById() one.

I see the following impact of BrowserMark test cases (Linux Desktop):
05_DOM_Create_Source: +190.5% (~2.9x better)
06_DOM_Dynamic_Create: +150.0% (~2.5x better)

Those tests were spending most of their time traversing the tree due to the
"div#hidden_playground" query. That query would go through the slow path
because:
- We did not support going through fast path for tag#id queries, only #id
  ones.
- The id is not unique in the document.

This is a partial merge of WebKit r150187 by <rniwa@webkit.org>;.

R=esprehn
BUG=323962
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=164102

[Inactive, 2013-11-27 18:37:06]

On 2013/11/27 17:11:36, Chris Dumez wrote:

FYI, the sources of these tests are visible at:
http://browsermark.rightware.com/tests/benchmarks/dom/create_source/test.js
http://browsermark.rightware.com/tests/benchmarks/dom/dynamic_create/test.js

[abarth-chromium, 2013-12-02 19:16:10]

We've tried to merge these CLs before and gotten rejected by ClusterFuzz...

esprehn, would you be interested in reviewing this CL?

[Inactive, 2013-12-02 19:24:11]

On 2013/12/02 19:16:10, abarth wrote:
> We've tried to merge these CLs before and gotten rejected by ClusterFuzz...

Is this something I can check before landing? Last I checked, I did not have
access to ClusterFuzz but I did get bug reports filed against my patches after
landing because of ClusterFuzz. I would really like to make this land upstream
due to the big impact on several BrowserMark test cases.

[esprehn, 2013-12-02 19:41:46]

On 2013/12/02 19:16:10, abarth wrote:
> We've tried to merge these CLs before and gotten rejected by ClusterFuzz...
> 
> esprehn, would you be interested in reviewing this CL?

I'll take a look.

[abarth-chromium, 2013-12-02 20:24:16]

On 2013/12/02 19:24:11, Chris Dumez (Away) wrote:
> Is this something I can check before landing?

I believe this was the bug:

https://code.google.com/p/chromium/issues/detail?id=271131

It might not be an issue with your CL.  It's just something to watch out for.

[Inactive, 2013-12-02 20:32:45]

On 2013/12/02 20:24:16, abarth wrote:
> On 2013/12/02 19:24:11, Chris Dumez (Away) wrote:
> > Is this something I can check before landing?
> 
> I believe this was the bug:
> 
> https://code.google.com/p/chromium/issues/detail?id=271131
> 
> It might not be an issue with your CL.  It's just something to watch out for.

Thanks! I'll check if I can reproduce with my patch.

[esprehn, 2013-12-02 20:38:04]

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:92: ASSERT(it != m_map.end());
The old code definitely didn't ASSERT this, why is there always a match now?

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:95: ASSERT(entry.count);
This doesn't seem right, why will find() always get a match?

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:103: entry.orderedList.clear(); // FIXME:
Remove the element instead if there are only few items left.
a few?

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/SelectorQuery...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/SelectorQuery...
Source/core/dom/SelectorQuery.cpp:478: return selectorMatches(selector,
*element, rootNode) ? element : 0;
Woah looks like copy pasta?

[Inactive, 2013-12-02 20:47:25]

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:92: ASSERT(it != m_map.end());
On 2013/12/02 20:38:04, esprehn wrote:
> The old code definitely didn't ASSERT this, why is there always a match now?

This believe this is actually what caused the Clusterfuzz crash that abarth
mentioned (based on the backtrace). It is true, that the new code is stricter. I
am looking at the call sites right now to understand if this assumption is
correct or not.

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/SelectorQuery...
File Source/core/dom/SelectorQuery.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/SelectorQuery...
Source/core/dom/SelectorQuery.cpp:478: return selectorMatches(selector,
*element, rootNode) ? element : 0;
On 2013/12/02 20:38:04, esprehn wrote:
> Woah looks like copy pasta?

Yes, SelectorDataList::executeQueryFirst() and
SelectorDataList::executeQueryAll() are currently mostly (except the former
returns as soon as a match is found and the latter appends matches to a vector)
duplicated because they are really hot.

This was done by this earlier optimization:
https://chromiumcodereview.appspot.com/18732004

I will see what I can do about this.

[Inactive, 2013-12-02 21:24:42]

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:92: ASSERT(it != m_map.end());
On 2013/12/02 20:47:26, Chris Dumez (Away) wrote:
> On 2013/12/02 20:38:04, esprehn wrote:
> > The old code definitely didn't ASSERT this, why is there always a match now?
> 
> This believe this is actually what caused the Clusterfuzz crash that abarth
> mentioned (based on the backtrace). It is true, that the new code is stricter.
I
> am looking at the call sites right now to understand if this assumption is
> correct or not.

Yes, I confirmed this is indeed the source of the ClusterFuzz crash. I will keep
the if check here.

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:103: entry.orderedList.clear(); // FIXME:
Remove the element instead if there are only few items left.
On 2013/12/02 20:38:04, esprehn wrote:
> a few?

I believe the idea on WebKit side was that it may not be worth removing the
element from the vector if it contains more than a few elements, likely because
finding the element in the vector is O(n) and removing it is also O(n)).

Considering this is a very specific and tricky optimization, I would propose to
simply remove the FIXME.

[Inactive, 2013-12-02 21:53:25]

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:92: ASSERT(it != m_map.end());
On 2013/12/02 20:38:04, esprehn wrote:
> The old code definitely didn't ASSERT this, why is there always a match now?

Done.

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:101: entry.element = 0;
Instead of resetting it unconditionally to 0 here, I use the second element in
entry.orderedList if available.

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:103: entry.orderedList.clear(); // FIXME:
Remove the element instead if there are only few items left.
On 2013/12/02 21:24:42, Chris Dumez (Away) wrote:
> On 2013/12/02 20:38:04, esprehn wrote:
> > a few?
> 
> I believe the idea on WebKit side was that it may not be worth removing the
> element from the vector if it contains more than a few elements, likely
because
> finding the element in the vector is O(n) and removing it is also O(n)).
> 
> Considering this is a very specific and tricky optimization, I would propose
to
> simply remove the FIXME.

Done.

https://codereview.chromium.org/92083002/diff/1/Source/core/dom/DocumentOrder...
Source/core/dom/DocumentOrderedMap.cpp:152: for (Element* element =
entry.element ? entry.element :
ElementTraversal::firstWithin(*scope->rootNode()); element; element =
ElementTraversal::next(*element)) {
As loop condition, I now use "entry.orderedList.size() < entry.count", instead
of "element" to abort tree traversing as soon as we found the expected number of
elements.

I added an ASSERT(element) inside the loop instead as it should always be
non-null, as long as (entry.orderedList.size() < entry.count).

[Inactive, 2013-12-05 15:57:24]

esprehn@, could you please take another look when you get a chance?

[Inactive, 2013-12-10 15:34:28]

On 2013/12/05 15:57:24, Chris Dumez wrote:
> esprehn@, could you please take another look when you get a chance?

ping review? Anyone has an opinion on this?

Without this change, we are 2-3 times slower than WebKit on several tests in the
Browsermark benchmark.

[Inactive, 2013-12-16 15:37:33]

Could I please get feedback on this patch?

Would it help if I split the patch into
- Using a single hash table in DocumentOrderedMap instead of 2
- tag#id fast patch in selectors

I am happy to help making this a bit easier to review if this is needed.

[esprehn, 2013-12-17 18:57:47]

Do we know how often pages have multiple ids and do querySelectorAll for them?

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

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:461: if
(UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
Remove UNLIKELY unless you have a perf test to show it does something.

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:463: ASSERT(elements);
Should return a reference from getElementsById and not ASSERT here.

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/TreeScope...
File Source/core/dom/TreeScope.cpp (right):

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/TreeScope...
Source/core/dom/TreeScope.cpp:158: return 0;
Why not return emptyVector? We should just add a static local I think.

[Inactive, 2013-12-17 21:17:24]

On 2013/12/17 18:57:47, esprehn wrote:
> Do we know how often pages have multiple ids and do querySelectorAll for them?

Valid question considering the purpose of this patch was mainly to catch up with
WebKit on BrowserMark 2 benchmark.

I visited random WebSites and saw it being used on:
- http://www.amazon.com/ (#8 on Alexa)
Calling TreeScope::getAllElementsById(title)
Calling TreeScope::getAllElementsById(hover)
Calling TreeScope::getAllElementsById(title)
Calling TreeScope::getAllElementsById(hover)

http://espn.go.com/ (#77 on Alexa)
Calling TreeScope::getAllElementsById(top-stories)

salesforce.com (#179 on Alexa)
Calling TreeScope::getAllElementsById(cse-search-box)
Calling TreeScope::getAllElementsById(search-submit)
Calling TreeScope::getAllElementsById(searchtext)

Samsung.com (#236 on Alexa)
Calling TreeScope::getAllElementsById(hero-container)
Calling TreeScope::getAllElementsById(hero-media)

nfl.com (#248 on Alexa)
Calling TreeScope::getAllElementsById(HP11_content_stream-3-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-3-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-7-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-7-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-8-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-8-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-11-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-11-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-12-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-12-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-13-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-13-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-29-img)
Calling TreeScope::getAllElementsById(HP11_content_stream-29-img)

[Inactive, 2013-12-17 21:20:24]

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

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:461: if
(UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
On 2013/12/17 18:57:48, esprehn wrote:
> Remove UNLIKELY unless you have a perf test to show it does something.

Done.

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/SelectorQ...
Source/core/dom/SelectorQuery.cpp:463: ASSERT(elements);
On 2013/12/17 18:57:48, esprehn wrote:
> Should return a reference from getElementsById and not ASSERT here.

Done.

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/TreeScope...
File Source/core/dom/TreeScope.cpp (right):

https://codereview.chromium.org/92083002/diff/40001/Source/core/dom/TreeScope...
Source/core/dom/TreeScope.cpp:158: return 0;
On 2013/12/17 18:57:48, esprehn wrote:
> Why not return emptyVector? We should just add a static local I think.

Done.

[esprehn, 2013-12-18 00:16:50]

lgtm, thanks for doing some research about the numbers!

https://codereview.chromium.org/92083002/diff/60001/Source/core/dom/DocumentO...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/60001/Source/core/dom/DocumentO...
Source/core/dom/DocumentOrderedMap.cpp:148:
DEFINE_STATIC_LOCAL(Vector<Element*>, emptyVector, ());
nit: This should be at the top of the function.

[Inactive, 2013-12-18 15:25:56]

https://codereview.chromium.org/92083002/diff/60001/Source/core/dom/DocumentO...
File Source/core/dom/DocumentOrderedMap.cpp (right):

https://codereview.chromium.org/92083002/diff/60001/Source/core/dom/DocumentO...
Source/core/dom/DocumentOrderedMap.cpp:148:
DEFINE_STATIC_LOCAL(Vector<Element*>, emptyVector, ());
On 2013/12/18 00:16:50, esprehn wrote:
> nit: This should be at the top of the function.

Done.

[commit-bot: I haz the power, 2013-12-18 15:26:39]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/ch.dumez@samsung.com/92083002/80001

[commit-bot: I haz the power, 2013-12-18 17:27:58]

Change committed as 164102