Re: Selectors API

On Mar 23, 2009, at 11:08 PM, Maciej Stachowiak wrote:

>
> On Mar 23, 2009, at 7:30 AM, Boris Zbarsky wrote:
>
>> Anne van Kesteren wrote:
>>>> http://lists.w3.org/Archives/Public/public-webapi/2007Mar/0066.html
>>>> http://lists.w3.org/Archives/Public/public-webapi/2007Apr/0009.html
>>> I read those. That was long after this was initially discussed  
>>> though. And also around the time I stopped being the active editor  
>>> of the specification.
>>
>> Er, indeed.  Those seem to be discussion of ElementTraversal.
>>
>> I was pretty sure I'd raised the same issue with Selectors API, but  
>> the W3C list search is crappy enough that I can't find the  
>> posts...  In fact, the only thread on the matter I can find is the  
>> "ACTION-87: Selectors API" thread (announcing that you plan to  
>> start working on the spec at) at <http://lists.w3.org/Archives/Public/public-webapi/2006Feb/0108.html 
>> >. Was that it?
>>
>> In any case, the static implementation was considerably more  
>> complicated in Gecko, I suspect performance is a wash in most  
>> cases, though it's easy to create examples that are much faster  
>> with one or the other approach.
>
> Live lists will almost certainly be slower in the face of DOM  
> mutation concurrent with iterating the list. I don't know of any  
> reason things would be different in Gecko.
>
> In the case of Selectors API especially, a fairly likely use case is  
> to mutate the DOM while iterating the list - imagine finding all  
> divs with a particular class name, attaching behavior, and then  
> removing the class so that behavior is not accidentally added more  
> than once. This would be terrible for most conceivable live list  
> implementations. Complex selectors (involving indirect adjacent  
> combinators for instance) would make things even worse - even DOM  
> mutations that don't affect the contents of the list may force  
> invalidation of any caches or else a complex calculation to prove  
> they don't change the contents of the list.
>
> This is the reason I originally reported that live lists are likely  
> to be a performance issue for some common uses of this API.

In fact, reading my old post I can see that I already explained the  
perf issues pretty well, including the performance downside of static  
lists, and the idea that you can mitigate this somewhat by a variant  
API that returns only the first match.

I'm still pretty sure you would get O(N^2) behavior in many cases of  
mutating while iterating a live querySelector list, even if live lists  
are easier to implement in Gecko.

Regards,
Maciej

Received on Tuesday, 24 March 2009 06:15:22 UTC