Pavel Panchekha

By

Share under CC-BY-SA.

Selector Matching is Quadratic

I previously posted asking what the algorithmic complexity of selector matching is. I've learned a lot about browsers in the two years since, so this post contains an answer and also further thoughts.

Quadratic Selector Matching

Selector matching is quadratic when you have \(O(n)\) elements which each need to walk up the node tree \(O(n)\) steps to test whether a selector matches. There are a lot of caches and filters to speed this process up, so to make sure it's slow across all extant browsers, we need to do something particular. So, create a deeply nested web page, like this: 

<body>
<script defer>
let the_elt = document.body
for (let i = 0; i < 1_000; i++) {
  let new_elt = document.createElement("div");
  the_elt.appendChild(new_elt);
  the_elt = new_elt;
}
</script>

This creates 1,000 nested <div> elements. Be careful: nest these too deep and most browsers crash. Now, we need to style these elements. The selector has to require a long walk up, and it also has to be use tags that actually do exist in the browser to avoid triggering the Bloom filter optimization or the cache optimization. So this works: 

<!doctype html>
<style>
div body div { color: blue; }
</style>

This triggers quadratic behavior in Chrome and Firefox. In Safari, thanks to CSSJIT, style recomputation is already very fast and it's hard to know if it's quadratic or not. At a high level, this is quadratic because for each <div> element, we attempt to match this one rule, and for each one, we need to walk past \(O(n)\) other <div> elements to get to the <body> element, at which point a few more steps confirm that that <body> is not inside a <div> and thus that the selector doesn't match.

So that's the answer to the question of asymptotic complexity.

What matters in selector matching?

In my previous post I had a bunch of thoughts on how to guarantee \(O(n r)\) runtime, which was optimal in the sense that a page may well have \(O(n r)\) selector matches and thus this was kind of like \(O(1)\) time per match. But over the last two years I have understood that the biggest factor this was missing was sparsity. The vast majority of rules don't match the vast majority of elements, so that the overall number of matches is more like \(O(n + r)\) than \(O(n r)\). Handling this sparsity by rapidly filtering out useless rules is most of what browsers' existing optimizations do, and any algorithmic approach has to think about this.

Invalidation is also essential, but not in the way I thought. Optimal invalidation would, of course, be very attractive, but the state of the art in selector invalidation is still somewhat primitive compared to, say, layout invalidation. I'm not sure why this is, but Chrome's invalidation sets and Firefox's diffing approach (curiously, kind of philosophically opposite from their layout invalidation philosophy) are not particularly close to optimal, and that seems to be OK. On the other hand, Webkit demonstrates that JIT-compiling selector matching and reducing overhead works super well, and that if the overhead of from-scratch computation is low enough then you probably don't have to worry much about invalidation.

Finally, extending that thought, low memory and time overheads matter a lot, and tricks like Bloom filters make a big impact on how fast and efficiently selector matching can happen.