Re: Computational complexity of CSS

Andrew,

Your O(N*M) assertion bears little resemblance to reality.  In  
practice sibling styles (and even cousin styles) can be shared,  
avoiding even the matching or resolution phases.  For typical Web  
pages, this sibling/cousin sharing optimization results in having to  
match styles for only about 30% of the elements in a document.

Moreover, each element need not examine every rule.  Rules can be  
hashed based off what's in their rightmost simple selector sequence.   
Again for typical pages, a given element need only examine a very  
small subset of the actual rules.

With these optimizations CSS scales up quite well, even to a large  
number of rules and elements.

See my blog entry I wrote on this subject a while back:

http://weblogs.mozillazine.org/hyatt/archives/2005_05.html#007507

Cheers,
dave
(hyatt@apple.com)

Received on Wednesday, 16 November 2005 22:36:41 UTC