Re: [Element Traversal LC] access to element by index

Henri Sivonen wrote:
> 
> On Apr 2, 2008, at 13:20, Jonas Sicking wrote:
>> Henri Sivonen wrote:
>>> On Apr 2, 2008, at 12:44, Jonas Sicking wrote:
>>>>> And to what end? To use indexing instead of list-style iteration.
>>>>
>>>> Exactly. Something that I would imagine is quite commonly done. Note 
>>>> that we're not just talking iterating over a full DOM tree, we're 
>>>> also talking about navigating around in a DOM tree from one known 
>>>> specific node to another.
>>> It seems to me that allowing indexed access to children creates a 
>>> similar kind of problem that allowing indexed access to strings by 
>>> UTF-16 code unit has created. Allowing app code to index into 
>>> platform structures that are most commonly forward-iterated seems 
>>> like an anti-pattern in terms of what implementation constraints are 
>>> placed if the impression that the app developer gets is that indexing 
>>> has the performance properties of array access and that it is OK to 
>>> write app code with that assumption.
>>
>> What makes you think that most users of the DOM-tree does 
>> forward-iteration? This is not my experience with the code I've seen. 
>> Rather it has been trying to get to specific nodes within a tree.
> 
> If one wants a specific node, why not put an id on it and use 
> getElementById?

It can be a pain to add IDs to *all* the nodes you ever access. A 
pattern i've seen a lot is to have small repeating sections in a page, 
and then navigating within that repeated section. For example a shopping 
cart list where you'd want to navigate from the 'add item' button to the 
'number of items' field in the same row.

The most recent example of this that I touched was the code dealing with 
customizing toolbars in the firefox chrome where each button was built 
up using a small set of DOM nodes and we wanted to mutate each set of 
nodes in the same way in order to turn on and off customization. This 
resulted in code that iterated over each button and then for each button 
did a trivial navigation within that buttons DOM tree.

> Knowing that you want the fifth element child of another 
> element requires a priori knowledge of the document tree shape anyway. 

Seems like most of the time the same person is writing the markup and 
the DOM-walking code so this doesn't seem like an evil requirement.

> That said, I don't think there's a problem with having a 
> getChildElementByIndexThisIsNotGuaranteedToBeArrayAccess() if you really 
> want to get the nth element child only instead of iterating with an index.

Sure, as long as we also add 
.firstElementChildThisIsNotGuaranteedToBePropertyAccess ;)

>> The same argument can be made for .nextElementSibling, why give 
>> forward-iterating access into platform structures that are most 
>> commonly index-accessed?
> 
> Indeed the argument I made should lead to iterator objects instead of 
> either item(n) or nextSibling.
> 
> I think one of the major design flaws of the DOM is that it gives two 
> views to the tree without specifying the performance characteristics of 
> those views. App developers who like linked lists may reasonable assume 
> that nextSibling is a mere pointer dereference. App developers who like 
> arrays may reasonably assume that item(n) is a mere array access. Now 
> DOM implementations are damned either way and have to do tricks to make 
> the non-native view fast as well.

Honestly, is this really a big problem? It used to be that iterating a 
child list using .nextSibling was O(N^2). We fixed this in firefox 3 to 
make it O(N) most of the time, the implementation uses inexact caching 
which is why it's just most of the time. However we never heard a lot of 
people complaining about the O(N^2), nor did we see a noticeable 
performance win when we fixed it.

It's entirely possible to at least in most cases get approximately array 
access speed for .item(x) and property access speed for .nextX no matter 
how you internally store things. As demonstrated by webkit and gecko 
respectively.

/ Jonas

Received on Wednesday, 2 April 2008 12:10:35 UTC