W3C home > Mailing lists > Public > www-style@w3.org > November 2005

Re: Computational complexity of CSS

From: David Hyatt <hyatt@apple.com>
Date: Wed, 16 Nov 2005 14:36:21 -0800
Message-Id: <27D0E2CA-8115-4B72-8E58-3A54C108B571@apple.com>
To: Andrew Fedoniouk <news@terrainformatica.com>, W3C CSS <www-style@w3.org>

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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 27 April 2009 13:54:41 GMT