Chapter 6 - Faster CSS Rule Matching

[Tim-Liam-Hill]

I have been thoroughly enjoying following this textbook and have been challenging myself to expand on what is given where possible (for example, I expanded on the given HTML parser to handle more HTML examples).

I am currently in the middle of a CSSParser rework to better handle more complex stylesheets and was wondering what techniques are used by modern browsers to allow for faster CSS rule matching. That is to say: at present Chapter 6 results in a list of CSS rules that we iterate through for every single node to look for matches. For longer stylesheets with a lot of class rules this would be slow (and per my experience in web dev this seems to be a common approach).

One thought I have is to better group selectors together. That is to say: we can put all class selectors in a specific group of rules, all tag selectors in a specific group of rules etc. That way if a node doesn't have a class attribute we can skip iterating through that group of rules altogether.

The next idea is to use hashing within these groups. If my tag is 'd'iv then I should be able to immediately access all 'div' related rules in a dict.

These are fairly basic ideas so an further input is appreciated. I imagine there is some cool trickery with bloom filters, trees and other datastructures that modern browsers use.

[pavpanchekha]

Hi Tim! There's a bunch of optimizations real browsers provide; a couple of sources I recommend looking at are:

• Nolan Lawson's talk: https://www.youtube.com/watch?v=nWcexTnvIKI
• The Stylo blog post: https://hacks.mozilla.org/2017/08/inside-a-super-fast-css-engine-quantum-css-aka-stylo/
• Andreas Kling's Ladybird videos include one on the class cache: https://www.youtube.com/watch?v=khJ_VNfh0fU

But to give you a direct answer, some optimizations I think are shared by all browsers include:

• A class cache, where rules are grouped by class, tag name, etc from the rightmost selector, and only the ones that could match are tested.
• Ancestor bloom filters for fast-rejecting descendant selectors and I think now descendant bloom filters for :has selectors.
• Style sharing, where "similar" elements, appropriately determined, skip matching entirely since they match the same rules

Some differences between browsers include:

• Webkit has a "CSS JIT", which compiles the matching loop to machine code. Chrome, I believe, also explored this but decided against. It really does make CSS matching much faster, but it's still using the same basic optimizations, just compiled instead of interpreted.
• For invalidation, Chrome uses a nice "invalidation set" system. Firefox uses, to my mind, a much grungier system that involves diffing stuff. I'm not aware of what Webkit does, maybe CSS JIT is fast enough that they don't invalidate.
• Firefox's Stylo uses work-stealing multithreading

I am most familiar with Firefox's matching engine (Stylo) and tend to think it has the nicest code, but I'm sure this is more familiarity than anything. The Chrome source code has great documentation internally (just search the codebase for *.md) that's very worth reading.

[Tim-Liam-Hill]

Thanks for the insights! I should have realised that Andreas would have a relevant video.

The more and more I look into it, the more I realise that the CSS standard is monstrous to implement completely, let alone completely and efficiently. For now I think I'll settle for the basic tags and a couple of combinators.

Thanks again!