W3C home > Mailing lists > Public > www-dom@w3.org > October to December 1998

RE: An observation about "live" NodeLists

From: Miles Sabin <msabin@cromwellmedia.co.uk>
Date: Mon, 19 Oct 1998 18:25:40 +0100
Message-ID: <c=US%a=_%p=Cromwell_Media%l=ODIN-981019172540Z-24187@odin.cromwellmedia.co.uk>
To: "'Ray Whitmer'" <ray@imall.com>, "'DOM list'" <www-dom@w3.org>
Ray Whitmer wrote,
> Any implementation which:
> 
> 1.  Caches seen items in the NodeList in something indexable 
>     like an array.
> 2.  Has a simple hierarchical comparison function that given 
>     two nodes can check their traversal order.
> 
> can do a simple binary search on the cached items of the 
> nodelist and remove any nodes that fall in the range being
> removed.

> On the other hand, any implementation which:
> 
> 1.  Caches a single node with an index.
> 2.  Has a simple hierarchical comparison function that given 
>     two nodes can check their traversal order.
> 
> can quickly identify removed nodes which require the index of 
> the cached node to be modified.

> Even cases where the current or single node is removed, it is 
> not difficult to store a nearby neighbor as the place where
> searching is to resume for the removed index. Thus the
> remove(list.item(0)) loop can be quite efficient.

Perhaps, perhaps not.

The trouble with your suggestion is that it seems to require
that every active NodeList on a given subtree (maybe all active
NodeLists over the whole tree?) has to be visited each time that
subtree is modified. This means that we have an extra multiplier:
the number of active NodeLists. Now, how many of those are there?
How long is a piece of string? In Java, at least, this is a
serious issue, because the vagaries of GC make it impossible
to tell particularly early whether or not a NodeList is in use.

Implementations which keep an edit count at each Node have
an advantage here, in that they *don't* have to visit each
NodeList (the same would apply for iterators). The performance
issue now boils down to: is the number of active NodeLists
likely to be sufficiently large to outweigh the kind of
gains you describe.

Bizzarely it looks as though the very efficiency that the
strategy you describe provides will be self-defeating: the
faster NodeLists are the more tempting it is to use 'em;
but the more you use 'em, the slower they get.

None of us have any way of knowing a general answer to that
question, because it depends on how the DOM is used.

Cheers,


Miles
Received on Monday, 19 October 1998 13:31:17 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Friday, 22 June 2012 06:13:45 GMT