Separate the id fast path in SelectorQuery

Desktop / Chromium - esprehn [chromium.org] - 15 April 2017 04:56 EDT

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}

8f55866 Separate the id fast path in SelectorQuery.
.../WebKit/Source/core/dom/SelectorQuery.cpp | 168 +++++++++++----------
third_party/WebKit/Source/core/dom/SelectorQuery.h | 6 +
.../WebKit/Source/core/dom/SelectorQueryTest.cpp | 39 ++---
3 files changed, 118 insertions(+), 95 deletions(-)

Upstream: git.chromium.org


  • Share