Best DOM tree traverse

[oliveirard]

Hi everybody!

What's the best DOM tree traverse method that you guys know? Nowadays I'm developing for pocket pcs and efficiency is quite an issue. Recursive methods like the one available at http://www.permadi.com/tutorial/domTree/index.html take too long. Hope you guys help me improve this one.

Thanks!

[oliveirard]

Ok. Here's what I've found so far. First I thought the delay problem was because of the recursion. But my iterative version takes even more because of the array pushes/pops. Take a look:

function treeTraverseIterative(elem) {
	var queue = new Array();
	var i, currentElem, childs;

	queue.push(elem);
	while (queue.length > 0) {
		currentElem = queue.pop();
		visit(currentElem);
		childs = currentElem.childNodes.length;
		for (i = 0; i < childs; i++) {
			queue.push(currentElem.childNodes[i]);
		}
	}
}
function treeTraverseRecursion(currentElem) {
	var i = 0;
	var currentElemChild = currentElem.childNodes[i];

	if (currentElem) {
		while (currentElemChild) {
			treeTraverseRecursion(currentElemChild);
			i++;
			currentElemChild = currentElem.childNodes[i];
		}
		visit(currentElem);
	}
}
function visit(elem) {
	// visits the element
}

Now I'm reaching to this conclusion. I can stand with this tree traverse delay , but updates to this tree takes too long. If I try to change only the text fields (nodeType == 3), on some examples, it turned out 3 times more consuming! Please.. can anyone help me do this faster?

Thanks for your attention

[mwinter]

Trying to tackle it generically isn't likely to yield any results, especially as I doubt many (if any) of the other regular posters have Pocket PCs that they can use to experiment upon. Perhaps if you explain precisely what you're trying to do (and include a link to an example, preferably), you'll have better luck receiving useful tips.

Mike

[oliveirard]

Thanks mwinter! I'll try to do it this time. I'm using user javascript with Opera Mobile to change texts content and size from sites of my domain at the onload event. The problem is that it is taking too much time to traverse/change the DOM tree. If you access these examples (iterative, recursive), maybe you can help me do this faster. These examples clock the time to traverse the DOM tree and create/insert a font node with the character "*" for every text entry. See the results I'm getting:

• iterative algorithm on my PC: 0.2 second (average);
• recursive algorithm on my PC: 0.8 second (average);
• iterative algorithm on Pocket PC: 28 seconds (average);
• recursive algorithm on Pocket PC: 35 seconds (average);

After running these tests, I commented that javascript part where a new node is created with the font tag and the "*" character everytime a text is found on the DOM tree. The results are expressive better:

• iterative algorithm on Pocket PC: 2.75 seconds (average);
• recursive algorithm on Pocket PC: 2 seconds (average);

So I tried to change the text content without changing the node structure using currentElem.nodeValue = "*"; Although it takes half of the time obtained on the first tests, it is still a big waste, and even don't size up the text:

• iterative algorithm on Pocket PC: 15 seconds (average);
• recursive algorithm on Pocket PC: 11 seconds (average);

In summary, I need to parse/traverse the DOM tree looking for texts and change their content and size. From these results, we can say the problem isn't with the DOM traversal algorithm, but with the DOM structure change. Please, I would really appreciate if you pros could help me do this faster.

Thanks for the attention

[mwinter]

You still haven't answered my question properly. I asked what precisely are you doing. That is, the real goal.

If your example is anything like the real thing, then walking through the entire document tree just isn't feasible. According to IE, there are 4059 elements within that document, however, there are only 1000 text nodes, each contained within a strong element. Simply getting references to those strong elements using the getElementsByTagName method would reduce the amount of time necessary to around a quarter.

As I said, approaching this generically isn't likely to get you any results. If you want a practical solution, you need to find shortcuts using the real situation.

Mike

[oliveirard]

