The default bug view has changed. See this FAQ.

stylo: Gecko selector matching overhead scales better with the number of rules than Servo's

Assigned to



CSS Parsing and Computation
2 days ago
a day ago


(Reporter: bholley, Assigned: bholley)


(Blocks: 1 bug)

Firefox Tracking Flags

(Not tracked)



(2 attachments)

While profiling the testcase in bug 1331848, I created a version of the primary stylesheet that just |cat|s the original stylesheet together 100 times. I did this in order to dig deeper into CSS parsing performance, but noticed an interesting difference in selector matching performance characteristics between Gecko and Stylo.

Using Stylo (sequential mode):
* Original stylesheet: 21ms in matches_complex_selector:
* duplicated-100x stylesheet: 1317 ms in matches_complex_selector :

Using Gecko:
* Original stylesheet: 20ms in ResolveStyleFor:
* duplicated-100x stylesheet: 190ms in ResolveStyleFor:

So Servo's style system scales roughly linearly with the number of selectors to match (which is what I'd expect), whereas Gecko's scales sub-linearly.

We should figure out what Gecko's secret sauce is here and copy it.
Boris, how does Gecko manage to achieve logarithmic performance characteristics here?
Flags: needinfo?(bzbarsky)
Or rather, any idea how? I can also dig into this when I get cycles.
Created attachment 8849218 [details]

original (non-duplicated) stylesheet.
Created attachment 8849219 [details]

It looks to me like servo is spending a lot more time in selector matching as a fraction of the profile than Gecko.  So my first hunch is that we're not rejecting as many things as we could based on rulehash bits or something.

I did measure how many rules get examined by get_matching_rules in servo during this restyle (i.e. the length of self.other_rules), and compared to the length of mUniversalRules at and the two seem to be the same: 309.

On the servo side, for the cases when we have 309 rules there we _seem_ to pretty consistently miss the bloom filter for 3 of them, but hit for everything else, so should reject quite rapidly.  Given that, I don't know why we're spending so much time under matches_complex_selector_internal.

That said, when I just disabled all the iframes on that page, I no longer see the "309 rules" list, so I dunno what's going on _there_.  :(
Flags: needinfo?(bzbarsky)
This bug could seriously benefit from some testcase reduction (e.g. to strip out all the irrelevant stylesheets, at the very least).  That would make it much simpler to measure various stuff relevant to the matching of this particular sheet...
One thing worth checking is how long it takes for the bloom filter to reject a rule.  At first glance, Servo's filter may be rehashing things every time, where Gecko precomputes some hashes once.
Regarding the bloom filter, we were hashing all the time with fnv the precomputed hash. This is not too bad I think, but can be better.

I opened to make it better.
You need to log in before you can comment on or make changes to this bug.