Computational complexity of CSS

(I did not find discussion of this subject on the Net 
so my pardon if it was already discussed)

Let's imagine that we have document with N elements
and style sheet with M styles defined. 

Resolving all styles for all elements is a task 
with computational complexity[1] defined as O(N*M).
Such complexity reflects the nature of CSS, selectors
in particular.

Such complexity is generally not good - 
1000 elements with 1000 styles is 1,000,000 checks
"does this selector match this element or not?"

Even you have defined only 10 of styles for your document 
UA adds its own styles from intrinsic(default) style table.
(status of this intrinsic style table is also interesting thing, btw)

This property of CSS is a problem in some situations.

For example I have a stress test where <select>
contains 10,000 <option>s and each option
contains <table> inside.

If let's say in style sheet we have something like this:

  select > option { background-color: color1... }
  select:focus > option { background-color: color2 ... }

(weird but happens)

then on focus-out event UA must resolve (find and inherit) 
styles for all 10,000 items-elements (and their children) of the list.
This is serious task for modern hardware. 

Is anybody looking in this direction or you think 
this problem is a bit artificial?

Andrew Fedoniouk.
http://terrainformatica.com




[1] http://en.wikipedia.org/wiki/Computational_complexity_theory

Received on Wednesday, 16 November 2005 05:00:16 UTC