W3C home > Mailing lists > Public > public-webapps@w3.org > January to March 2009

Re: Selectors API

From: Boris Zbarsky <bzbarsky@MIT.EDU>
Date: Tue, 24 Mar 2009 10:25:10 -0400
Message-ID: <49C8ED46.5020903@mit.edu>
To: Maciej Stachowiak <mjs@apple.com>
CC: Anne van Kesteren <annevk@opera.com>, WebApps WG <public-webapps@w3.org>
Maciej Stachowiak wrote:
> 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.

Yes, they would be.  The question is how much, and how often one 
iterates the whole list as opposed to just part of the list.

> 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.

For what it's worth, this specific use case has more or less O(N) 
behavior in Gecko (there is in fact an O(N^2) term with a very very 
small constant, but for most reasonable N (order of 10^4 or so) the O(N) 
terms dominate, I think).

One can experiment with this if desired by iterating document.anchors 
and removing href attributes, which is exactly the scenario above.

> 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, though, is a very good point.  The set of mutations that could 
affect the list would indeed be much larger here than in most cases, and 
detection of when the list needs updating would be much more 
complicated...  So the implementation might not in fact be any simpler.

-Boris
Received on Tuesday, 24 March 2009 14:26:17 GMT

This archive was generated by hypermail 2.3.1 : Tuesday, 26 March 2013 18:49:30 GMT