Only cache nth-indices when child count > 32.

Only cache nth-indices when child count > 32.

When matching :nth-* selectors, we sparsely cache the child index count
into a hashmap for the parent element. Doing this regardlessly gave us
a performance penalty for small number of children as where noticed in
a performance degradation for [1].

The new approach is to not cache any indices until we match an :nth-*
selector for which we walk more than 32 siblings. The number 32 were
proposed in the bug report, and it turns out to be quite suitable given
the experiments which were done comparing the implementation not using
a cache at all, and the implementation where we cached regardlessly.

We trigger caching for nth-of-type indices based on the sibling count
as well, but not the sibling-of-type count as that would cause terrible
performance if the elements of the same type were sparse compared to
other siblings.

Gives a > 40% performance improvement for [1].

[1] blink_perf.css:PseudoClassSelectors.

BUG=483338
TEST=blink_perf.css:PseudoClassSelectors

Committed: https://crrev.com/4b3bb3fcc9a3e6a9248cd4592e4f1f61a6462cf8
Cr-Commit-Position: refs/heads/master@{#374356}

[rune, 2016-02-02 16:08:40]

The CQ bit was checked by rune@opera.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-02 16:11:45]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1655993005/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1655993005/1

[commit-bot: I haz the power, 2016-02-02 16:16:40]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-02 16:16:41]

Dry run: Try jobs failed on following builders:
  ios_rel_device_ninja on tryserver.chromium.mac (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.mac/builders/ios_rel_device_ni...)

[rune, 2016-02-02 16:42:30]

The CQ bit was checked by rune@opera.com to run a CQ dry run

[commit-bot: I haz the power, 2016-02-02 16:44:04]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1655993005/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1655993005/20001

[commit-bot: I haz the power, 2016-02-02 18:11:50]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-02-02 18:11:51]

Dry run: This issue passed the CQ dry run.

[rune, 2016-02-03 11:48:34]

rune@opera.com changed reviewers:
+ esprehn@chromium.org

[rune, 2016-02-08 13:03:32]

ping

[esprehn, 2016-02-08 21:19:08]

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/dom/NthIndexCache.cpp (right):

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:34: const unsigned
CachedSiblingCountLimit = 32;
kCachedSiblingCountLimit

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:115:
ASSERT(element.parentNode());
parentNode is null for children of a ShadowRoot, I don't think this is right. do
you want parentOrShadowHostNode() ?

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:123: unsigned
NthIndexCache::nthOfTypeIndex(Element& element)
Could these be const?

[rune, 2016-02-08 23:42:14]

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/dom/NthIndexCache.cpp (right):

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:34: const unsigned
CachedSiblingCountLimit = 32;
On 2016/02/08 21:19:07, esprehn wrote:
> kCachedSiblingCountLimit

Acknowledged.

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:115:
ASSERT(element.parentNode());
On 2016/02/08 21:19:07, esprehn wrote:
> parentNode is null for children of a ShadowRoot, I don't think this is right.
do
> you want parentOrShadowHostNode() ?

parentNode is the ShadowRoot node for children of ShadowRoot. parentNode is null
for ShadowRoot, but we will not try to match for Shadow root. However, I'll need
to check querySelector(All) on elements not in the document or document
fragment. Might be that this ASSERT fails in such cases.

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:123: unsigned
NthIndexCache::nthOfTypeIndex(Element& element)
On 2016/02/08 21:19:07, esprehn wrote:
> Could these be const?

The methods are static.

[rune, 2016-02-09 08:24:57]

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/dom/NthIndexCache.cpp (right):

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:34: const unsigned
CachedSiblingCountLimit = 32;
On 2016/02/08 23:42:14, rune wrote:
> On 2016/02/08 21:19:07, esprehn wrote:
> > kCachedSiblingCountLimit
> 
> Acknowledged.

Done.

https://codereview.chromium.org/1655993005/diff/20001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/dom/NthIndexCache.cpp:115:
ASSERT(element.parentNode());
On 2016/02/08 23:42:14, rune wrote:
> On 2016/02/08 21:19:07, esprehn wrote:
> > parentNode is null for children of a ShadowRoot, I don't think this is
right.
> do
> > you want parentOrShadowHostNode() ?
> 
> parentNode is the ShadowRoot node for children of ShadowRoot. parentNode is
null
> for ShadowRoot, but we will not try to match for Shadow root. However, I'll
need
> to check querySelector(All) on elements not in the document or document
> fragment. Might be that this ASSERT fails in such cases.

The calls to retrieve nth-indices in SelectorChecker are all protected by "if
(element.parentElementOrDocumentFragment())", so it looks fine. I could replace
the parentNode() with parentElementOrDocumentFragment(), but the assert is to
check for the safe use of parentNode() below.

[esprehn, 2016-02-09 09:37:58]

lgtm

[rune, 2016-02-09 09:47:49]

The CQ bit was checked by rune@opera.com

[commit-bot: I haz the power, 2016-02-09 09:49:23]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1655993005/40001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1655993005/40001

[commit-bot: I haz the power, 2016-02-09 12:06:35]

Committed patchset #3 (id:40001)

[commit-bot: I haz the power, 2016-02-09 12:08:44]

Description was changed from

==========
Only cache nth-indices when child count > 32.

When matching :nth-* selectors, we sparsely cache the child index count
into a hashmap for the parent element. Doing this regardlessly gave us
a performance penalty for small number of children as where noticed in
a performance degradation for [1].

The new approach is to not cache any indices until we match an :nth-*
selector for which we walk more than 32 siblings. The number 32 were
proposed in the bug report, and it turns out to be quite suitable given
the experiments which were done comparing the implementation not using
a cache at all, and the implementation where we cached regardlessly.

We trigger caching for nth-of-type indices based on the sibling count
as well, but not the sibling-of-type count as that would cause terrible
performance if the elements of the same type were sparse compared to
other siblings.

Gives a > 40% performance improvement for [1].

[1] blink_perf.css:PseudoClassSelectors.

BUG=483338
TEST=blink_perf.css:PseudoClassSelectors
==========

to

==========
Only cache nth-indices when child count > 32.

When matching :nth-* selectors, we sparsely cache the child index count
into a hashmap for the parent element. Doing this regardlessly gave us
a performance penalty for small number of children as where noticed in
a performance degradation for [1].

The new approach is to not cache any indices until we match an :nth-*
selector for which we walk more than 32 siblings. The number 32 were
proposed in the bug report, and it turns out to be quite suitable given
the experiments which were done comparing the implementation not using
a cache at all, and the implementation where we cached regardlessly.

We trigger caching for nth-of-type indices based on the sibling count
as well, but not the sibling-of-type count as that would cause terrible
performance if the elements of the same type were sparse compared to
other siblings.

Gives a > 40% performance improvement for [1].

[1] blink_perf.css:PseudoClassSelectors.

BUG=483338
TEST=blink_perf.css:PseudoClassSelectors

Committed: https://crrev.com/4b3bb3fcc9a3e6a9248cd4592e4f1f61a6462cf8
Cr-Commit-Position: refs/heads/master@{#374356}
==========

[commit-bot: I haz the power, 2016-02-09 12:08:45]

Patchset 3 (id:??) landed as
https://crrev.com/4b3bb3fcc9a3e6a9248cd4592e4f1f61a6462cf8
Cr-Commit-Position: refs/heads/master@{#374356}