Re: CSS Selector Complexity : Working draft document

From: "Boris Zbarsky" <bzbarsky@MIT.EDU>
Sent: Thursday, July 31, 2008 10:58 PM
To: "Francois Remy" <fremycompany_pub@yahoo.fr>
Cc: "CSS 3 W3C Group" <www-style@w3.org>
Subject: Re: CSS Selector Complexity : Working draft document

> Francois Remy wrote:
>> - Loop Complexity (or static complexity: time needed to find matching 
>> elements at load time)
>
> As I said in my other mail, this is not an interesting metric for a 
> rendering engine (unless you're implementing querySelectorAll).  During 
> load time the question that's asked (repeatedly) is not "which elements 
> match this selector?" but "which selectors match this element, so that I 
> can apply the relevant style rules?"

It's not the good way to do the things to do it "revertly", I think.

SAMPLE 1 :
=================================

Consider "span *" and this document :
- <html>
    - <body>
        - <div>
            - <span>
                - <b>
        - <div>
            - <div>
        - <div>
            - <div>

If we do it revertly, we must check 9 elements (the whole tree) because all 
can match "*".
After that, with all childs, we must check each parent until we reach HTML 
to see if there's a SPAN element.
>>> If I don't make an error, we have 26 checking steps (all parents of all 
>>> elements except for B that have a SPAN parent before the end).

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) and check all childs of the matching SPAN 
element.
>>> We have here only 2 checking steps (SPAN and B)

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

SAMPLE 2 :
=================================
The only one selector I found that can give the advantage to this way to 
find the elements is : " * * ".

On the same document as before :
>>> Logical way : 31 elements checked
>>> Reverted way : 17 elements checked

But it's more usual to have a selector of first type than of second type, I 
think.
But I understand now what you were saying, it's more important that such 
performance consideration.

REMARKS :
=================================
I've now catched up why you say :matches is a complex pseudo-class.
In a browser that apply the revert way to find matched elements, it's more
complicated than for the others because you must change of direction of the
matching search during the ":matches" operation.

    a b:matches(c) d { ... }

For a browser that use the logical way is very easy to implements, but for a 
browser that implements the revert way, we are coming from D and we must 
return to D each time we encounter a B to see if he have a C as child. It's 
counter productive, in fact.

Can developers of IE, Safari and Opera say if they are using the logical of 
the reverted way ?
It's very useful for later discussion. IE probably uses the logical way 
since it provides querySelector.

>
>> - Update Complexity (number of times the matched elements can be 
>> reevaluated * time it need)
>
> My previous post broke this down in what I think is a more useful way.
>
>>     * I voluntary excluded the optimizations that can be done by the UA 
>> because they are probably not the same
>
> But the space of possible optimizations is in fact key...  The question is 
> always what the fastest smallest way is to implement something.
>
> -Boris

Received on Thursday, 31 July 2008 22:01:09 UTC