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


Reply via email to