Performance: firstChild or getElementById?

[Thompson]

Hi, folks :)

Which is more faster, by the viewpoint of processing speed? element.firstChild or getElementById?

if I have only 1 element of each, this should not make difference... but if I have various of them (various children and various diferents IDs), which way is more faster?

A girl that works with me told me that getElementById is a bad choice, because this instruction will make the program run over all elements to discover that who have the selected ID, while the other way (element.firstChild, or just element.something) is faster because it gets the target without run any element of the page.

Is this true? What is really faster?

[Kor]

...but element is to be found as well, so that there will be a search through all the elements as well....

[Beagle]

To find any element from a total stand still, Kor is right, you'll have to first find element, so both are equivalent.

However, if you already have a reference to an element, and you want to get its firstChild, firstChild is faster than getElementById. I'm pretty sure firstChild runs in constant time. I don't know the efficiency of getElementById, but it won't be more than n = (# of ids in document).

[Kor]

... if there is a self reference, well, hm, I guess that the code will run faster, I am not sure, I might check.

onsomeevent = "somefunction(this.firstChild)"

I am not sure how the self reference is interpreted...

[Beagle]

I'm pretty sure "this" resolves in constant time as well, because this is always defined wherever you are, it's just a variable like any other.

[brothercake]

Remember that "firstChild" is not necessarily what you mean - whitespace text nodes are included in mozilla's DOM, and firstChild might be a line break or tab between two elements.

[jkd]

The DOM tree is basically doubly-linked lists paired with a parent and this reference. As such, element.firstChild is just element.childNodes[0] which is basically (car element.childNodes) for the LISP-ers, which is a constant-time operation. Even (car (car element.childNodes)) is still constant.

As for getElementById, if I was writing a browser, I would store a global lookup of ids for the loaded document. One, everybody uses the method, so it would make it O(1) instead of O(n), where n is the number of nodes on the page, and two, ids are supposed to be unique, thus this provides a good way of checking for that.

I haven't done any tests to confirm it, but I'm willing to bet (a little amount) that getElementById runs in constant-time by keeping in memory id-ed nodes. In which case, there isn't a significant difference between a constant-time hash table lookup, and a constant-time linked list traversal (the latter may be several times faster, but still on the same order of magnitude).

[liorean]

The node transversals aren't actually implemented in constant time. They are typically implemented as filters applying to sets of nodes with the option to exclude subtrees, and as such for example a previousSibling access time isn't quite constant time.

In an answer to a question about traversal speeds Jens Lindström (one of the Opera devs) answered saying that (in Opera) the actual algorithmical complexity is at worst O(n^2) for random index access in nodelists (such as elm.childNodes, doc.all, elm.getElementsByTagName) where n is typically larger than the length of the nodelist.

As Opera performance doesn't seem deteriorate faster than that of the other browsers, I would say they have the same or similar enough algorithmical complexity for these types of traversals.