Sorry Mike. I'll try again. The real situation could be ANY web page. Ok? So it is indeed a generic situation and the getElementsByTagName won't help. Only on that example, but we must try to solve it generically (that example was just to substitute the pocket PC that you, and probably most from this forum, don't have).

Let's get back to those results. Remember when I said that huge DOM tree took 2 seconds to be traversed on the pocket? That's enough to me. What I can't stand is to wait about more 30 seconds to make updates to this text, including changing and resizing. It feels like the problem is really at this stage: updating the DOM tree after EVERY font node inserted. Any suggestions?

[mwinter]

Let's get back to those results. Remember when I said that huge DOM tree took 2 seconds to be traversed on the pocket? That's enough to me. What I can't stand is to wait about more 30 seconds to make updates to this text, including changing and resizing. It feels like the problem is really at this stage: updating the DOM tree after EVERY font node inserted. Any suggestions?

If the real bottleneck is the DOM manipulation, then you might as well forget about traversal efficiency (and I expect you could only shave a few milliseconds off using a depth-first traversal, which shouldn't need a queue).

There's obviously no way to speed up the native code used to create new elements. However, it may be feasible (the question shifts to why, not what, you are doing, now) to use the server to modify the document and return it. After all, it only takes a few seconds to complete a HTTP request/response cycle even over dial-up (at least for well-written documents).

I'm afraid that this looks like a dead end, but I suppose it's to be expected, really: a Pocket PC is resource-limited and cannot be expected to have the processing power of a desktop machine.

Mike

[oliveirard]

WOW!! Not a dead end! Got a suggestion from this friend of mine (thanks TwoD!) to use stylesheets with relative text sizes instead of creating new nodes for every text. Conclusion: traversing the DOM tree on the pocket takes usually less than a second. The bottle neck is the creation/insertion of new nodes. I don't believe I didn't test this ! Anyway, now things go faster, but still a couple of seconds of an annoying delay.

Now I believe its quite a dead end considering more improves. Just to mention, I already tested to make changes on innerHTML instead of traversing the DOM. It's impressive awful! A simple parsing takes about 4 times more than the DOM traversal. String routines don't go well on these little devices... Any more suggestions??

Well, if none, I gotta say the delay may be acceptable if I could, at least, hide the next page until it is loaded. Do you know how can I stand with the current page and only present the next one when it's onload event is fired? This way I could hide that small delay. Just to mention, I can't change the original pages, like including "display:none" on body tag to show it at the onload event. I can only change the page dynamically (it could also be some kind of trick with configuring the browser not to display a page until everything is loaded or.. I don't know ).

Counting on you guys! And thanks for everything!

P.S.: thanks, mwinter, for the server-side programming suggestion. In fact, that was my first attempt since I don't like the client-side (too messy!), but I gotta do it this way. Not allowed to reach the servers.

[nikob]

I did a code for corinis with iterative traversal:
http://dev.corinis.org/corinis/wiki/...t/DomTraversal

/**
 * go through every child node of root
 */
function traverseDom (root)
{

        var s = '';

        var c = root, n = null;
        do
        {
                n = c.firstChild;
                if (n == null)
                {
                        // visit c
                        if (c.nodeType == 3)
                                s += c.nodeValue.replace(/\s/, "");
                        // done visit c

                        n = c.nextSibling;
                }
                
                if (n == null)
                {
                        var tmp = c;
                        do {
                                n = tmp.parentNode;
                                if (n == root)
                                        break;

                                // visit n
                                if (n.nodeType == 3)
                                        s += n.nodeValue.replace(/\s/, "");
                                // done visit n

                                tmp = n;
                                n = n.nextSibling;
                        }
                        while (n == null)
                }
                
                c = n;
        }
        while (c != root);
        return s;
}

its a lot neater than the code posted before, because it does not use an Array.

I like using the iterative way to go though the dom much more than the recursive way because I found out that using a lot of memory (like with a recursive traversal or with the previous code) makes ie not only slow, but also quite unstable.

[oliveirard]

Thanks nikob! I'll take a look, make some tests and come back with the results.