Re: Walking the DOM (was: XML APIs)

keshlam@us.ibm.com writes:

> Depends on what we mean by "take into account". If it can be expressed as
> just one localized test -- "Has the iterator's reference/current node been
> altered/relocated since we last looked at it", exact definition still to be
> hammered out -- the iterator's structure, whether recursive or iterative,
> need not change beyond throwing an exception if that test fails. That
> shouldn't interfere with a compiler's ability to recognize and unwind
> tail-recursion.
>
> Doing this test efficiently is a trifle ugly -- you get into questions of
> how much should be computed locally and how much should be flags set when
> the tree was actually altered -- but I don't think I agree with your flat
> assertion that it can't be done.

I don't think you can make the test local if there are multiple iterators
present, though it may be just barely possible if you use timestamps.  In
any case you might be able to make it local for one or the other of
iterators and structure-modifiers, but certainly not both.  One or the other
is going to have to do some tree-walking, which moves the complexity from
O(1) to at best O(log N), while also imposing a non-trivial penalty on even
the O(1) operation.
 
> >I believe it is also essential that DOM implementations make structural
> >_modification_ methods fast
> 
> In principle I agree, but in practice this depends on what the
> implementation is being used for. We may wind up with implementations tuned
> for various points on various axes (speed if read-only, speed when edited,
> speed when edited but with NodeList not a concern; code size, model size,
> gods know what) competing against each other in the marketplace. That is
> not necessarily a bad thing.

I'm sure we will.  Unfortunately, the spec with its present wording
_precludes_ a large portion of the available implementation space.  My main
concern is with ensuring that Level 2 makes the available implementation
space larger rather than smaller, by relaxing existing Level-1 requirements
rather than creating new (non-optional) ones.  Structurally-aware iterators,
for example, would exclude an even larger portion of the space.

>                            The spec makes no performance promises; that's
> left to quality-of-implementation... and quality is defined by how well an
> implementation meets the needs of each individual user.

On the contrary, the spec makes a performance ``promise,'' namely that the
performance is required to be _significantly_ worse than the performance of
an implementation of the raw interfaces without the additional requirements.
Actually that's not a promise, it's a threat.

If the non-structural requirements like live nodelists and structurally-
aware iterators were specified as optional or implementation dependent,
_then_ the spec would be making no performance promises and I would be free
to adopt an implementation that optimized the variables I'm concerned
about. 

> If you can't find an implementation that meets your needs, you may have to
> write a better one. If you can't do that either, you may in fact find
> yourself forced to abandon the DOM.

I have _already_ abandoned it, in the sense that there is no way my
application can be made to work efficiently if my implementation slavishly
follows the behavioral parts of the spec.  It can, and does (or rather I
expect it to after I've done updating it, which is a rather low-priority
item), implement the interfaces.  

>                                      No silver bullets, folks; the DOM is
> just one solution, and I expect that sometimes the needs of a particular
> application _will_ dominate over interoperability and the DOM will
> occasionally lose the race. But If it's only adopted in 90% of the
> potential applications, that's still a big win.

My personal guess is closer to 10%.  Maybe even 1%.  Maybe even just
Netscape and MSIE.  My guess is that the performance and size overheads to
support live nodelists efficiently are _huge_, and that most savvy
implementors would be unwilling to pay that price.  Bear in mind that the
DOM's interfaces without liveness, etc. are very simple, so a programmer can
easily justify making an efficient, customized implementation over
downloading (let alone paying for) a significantly less-efficient generic
one.

There's also the fact that a locally-developed, simple implementation is
going to be easier to maintain than a third-party, complex one.

-- 
 Stephen R. Savitzky   Chief Software Scientist, Ricoh Silicon Valley, Inc., 
<steve@rsv.ricoh.com>                            California Research Center
 voice: 650.496.5710   fax: 650.854.8740    URL: http://rsv.ricoh.com/~steve/
  home: <steve@starport.com> URL: http://www.starport.com/people/steve/

Received on Tuesday, 3 November 1998 17:49:30 UTC