Separate the id fast path in SelectorQuery.

Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

Note: These numbers were all taken on a 2013 Mac Pro trashcan.

BUG=703900
Review-Url: https://codereview.chromium.org/2820013002
Cr-Commit-Position: refs/heads/master@{#464861}
Committed: https://chromium.googlesource.com/chromium/src/+/8f55866589a385c959b0e9f0a3bd1f70e4139a66

[esprehn, 2017-04-15 01:17:52]

Description was changed from

==========
ExecuteWithId.

BUG=
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in non-All queries like
document.querySelector("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also caches the id information so we don't need to scan the selector
each time.

BUG=703900
==========

[esprehn, 2017-04-15 01:22:33]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in non-All queries like
document.querySelector("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also caches the id information so we don't need to scan the selector
each time.

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in non-All queries like
document.querySelector("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

BUG=703900
==========

[esprehn, 2017-04-15 01:23:57]

The CQ bit was checked by esprehn@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-15 01:24:11]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[esprehn, 2017-04-15 01:27:53]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in non-All queries like
document.querySelector("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

BUG=703900
==========

[esprehn, 2017-04-15 01:53:38]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:
ex.  document.querySelectorAll("#catlinks .mw-normal-catlinks");
goes from taking 0.32ms to taking 0.03ms.

BUG=703900
==========

[esprehn, 2017-04-15 02:05:07]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:
ex.  document.querySelectorAll("#catlinks .mw-normal-catlinks");
goes from taking 0.32ms to taking 0.03ms.

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us very close to Safari in speed on queries
containing ids (bindings and NodeList overhead are now the primary
issues).

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost position, for example the above
benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

[esprehn, 2017-04-15 02:09:01]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us very close to Safari in speed on queries
containing ids (bindings and NodeList overhead are now the primary
issues).

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost position, for example the above
benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

[esprehn, 2017-04-15 02:09:20]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

[esprehn, 2017-04-15 02:10:49]

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

[esprehn, 2017-04-15 02:11:32]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

[dglazkov, 2017-04-15 02:14:22]

lgtm

[esprehn, 2017-04-15 02:39:24]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

Note: These numbers were all taken on a 2013 Mac Pro trashcan.

BUG=703900
==========

[commit-bot: I haz the power, 2017-04-15 04:33:30]

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

[commit-bot: I haz the power, 2017-04-15 04:33:31]

Dry run: This issue passed the CQ dry run.

[esprehn, 2017-04-15 05:34:49]

The CQ bit was checked by esprehn@chromium.org

[commit-bot: I haz the power, 2017-04-15 05:34:56]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-15 08:57:01]

CQ is committing da patch.

Bot data: {"patchset_id": 40001, "attempt_start_ts": 1492234489625930,
"parent_rev": "4aac471cc7394249b1a3d32a777d0539c2ae54d5", "commit_rev":
"8f55866589a385c959b0e9f0a3bd1f70e4139a66"}

[commit-bot: I haz the power, 2017-04-15 08:58:34]

Description was changed from

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

Note: These numbers were all taken on a 2013 Mac Pro trashcan.

BUG=703900
==========

to

==========
Separate the id fast path in SelectorQuery.

This allows us to use the id to limit the search in *All queries like
document.querySelectorAll("#scope .foo") where previously we'd scan the entire
document looking for .foo, now we'll first use the id map to find #scope.

This also means we'll now use the class fast path for queries like
document.querySelector(".foo .bar") where previously we disabled the class
fast path entirely just in case there was an id selector somewhere past
the class selector (ex. #foo .bar).

Finally I cached the id information so we don't need to scan the selector
each time.

A future patch will be able to use this data and new id specific path to
support using the id map for elements inside a ShadowRoot that is not
attached to the tree making queries like querySelector("#foo") O(1) when
the host scope is disconnected.

On an example page like Wikpedia cats (https://en.wikipedia.org/wiki/Cat)
with 9800 elements this yields a 25% improvement in class queries that can
now take the class fast path that needed to scan the entire document, and
up to a 90% improvement in queries that can now take the id fast path to
either quickly abort when the id is not present, or limit the scope to a
small number of elements:

ex. 
var t = performance.now();
document.querySelectorAll("#catlinks .mw-normal-catlinks");
performance.now() - t;

goes from taking 0.32ms to taking 0.03ms.

Or simulating an doing many queries:
var t = performance.now();
for (let i = 0; i < 100; ++i) {
  document.querySelectorAll("#catlinks .mw-normal-catlinks");
}
performance.now() - t;

Goes from taking 15ms to taking 0.24ms.

This improvement brings us within 20% of the speed of Safari on all
queries containing ids. Bindings and NodeList TraceWrapper overhead are
now the primary issues. 

(We already beat Firefox on all these benchmarks, and they don't handle
ids anywhere except in the rightmost subs selector, for example the
above benchmarks take 0.5ms and 25ms respectively.)

Note: These numbers were all taken on a 2013 Mac Pro trashcan.

BUG=703900

Review-Url: https://codereview.chromium.org/2820013002
Cr-Commit-Position: refs/heads/master@{#464861}
Committed:
https://chromium.googlesource.com/chromium/src/+/8f55866589a385c959b0e9f0a3bd...
==========

[commit-bot: I haz the power, 2017-04-15 08:58:36]

Committed patchset #3 (id:40001) as
https://chromium.googlesource.com/chromium/src/+/8f55866589a385c959b0e9f0a3bd...