Part 2 · 5 chapters · ~35 min

CSSOM Algorithms

Three algorithmic choices make style resolution linear: bucket rules by their rightmost compound, match right to left so the first test rejects almost everything, and keep a bloom filter of ancestors so most walks never start. This part is those three, the cascade as a sort with style sharing on top, invalidation sets as the set algebra that decides what to restyle on a change, and how to measure all of it.

15

Selector matching, right to left

the question

"5,000 elements, 300 rules. Does the browser test every rule against every element on every change?"

It tests far fewer than that, because of two algorithmic choices: rules are bucketed by their rightmost compound so that an element only sees rules that could match its own tag, id, classes or attributes; and selectors are matched right to left so that the rightmost compound (tested in O(1)) rejects almost every candidate before any ancestor walk. The result is work roughly linear in the number of elements, with the walk reserved for the few (element, rule) pairs that pass the first test.

the algorithm per element
  1. Collect candidate rules from the buckets for this element's id, each of its classes, its tag, its attribute names, and the universal bucket. Rules are stored in the buckets in source order with their specificity precomputed (the JS course's tiny browser has the parser; the browser course part 3 the pipeline).
  2. For each candidate, test the rightmost compound against the element: tag compare, class membership (a small list or a bitset per element), id compare, attribute lookup, pseudo-class state (:hover, :nth-child, which requires sibling counting). Most fail here.
  3. For survivors, walk the combinators leftward: descendant (any ancestor matching the next compound; keep walking up on failure), child (exactly the parent), next sibling (exactly the previous element sibling), subsequent sibling (any earlier sibling). Each step is a compound test on another element.
  4. Collect the matched declarations with their rule's specificity and order for the cascade sort.
complexity, and what moves it
  1. Per element: O(candidate rules) rightmost tests + O(survivors × depth) walks. With good buckets, candidates are a handful; survivors are fewer.
  2. Universal and tag-only rightmost compounds (.sidebar *, .table div) land in big buckets and pass the first test often, so they trigger walks on many elements. The old advice "do not end a selector with *" is correct for this reason and only this reason.
  3. :nth-child, :nth-of-type, :last-child: require counting siblings; engines cache sibling indices per parent and invalidate on DOM mutation. O(1) amortised, O(siblings) after a mutation.
  4. :has(): inverts direction: the subject is on the left; matching requires searching the subtree for the argument. Engines cache results per element and use feature filters to skip subtrees; still the most expensive selector, by design.
  5. Depth: a 30-deep DOM makes each descendant walk up to 30 steps. The bloom filter (next chapter) skips most walks entirely.
the sizes
A page with 5,000 elements and 300 rules: initial style resolution in a few milliseconds; a class change on a leaf, microseconds; a class change on the root, the cost of the subtree (chapter 3). Rules do not get slow; changes with wide reach do.
RIGHT-TO-LEFT MATCHING
why the last compound is tested first
swipe the figure sideways, or tap expand for full screen
1/6
the selector
The selector: .sidebar nav a.active. Three compounds joined by descendant combinators. The question for each element on the page: does it match? There are 5,000 elements and 300 rules; the engine answers this for every (element, selector) pair that could possibly match.
16

The ancestor bloom filter

Even with right-to-left matching, a descendant selector whose rightmost compound matches still costs an ancestor walk. The engine avoids most of those walks with a bloom filter over the ancestors of the current element, maintained as the style tree walk descends and ascends. One or two bit tests say "those ancestors are definitely not there", and the walk is skipped.

bloom filters, in general
  1. A bit array of m bits and k hash functions. Insert: set the k bits for the item. Query: are all k bits set? No → definitely absent. Yes → probably present (false positives possible, false negatives impossible).
  2. Cost: O(k) per insert and query; m bits of memory regardless of item count. No deletions in the basic form; a counting variant (a small counter per bit) supports removal, which the style walk needs when it ascends.
  3. False positive rate: about (1 − e^(−kn/m))^k for n items. With m = 4,096 bits, k = 2, and n = 60 features (20 ancestors × 3 features each), the rate is under 0.1%.
