988740 - Improve querySelector score on https://www.webkit.org/blog-files/css-jit-introduction/html5-single-page-microbenchmark.html

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[mdew]

User Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Firefox/31.0 (Beta/Release)
Build ID: 20140324150004

Steps to reproduce:

Visit and run test.
https://www.webkit.org/blog-files/css-jit-introduction/html5-single-page-microbenchmark.html



Actual results:

Currently nightly got:
Total time spent matching selectors = 11320ms.
That is about 2417 matching operations per millisecond.
Chrome got:
Total time spent matching selectors = 1138ms.
That is about 24047 matching operations per millisecond.


Expected results:

Improve time matching css selectors.

Comment 1

[Boris Zbarsky [:bzbarsky]]

The really slow to match selectors in the test are these three:

                // Adjacent failure.
                target.querySelector('.nope p+p~p');
                target.querySelector('.nope div+p+p~p');
                target.querySelector('.nope p+p~p a');

and a slightly slow one is:

                target.querySelector('.nope tr+tr~tr>td a');

For everything else we seem to be faster than Chrome.

Note that replacing '.nope p+p~p' with '.nope p~p~p' makes the matching _much_ faster in Gecko, because then we don't end up doing the "avoid greedy matching" recursion in SelectorMatchesTree.

What I seem to recall WebKit doing here is that their equivalent of SelectorMatchesTree can return a tri-state one of the states of which is "never matches due to ancestor not matching" or some such.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Testcase, to make sure it doesn't go away

Comment 3

[Boris Zbarsky [:bzbarsky]]

So in particular, given a selector of this form:

  nosuchname > p+p~p

and a node with lots of <p> kids our current greedy matching fail avoidance will match the rightmost p, then match a previous "p" sibling, then see that it matches but the following combinator is not '~', so we will actually try walking to a yet more previous sibling first, effectively comparing "p" to all the elements in the list, before we unwind the stack.  That's the "tests from the top of the content tree, down" comment in SelectorMatchesTree, except we're actually testing from left to right.

Just switching SelectorMatchesTree to a tristate here won't help on its own, since as far as I can tell we don't examine the parent until we get to the end of the list.

Note that this is a querySelector-specific issue to some extent, at least when the non-matching thing is ".nope", since during normal style resolution the Bloom filter would just bail out from all this stuff early.

Comment 4

[Boris Zbarsky [:bzbarsky]]

David, can we do something smarter for this case?  e.g. could we try actually doing the tristate thing and SelectorMatchesTree() on selector->mNext in this case before we walk to the previous element?

Comment 5

[Emilio Cobos Álvarez (:emilio)]

On current nightly I get 1245ms with stylo enabled, so this is fixed by bug 1410624.

Comment 6

[Kacper Michajłow [:kasper93]]

For the record, so everyone knows how we do now:

Firefox Nightly (20171106100122)
- Stylo Enabled      : 1345ms
- Stylo Disabled     : 12494ms

Chrome v62.0.3202.89 : 502ms

Comment 7

[Emilio Cobos Álvarez (:emilio)]

(In reply to Kacper Michajłow [:kasper93] from comment #6)
> For the record, so everyone knows how we do now:
> 
> Firefox Nightly (20171106100122)
> - Stylo Enabled      : 1345ms
> - Stylo Disabled     : 12494ms
> 
> Chrome v62.0.3202.89 : 502ms

Yeah, note that chrome does well just "by chance", in the sense that they happen to have an optimization of dubious value for when there's a className in an ancestor selector, so they end up not doing any selector-matching.

From my measurements when I implemented this doing some random browsing and speedometer, I never encountered such a selector, plus the optimization looked somewhat dubious in other cases.