1027978 - consider using bloom filter in querySelectorAll()

Status: NEW

(Core :: DOM: Core & HTML, defect, P3)

Description

[Ben Kelly [:bkelly, not reviewing]]

On twitter we had an interesting conversation with Brian Kardell.  He was asking if a bloom filter was used for querySelectorAll().

Boris indicated that while we use bloom filters in other places for CSS selectors, we don't currently use it for querySelectAll().  At the time it was implemented it was a net-negative in terms of performance.

However, Boris also suggests that the situation could have changed.  For example, we now have a selector cache in querySelectorAll().

He also mentioned that we need to be careful about measuring micro-benchmarks vs. real-world workloads.

Full twitter conversation is here:

  https://twitter.com/briankardell/status/479721371165929472

Comment 1

[Ben Kelly [:bkelly, not reviewing]]

Spam Boris's request queue as requested. :-)

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Microish benchmark

Some notes to self:

1)  Chrome (but not Safari) has some sort of optimization where if there is only one selector in the selector list and that selector has a descendant combinator where the LHS is an id selector then they do some sort of fast path.  That might be worth looking into, but is somewhat independent of this bug.

2)  We'd need to associate a hash with each selector in the selector list.  Probably want to factor out the code in RuleValue::CollectAncestorHashes.  An initial investigation can probably just recompute this on each qSA call, but long-term we want to cache it like we do the parsed selectors.

3)  Need to maintain the ancestor push/pop stuff as we walk over the tree.

4)  Need to check the filter; probably need to pass the hashes into nsCSSRuleProcessor::SelectorListMatches.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Another note to self: The steps in bug 1023445 might be interesting to measure.

Comment 4

[Boris Zbarsky [:bzbarsky]]

Emilio will basically deal with this once he enable's stylo's code here.

Comment 5

[Boris Zbarsky [:bzbarsky]]

Emilio, you fixed this in stylo, right?

Comment 6

[Emilio Cobos Álvarez (:emilio)]

Kinda. We have optimizations for the kind of thing we use the bloom filter code like having ancestor selectors with class names and such.

We also have a code path where we match right-to-left, but I never managed to make it fast enough so right now it's not enabled.

So the situation is better but a bloom filter would probably still need measuring and could still be useful for the case we have multiple selectors and such.

Comment 7

[Mayank Bansal]

Nightly: 481000
Chrome: 5000