Choosing Efficient Selectors Based on Computational Complexity

Choosing efficient selectors based on computational complexity

At runtime an HTML document is parsed into a DOM tree containing N elements with an average depth D. There is also a total of S CSS rules in the stylesheets applied.

Elements' styles are applied individually meaning there is a direct relationship between N and overall complexity. Worth noting, this can be somewhat offset by browser logic such as reference caching and recycling styles from identical elements. For instance, the following list items will have the same CSS properties applied (assuming no pseudo-classes such as :nth-child are applied):
```
<ul class="sample">
  <li>one</li>
  <li>two</li>
  <li>three</li>
</ul>
```
Selectors are matched right-to-left for individual rule eligibility - i.e. if the right-most key does not match a particular element, there is no need to further process the selector and it is discarded. This means that the right-most key should match as few elements as possible. Below, the p descriptor will match more elements including paragraphs outside of target container (which, of course, will not have the rule apply but will still result in more iterations of eligibility checking for that particular selector):
```
.custom-container p {}
.container .custom-paragraph {}
```
Relationship selectors: descendant selector requires for up to D elements to be iterated over. For instance, successfully matching .container .content may only require one step should the elements be in a parent-child relationship, but the DOM tree will need to be traversed all the way up to html before an element can be confirmed a mismatch and the rule safely discarded. This applies to chained descendant selectors as well, with some allowances.
On the other hand, a > child selector, an + adjacent selector or :first-child still require an additional element to be evaluated but only have an implied depth of one and will never require further tree traversal.
The behavior definition of pseudo-elements such as :before and :after implies they are not part of the RTL paradigm. The logic the assumption is that there is no pseudo element per se until a rule instructs for it to be inserted before or after an element's content (which in turn requires extra DOM manipulation but there is no additional computation required to match the selector itself).
I couldn't find any information on pseudo-classes such as :nth-child() or :disabled. Verifying an element state would require additional computation, but from the rule parsing perspective it would only make sense for them to be excluded from RTL processing.

Given these relationships, computational complexity O(N*D*S) should be lowered primarily by minimizing the depth of CSS selectors and addressing point 2 above. This will result in quantifiably stronger improvements when compared to minimizing the number of CSS rules or HTML elements alone^

Shallow, preferably one-level, specific selectors are processed faster. This is taken to a whole new level by Google (programmatically, not by hand!), for instance there is rarely a three-key selector and most of the rules in search results look like

#gb {}
#gbz, #gbg {}
#gbz {}
#gbg {}
#gbs {}
.gbto #gbs {}
#gbx3, #gbx4 {}
#gbx3 {}
#gbx4 {}
/*...*/

^ - while this is true from a rendering engine performance standpoint, there are always additional factors such as traffic overhead and DOM parsing etc.

Sources: 1 2 3 4 5

Which CSS selectors or rules can significantly affect front-end layout / rendering performance in the real world?

The first thing that comes to mind here is: how clever is the rendering engine you're using?

That, generic as it sounds, matters a lot when questioning the efficiency of CSS rendering/selection. For instance, suppose the first rule in your CSS file is:

.class1 {
    /*make elements with "class1" look fancy*/
}

So when a very basic engine sees that (and since this is the first rule), it goes and looks at every element in your DOM, and checks for the existence of class1 in each. Better engines probably map classnames to a list of DOM elements, and use something like a hashtable for efficient lookup.

.class1.class2 {
    /*make elements with both "class1" and "class2" look extra fancy*/
}

Our example "basic engine" would go and revisit each element in DOM looking for both classes. A cleverer engine will compare n('class1') and n('class2') where n(str) is number of elements in DOM with the class str, and takes whichever is minimum; suppose that's class1, then passes on all elements with class1 looking for elements that have class2 as well.

In any case, modern engines are clever (way more clever than the discussed example above), and shiny new processors can do millions (tens of millions) of operations a second. It's quite unlikely that you have millions of elements in your DOM, so the worst-case performance for any selection (O(n)) won't be too bad anyhow.

Update:

To get some actual practical illustrative proof, I've decided to do some tests. First of all, to get an idea about how many DOM elements on average we can see in real-world applications, let's take a look at how many elements some popular sites' webpages have:

Facebook: ~1900 elements (tested on my personal main page).

Google: ~340 elements (tested on the main page, no search results).

Google: ~950 elements (tested on a search result page).

Yahoo!: ~1400 elements (tested on the main page).

Stackoverflow: ~680 elements (tested on a question page).

AOL: ~1060 elements (tested on the main page).

Wikipedia: ~6000 elements, 2420 of which aren't spans or anchors (Tested on the Wikipedia article about Glee).

Twitter: ~270 elements (tested on the main page).

Summing those up, we get an average of ~1500 elements. Now it's time to do some testing. For each test, I generated 1500 divs (nested within some other divs for some tests), each with appropriate attributes depending on the test.

