CSS, selectors and computational complexity

CSS (Cascading style sheets) has pretty extensive set of so called selectors. Example:

ul[type="1"] > li
{
  list-style-type: decimal;
}

Selector here means the following: each li element that is immediate child of ul that has attribute type with the value "1" has that style.

Selectors and assosiated styles constitute static system of styles. And so they obey following rule (the law of CSS selectors):

At any given moment of time all elements in the DOM that satisfy set of selectors have corresponding styles applied.

Such static nature of CSS selectors establish some obvious (and not so) limitations on what could be done with selectors and what types of selectors CSS can support. For example:

  • Selectors cannot use information defined by styles. Imagine hypothetical selector and style:
    div:visible { visibility:hidden; }
    

    Such pseudo-class always fails and so breaks the rule defined above. There is simply no such moment of time when the rule above is valid.

  • Selectors can use only those features/characteristics of the DOM that can be evaluated at constant (or near) time. Otherwise observer will be able to catch moment of time when the rule will not be true.
    • Consequence of this: selectors that require scan of number of elements of the DOM unknown upfront ( have complexity O(n) in other words ) are "persons non grata" in CSS.

There is nothing wrong in principle with O(n) complexity. At the end resolution of all styles of the DOM that has n number of elements is O(n). The problem arises when you use selectors that each has O(n) complexity. Total complexity in this case will be O(n*n) and that is the cause of troubles.  In case of frequent dynamic updates each such update may require re-computation of all styles of all elements so web page may easily become non-responsive – CPU will be busy resolving styles without doing any good to the user.

Imagine that we have selector like:

ul:not-exist(a:hover) {color:red;}

where :not-exist(…) is true when DOM does not contain element in brackets.

Computation of such pseudo-class is a task of complexity O(n) where n is a number of elements in the DOM.

No one of currently supported selectors in CSS selector module (http://www.w3.org/TR/css3-selectors/) have complexity of O(n). But there are selectors like : only-of-type pseudo-class that are "not good" as in some conditions their computation are as complex as O(n).

Next article will explain what could be done in CSS to overcome complexity problem and still be able to accomplish tasks like ul:not-exist(a:hover) {color:red;}

Some numbers if you wish:

Let’s assume that we have

  1. DOM with 1000 elements and
  2. single selector that has complexity  O(n) that requre 1 microsecond for computation.

Total time requred for the DOM to get its styles will be:

1000 * 1000 * 1μS = 1000000 μS = 1 S (one second)

Lets double number of elements in the DOM so we will get:

2000 * 2000 * 1μS = 4000000 μS = 4 S.

So by simply doubling number of elements we’ve increased time needed by four.

In real time scenario (on complex sites) it will easily make such sites too heavy to deal with.

3 Replies to “CSS, selectors and computational complexity”

  1. Nice one … Made me think of the following.
    What makes applying CSS to DOM , *much* more complicated is (optional) existence of the ‘style’ attribute. Conceptually I think I see no reason of its existence? It makes the whole CSS + DOM (already complex) rules issue NON cocnsistent and introduces singulartities which is bad. Or should I say BAD. Also. It is not possible to use selectors inside the style attribute value. Why should we have this, one might ask?
    First I can think of, is unability to use pseudo class in the value of style. Example :

    <div style=’hover:color:red;link:color:green;’ ></div>

    Of course this does not work. Selectors inside style values are not permited.

    Of course, why in the first place anyone would use the ‘style’ attr, I can not comprehend. It is much more clear and easier to develop and manage CSS through element and selectors, classes and id’s.

    Dusan

  2. Ah? I typed < and > in the post above literally and thus no example has appeared. Ok maybe “BlackNote+WordPress” should transform them into escaped form automagically, maybe not. In any case the example is:

    <div style=’hove:color:red;link:color:ggreen;’ ></div>

    Dusan

  3. Inline styles are needed for WYSIWYG editors.
    While in WYSIWYG environment user have no concept of the CSS (and the DOM either).
    You have just something like <combobox id="list-of-fonts">...</combobox> in the UI. I am trying to eliminate the need of inline styles in <richtext> input element (WYSIWYG editor) though.

Comments are closed.