Optimizing large selector sets

CSS selectors are to frontend development as SQL statements are to the backend. Aside from their origin in CSS, we use them all over our JavaScript. Importantly, selectors are declarative, which makes them prime candidates for optimizations.

Browsers have a number of ways of dealing with parsing, processing, and matching large numbers of CSS selectors. Modern web apps are now using thousands of selectors in their stylesheets. In order to calculate the styles of a single element, a huge number of CSS rules need to be considered. Browsers don’t just iterate over every selector and test it. That would be way too slow.

Most browsers implement some kind of grouping data structure to sort out obvious rules that would not match. In WebKit, it’s called a RuleSet.

SelectorSet

SelectorSet is a JavaScript implementation of group technique browsers are already using. If you have a set of selectors known upfront, it makes matching and querying elements against that set of selectors much more efficient.

Selectors added to the set are quickly analyzed and indexed under a key. This key is derived from a significant part of the right most side of the selector. If the selector targets an id, the id name is used as the key. If there’s a class, the class name is used and so forth. The selector is then put into a map indexed by this key. Looking up the key is constant time.

When it’s time to match the element against the group, the element’s properties are examined for possible keys. These keys are then looked up in the mapping which returns a smaller set of selectors which then perform a full matches test against the element.

Speeding up document delegated events

jQuery’s original $.fn.live function (and its modern form, $.fn.on) are probably the most well known delegation APIs. The main advantage of using the delegated event handler over a directly bound one is that new elements added after DOMContentLoaded will trigger the handler. A technique like this is essential when using a pattern such as pjax, where the entire page never fully reloads.

Extensive usage of document delegated event handlers is considered controversial. This includes applications with a large number of $(‘.foo’).live(‘click’) or $(document).on(‘click’, ‘.foo’) registrations. The common performance argument is that the selector has to be matched against entire ancestor chain of the event target. On an application with large and deeply nested DOM, like github.com, this could be as deep as 15 elements. However, this is likely not the most significant factor. It is when the number of delegated selectors themselves is large. GitHub has 100+ and Basecamp has 300+ document delegated events.

Using the selector set technique described above, installing this jQuery patch could massively speed up your apps event dispatch. Here’s a fun little jsPerf test using real GitHub selectors and markup to demonstrate how much faster the patched jQuery is.

Conclusion

Both of these libraries should be unnecessary and hopefully obsoleted by browsers someday. Browsers already implement techniques like this to process CSS styles efficiently. It’s still unfortunate we have no native implementation of declarative event handlers, even though people have been doing this since 2006.

References

• https://github.com/josh/selector-set
• https://github.com/josh/jquery-selector-set

Written by

Joshua Peek

@josh