in the style engine
  1. Features: the tag, id and classes (and some attributes) of each ancestor, hashed. The hash of an internalised string is precomputed (the JS course part 6), so insertion is a few bit operations per feature.
  2. Maintenance: on entering an element during the depth-first style walk, push its features; on leaving, pop them (decrement counters). The filter always reflects exactly the current ancestor chain.
  3. Use: for a candidate descendant or child selector, before walking up, test each compound's features to the left of the subject against the filter. Any "absent" → skip the walk. All "maybe" → walk and confirm.
  4. What it does not cover: sibling combinators (not ancestors), pseudo-classes that depend on state, and :has() (which looks down; engines use a separate descendant-feature summary for its fast rejection).
the same shape elsewhere in your stack
  1. "Is this key possibly in the cache" before a network or disk lookup (CDNs, databases).
  2. "Is this URL possibly malicious" before a network check (safe browsing's prefix set).
  3. "Is this word possibly in the dictionary" before an expensive lookup (spell checkers).
  4. In a frontend: a bloom filter of seen ids in a feed to cheaply skip duplicates before a Set lookup; a filter of loaded chunk names; anywhere a fast "definitely no" saves a slow check. A Uint32Array and two hashes is twenty lines.
THE ANCESTOR BLOOM FILTER
rejecting descendant selectors without walking up
swipe the figure sideways, or tap expand for full screen
1/6
a bloom filter
A bloom filter: a bit array (here 32 bits; real engines use a few thousand) and k hash functions (here 2). To add an item, set the bits at its k hash positions. To test an item, check its k bits: all set means "maybe present"; any clear means "definitely absent".
17

Cascade resolution as a sort, and style sharing

code
// specificity and the cascade sort, as an algorithm (the browser course part 3 has the mechanism; the tiny browser has code)
// each matched declaration gets a sort key; the highest key wins per property:
//   key = (origin+importance rank, cascade layer order, specificity (a, b, c), source order)
//   compare lexicographically; the last (highest) wins
// specificity: a = #ids, b = .classes + [attrs] + :pseudo-classes, c = tags + ::pseudo-elements. :is()/:not()/:has() take their most specific argument; :where() is 0
// so the sort is: O(k log k) per element for k matched declarations, or O(k) with a counting approach since the key space is small
// what makes it expensive in practice: k. an element matching 40 rules with 10 declarations each sorts 400 keys. keep k small by keeping rules specific to their targets

// computed values: after the winner per property, resolve relative units against the parent (inheritance pass): O(properties) per element
// style sharing: elements with the same tag, classes, attributes, parent style and no :nth-* in play can share the computed style object: the engine checks a small cache
//   first. a list of 1,000 identical <li> computes style once. a list of 1,000 <li style="--i: n"> computes 1,000 times (inline style defeats sharing)
the cascade as an algorithm
  1. Input: for one element, the matched declarations, each tagged with origin (user agent, user, author), importance, cascade layer, specificity (a, b, c), and source order.
  2. Sort key: lexicographic over (origin and importance rank, layer order, specificity, source order). The spec defines the ranks; the tiny browser (browser course part 14) has the eight-line comparator.
  3. Winner per property: the highest key. Engines do not fully sort; they keep the best per property in one pass (O(k)), since only the maximum matters.
  4. Then inheritance and computation: for each property with no winner, the parent's computed value (if inherited) or the initial value; then relative units resolved. O(properties), with properties in the hundreds, so engines store computed styles in shared, copy-on-write groups (font properties, box properties, …) and only materialise the groups a selector touched.
style sharing
  1. The observation: siblings with the same tag, the same classes, the same attributes that selectors care about, the same parent style, and no position-dependent pseudo-classes in play, compute the same style. A list of 1,000 identical items is one computation.
  2. The algorithm: before matching, look in a small cache of recently computed elements for one that is "style-equivalent" (a checklist: tag, classes, ids, inline style absent, attributes used by selectors equal, pseudo-class state equal, parent style pointer equal). On a hit, share the computed style object. On a miss, compute and add to the cache.
  3. What defeats it: inline styles (each element unique), per-element custom properties (style="--i: 3", a common animation trick), ids used in selectors, :nth-child rules in scope, different attribute values that selectors reference.
  4. Why it matters: for lists, tables and repeated components, sharing turns style resolution from O(elements × rules) into O(distinct styles × rules). Breaking it on a 10,000-row table is a measurable regression.
18

Invalidation sets: what to restyle on a change

Resolving style once is a few milliseconds. Resolving it again on every DOM change would be the same few milliseconds per change, which at interaction rates is unacceptable. Invalidation sets answer "which elements could this change affect" with a precomputed summary of the stylesheet, so that most changes restyle a handful of elements.

the precomputation
  1. For each rule, for each compound to the left of a combinator, record the features (classes, ids, tags, attributes) that appear to its right. These are the features an element must have for its style to depend on the left compound's presence on an ancestor (or sibling).
  2. Union per feature: all rules contribute to one set per class, id, tag or attribute. A class that appears in a broad rule (.theme *) gets a set containing "everything" (the wildcard), which degrades to a full subtree restyle.
  3. Kinds of set: descendant (for descendant and child combinators), sibling (for + and ~, with a distance limit), self (the element itself, always), and for :has(), an upward set.
on a change
  1. A class added or removed: look up its sets. Self: mark the element. Descendant set: walk the subtree marking elements with any feature in the set (and stop at contain: style boundaries). Sibling set: walk following siblings likewise.
  2. An attribute change, an id change, a pseudo-class state change (:hover, :focus, :checked): the same mechanism with the corresponding feature; :hover on a deep element invalidates up the chain because :hover matches ancestors too.
  3. DOM insertion: the inserted subtree is styled fresh; siblings are invalidated for sibling selectors and :nth-*; ancestors for :has() and :empty.
  4. Then recalc: only marked elements are re-matched and re-cascaded (chapter 1's algorithm), with style sharing and computed-value diffing to decide what layout needs to know.
designing for small sets
  1. Prefer per-element classes to ancestor switches for things that change often: a .selected on the row, not a .has-selection on the table that selectors descend from.
  2. Keep broad rules static: a theme class on html is fine if it changes once; toggling it per interaction restyles the page.
  3. contain: style on components that are self-contained in their styling stops both the walk and the invalidation from crossing the boundary.
  4. Custom properties change values without changing selector matches: toggling --accent on a root invalidates computed values for elements that use it, not the matching; cheaper than a class switch that changes which rules apply, though still a subtree computed-value pass.
INVALIDATION SETS
which elements to restyle when a class changes, as set algebra
swipe the figure sideways, or tap expand for full screen
1/6
the rules
The stylesheet has, among its rules: .dense .cell { padding: 2px }, .dense td { … }, .theme-dark .btn { … }, .open > .menu { … }. At stylesheet parse time the engine builds, for each class that appears to the left of a combinator, the set of features to its right.
19

Measuring style work

code
// measuring style work
// Performance panel → "Recalculate Style" events: the count of elements affected and (with selector stats enabled) time per selector
// chrome://flags → "CSS selector stats" or Performance → settings → "Enable CSS selector stats": a table of selectors by elapsed time,
//   match attempts, and match count. a selector with many attempts and few matches is a broad rightmost compound
// Rendering → "Style invalidation tracking" (older) / the "Style recalc" details: which change triggered which subtree
// the experiment: toggle a class on the root vs on a leaf, with a 10,000-node subtree; compare Recalculate Style duration and element counts
QuestionToolWhat to read
How long does a style recalc take and how many elements?Performance → Recalculate Style event → summaryElements affected; a big count after a small change means a broad invalidation set
Which selectors are expensive?Performance → settings → CSS selector stats → the tableElapsed time, match attempts, match count; many attempts and few matches is a broad rightmost compound; long elapsed with :has() or :nth-* is the walk
Did style sharing work?Recalculate Style time per element, compared between identical rows with and without inline stylesA 10× difference means sharing was defeated
What did this change invalidate?Performance → the Recalculate Style event's initiator / the "style invalidation" details where availableThe triggering DOM change and the affected subtree
Is :has() the cost?Remove it and re-measure; selector stats:has() is always the most expensive selector in a stylesheet; use it where the alternative is JavaScript, not for convenience
Is containment helping?Toggle contain: style on the boundary; compare element countsThe subtree walk should stop at the boundary
the pointer
Part 3 is layout: the algorithms that turn computed styles into geometry. Block layout is one pass; inline layout is line breaking; flex is three passes; grid is a fixpoint over track sizes. The browser course part 4 drew the pipeline; this one walks the algorithms step by step.