The tests

The styles and elements are all generated using PHP. I've uploaded the PHPs I used, and created an index, so that others can test locally: little link.

Results:

Each test is performed 5 times on three browsers (the average time is reported): Firefox 15.0 (A), Chrome 19.0.1084.1 (B), Internet Explorer 8 (C):

                                                                        A      B      C
1500 class selectors (.classname)                                      35ms   100ms  35ms
1500 class selectors, more specific (div.classname)                    36ms   110ms  37ms
1500 class selectors, even more specific (div div.classname)           40ms   115ms  40ms
1500 id selectors (#id)                                                35ms   99ms   35ms
1500 id selectors, more specific (div#id)                              35ms   105ms  38ms
1500 id selectors, even more specific (div div#id)                     40ms   110ms  39ms
1500 class selectors, with attribute (.class[title="ttl"])             45ms   400ms  2000ms
1500 class selectors, more complex attribute (.class[title~="ttl"])    45ms   1050ms 2200ms

Similar experiments:

Apparently other people have carried out similar experiments; this one has some useful statistics as well: little link.

The bottom line:

Unless you care about saving a few milliseconds when rendering (1ms = 0.001s), don't bother give this too much thought. On the other hand, it's good practice to avoid using complex selectors to select large subsets of elements, as that can make some noticeable difference (as we can see from the test results above). All common CSS selectors are reasonably fast in modern browsers.

Suppose you're building a chat page, and you want to style all the messages. You know that each message is in a div which has a title and is nested within a div with a class .chatpage. It is correct to use .chatpage div[title] to select the messages, but it's also bad practice efficiency-wise. It's simpler, more maintainable, and more efficient to give all the messages a class and select them using that class.

The fancy one-liner conclusion:

Anything within the limits of "yeah, this CSS makes sense" is okay.

In which direction do selector engines read, exactly?

However I've read recently that most CSS selector engines read from right to left, in which case wouldn't the first example actually be slower?
Which way to CSS selector engines read in general? Left to right or right to left? And if they generally read right to left could someone please offer me an explanation as to why (I can't see how it makes sense to read right to left in terms of a selector engine)?

Frankly, it's nigh impossible to tell which selector will be slower in a given browser, much less across browsers. Performance tends to fluctuate and be unpredictable, especially at such microscopic scales and with unpredictable document structures. Even if we talk about theoretical performance, it ultimately depends on the implementation.

Having said that, as shown in Boris Zbarsky's answer to this other question and in Guffa's answer to yours, a typical browser (this is currently true of all major layout engines) takes an element and evaluates all the candidate selectors to see which ones it matches, rather than finding a set of elements that match a given selector. This is a subtle but very important difference. Boris offers a technical explanation that's not only incredibly detailed, but also authoritative (as he works on Gecko, the engine used by Firefox), so I highly suggest reading it.

But I thought I should address what seems to be another concern in your question:

As the selector engine would simply find every element with a class of name, and then have to identify which of those were divs?

As well as Patrick McElhaney's comment:

The linked question explains why selectors are read right-to-left in general, so #foo ul.round.fancy li.current is read li.current, ul.round.fancy, #foo, but is it really read right-to-left within each element (.current, li, .fancy, .round, ul, #foo)? Should it be?

I have never implemented CSS, nor have I seen how other browsers implement it. We do know from the answers linked above that browsers use right-to-left matching to walk across combinators within selectors, such as the > combinators in this example:

section > div.second > div.third

If an element isn't a div.third, then there is no point checking if its parent is a div.second whose parent is a section.

However, I don't believe that this right-to-left order drills all the way down to the simple selector level. In other words, I don't believe that browsers use right-to-left evaluation for each part of a simple selector sequence (also known as a compound selector) within the right-to-left evaluation across a series of compound selectors separated by combinators.

For example, consider this contrived and highly exaggerated selector:

div.name[data-foo="bar"]:nth-child(5):hover::after

Now, there's no guarantee a browser will necessarily check these conditions for an element in the following order:

Is the pointer over this element?
Is this element the 5th child of its parent?
Does this element have a data-foo attribute with the value bar?
Does this element have a name class?
Is this a div element?

Nor would this selector, which is functionally identical to the above except with its simple selectors jumbled around, necessarily be evaluated in the following order:

div:hover[data-foo="bar"].name:nth-child(5)::after

Is this element the 5th child of its parent?
Does this element have a name class?
Does this element have a data-foo attribute with the value bar?
Is the pointer over this element?
Is this a div element?

There is simply no reason that such an order would be enforced for performance reasons. In fact, I'd think that performance would be enhanced by picking at certain kinds of simple selectors first, no matter where they are in a sequence. (You'll also notice that the ::after is not accounted for — that's because pseudo-elements are not simple selectors and never even enter into the matching equation.)

For example, it's very well-known that ID selectors are the fastest. Well, Boris says this in the last paragraph of his answer to the linked question:

Note also that there are other optimizations browsers already do to avoid even trying to match rules that definitely won't match. For example, if the rightmost selector has an id and that id doesn't match the element's id, then there will be no attempt to match that selector against that element at all in Gecko: the set of "selectors with IDs" that are attempted comes from a hashtable lookup on the element's ID. So this is 70% of the rules which have a pretty good chance of matching that still don't match after considering just the tag/class/id of the rightmost selector.

In other words, whether you have a selector that looks like this:

div#foo.bar:first-child

Or this:

div.bar:first-child#foo

Gecko will always check the ID and the class first, regardless of where it is positioned in the sequence. If the element doesn't have an ID and a class that matches the selector then it's instantly discarded. Pretty darn quick if you ask me.

That was just Gecko as an example. This may differ between implementations as well (e.g. Gecko and WebKit may do it differently from Trident or even Presto). There are strategies and approaches that are generally agreed upon by vendors, of course (there isn't likely to be a difference in checking IDs first), but the little details may differ.

More CSS, less HTML?

You could calculate the average performance difference caused by the difference in file size as the time it would take to fetch one more TCP/IP package times the probability that it would happen because of that change (i.e. package size divived by the number of characters added).

You might get something like 10 ms * 1/1000, which would give you 10 µs.

That is such a small performance difference that you have to make the same thing a huge number of times before it's noticable.

So, you should use the one that is clearer and easier to maintain.

Personally I would go with the first option. I find it easier to see what's applied to the element if there is a single path to follow from the class names to the rules, rather than having a class scattered across several rules.

What happened to the Use efficient CSS selectors rule?

In Feb 2011, Webkit core developer Antti Koivisto made several improvements to CSS selector performance in Webkit.

Antti Koivisto taught the CSS Style Selector to skip over sibling selectors and faster sorting, which bring some minor improvements, after which he landed two more awesome patches: one which enables ancestor identifier filtering for tree building, halving the remaining time in style matching over a typical page load, and a fast path for simple selectors that speed up matching up another 50% on some websites.

CSS Selector Performance has changed! (For the better) by Nicole Sullivan runs through these improvements in greater detail. In summary -

According to Antti, direct and indirect adjacent combinators can still be slow, however, ancestor filters and rule hashes can lower the impact as those selectors will only rarely be matched. He also says that there is still a lot of room for webkit to optimize pseudo classes and elements, but regardless they are much faster than trying to do the same thing with JavaScript and DOM manipulations. In fact, though there is still room for improvement, he says:
“Used in moderation pretty much everything will perform just fine from the style matching perspective.”

While browsers are much faster at matching CSS selectors, it's worth reiterating that CSS selectors should still be optimised (eg. kept as 'flat' as possible) to reduce file sizes and avoid specificity issues.

What is the Relative Performance of Pseudo-Class and Custom Selectors?

It all comes down to what methods in the DOM the Sizzle engine (which is what jQuery uses to evaluate the selectors) can use to find the elements.

It can use the getElementById and getElementsByTagName methods to quickly get elements for a specific id and for a specific tag name. After that it simply has to loop through all found elements and compare each one to the conditions created from the selector.

The methods in the DOM can be used on any element, and used in combination, so for example finding all div elements inside an element with a specific id is very fast.

Does the number of IDs in a page impact the efficiency of the selectors?

It will be much faster if you avoid using the selector as it requires parsing the DOM as opposed to id's which are pre-stored in a map by most browsers. For example you can access your elements with id through window["elementId"] in chrome. Also don't forget unless you are using ":first" jquery will keep looking in the dom even after finding the first (and only) element.

I would use: $(document.getElementById("elementId")) for the best performance.

But then again I highly doubt your performance issues derive from this, 99% of the time it is excessive dom manipulation or memory leak causing the problems.

jQuery time complexity of $( #id ) selector and $(this).find( #id ). Which one is quicker?

There are lot of examples and measurements on jsPerf about performance counters of different actions. For example this one https://jsperf.com/jquery-find-vs-context-sel/38

Also you can prepare your own scenario and run it in different browsers to check exactly your case, to have measurements for your special case.

Why use in CSS?

It's the direct child, not a recursive match.

CSS

div > p {

}

HTML

<div>
   <p>Match</p>
   <span>
      <p>No match</p>
   </span>
</div>

CSS

div p {

}

Markup

<div>
   <p>Match</p>
   <span>
      <p>Match</p>
   </span>
</div>

Fastest selector method in jquery and CSS - ID or not?

My testing on modern browsers suggests that you should go with either,

$('#id').find('.class') // or
$('.class')

but not,

$('#id .class')

Reason being that all modern browsers implement getElementsByClassName resulting in almost-constant time lookups by class name (assuming a hash implementation). Which browsers are modern is another subjective question.

Choosing Efficient Selectors Based on Computational Complexity