consider using bloom filter in querySelectorAll()

ASSIGNED
Assigned to

Status

()

P3
normal
ASSIGNED
4 years ago
4 months ago

People

(Reporter: bkelly, Assigned: bzbarsky)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

4 years ago
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
(Reporter)

Comment 1

4 years ago
Spam Boris's request queue as requested. :-)
Flags: needinfo?(bzbarsky)
(Assignee)

Comment 2

4 years ago
Created attachment 8444969 [details]
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.
(Assignee)

Comment 3

4 years ago
Another note to self: The steps in bug 1023445 might be interesting to measure.
(Assignee)

Updated

a year ago
Depends on: 1410624
(Assignee)

Comment 4

10 months ago
Emilio will basically deal with this once he enable's stylo's code here.
Flags: needinfo?(bzbarsky)

Updated

4 months ago
Priority: -- → P3
You need to log in before you can comment on or make changes to this bug.