Re: CSS Selector Complexity : Working draft document

Francois Remy wrote:
> It's not the good way to do the things to do it "revertly", I think.

Thing is, in practice what you have in the common case is a static list 
of CSS rules and a stream of elements coming in as you parse the 
document.  For each element you need to figure out what styles apply.

> SAMPLE 1 :
> =================================
> 
> Consider "span *" and this document :
[snipped]
> If we do it revertly, we must check 9 elements (the whole tree) because 
> all can match "*".

Indeed.  How does the other approach perform in a world where you append 
the nodes one at a time and need to lay the document in between the appends?

I should also note that counting the number of "checks" is not 
necessarily the right thing to be worrying about.  As a data point, on 
somewhat modern hardware (Core Duo based laptop a few years old) the 
time it takes to make 250 calls from JS into C++, with each call walking 
a DOM with 251 elements in it and performing such a "check" for each 
element is about 30ms (on a newer laptop it's more like 18ms).  That 
gives us a hard upper bound of 0.5 microseconds per check on the older 
laptop.  That's for a selector with no combinators, of course.  If you 
have combinators that takes more work.  Your original document here 
requires 29 such simple selector checks in all.

> After that, with all childs, we must check each parent until we reach 
> HTML to see if there's a SPAN element.

Right.

> If we do it as I think, we must find a SPAN element (it's easy because 
> most browsers are maintaining a TAG dictionnary that contains each 
> element of the document grouped by tagName)

Actually, no.  They're not, that I know of.  Certainly Gecko isn't.  But 
more importantly, we're not asking "which nodes does this selector 
match" but "which rules apply to this node"?  We already have the node 
we're interested in.

> How does Gecko to be quicker than a browser that use the "logical" order 
> to find matched elements ?

Because we're asking a question that seems to be the inverse of the one 
that the "logical" order is optimal for.

> Can developers of IE, Safari and Opera say if they are using the logical 
> of the reverted way ?

The relevant trunk webkit code is at 
<http://trac.webkit.org/browser/trunk/WebCore/css/CSSStyleSelector.cpp#L1446>. 
  Looks to me like it uses what you call the "reverted" way.

> It's very useful for later discussion. IE probably uses the logical way 
> since it provides querySelector.

Gecko provides querySelector too, as does webkit.  We just walk the DOM 
and for each element see whether it matches the selector (reusing the 
code that's optimized for style resolution).  I suspect webkit does the 
same.  It's not as fast as it could be if we used the "logical" way 
here, probably, but it's fast enough, since each simple selector check 
is very fast.

-Boris

Received on Thursday, 31 July 2008 23:40:14 UTC