Most efficient way to iterate over all DOM elements

Question

Unfortunately I need to iterate over all the DOM elements of a page and I'm wondering what the most efficient technique is. I could probably benchmark these myself and might if I have the time but I'm hoping someone has already experienced this or has some options I hadn't considered.

Currently I'm using jQuery and doing this:

$('body *').each(function(){                                                                                                                            
    var $this = $(this);                                                                                                                                
    // do stuff                                                                                                                                         
});

While it works, It seems to cause some lag on the client. It could also be tweaked with a more specific jQuery context like $('body', '*'). It occurred to me that native Javascript is usually faster than jQuery and I found this:

var items = document.getElementsByTagName("*");
for (var i = 0; i < items.length; i++) {
    // do stuff
}

I'm assuming the native option is faster. Wondering if there are other options I hadn't considered. Maybe a recursive option that iterates over child nodes in parallel.

Solution 1

The Vanilla Javascript way you posted is the fastest. It will be faster than the jQuery solution you posted (See my comment on the question). If you're not removing or adding anything to the DOM in your loop and order of traversal doesn't matter, you can also speed it up ever so slightly by iterating in reverse:

var items = startElem.getElementsByTagName("*");
for (var i = items.length; i--;) {
    //do stuff
}

Edit: check this benchmark to see how much time you can save by using the native code: http://jsben.ch/#/Ro9H6

Solution 2

UPDATE:

Don't use $('body *') to iterate over the elements. It will be much quicker to use $('*') if you go for the JQuery method (see comments for details).

---

Plain ol' JavaScript is much faster, relatively speaking.

Using a test fiddle, I get about 30ms to process 13000 elements with JQuery, and 8ms to process 23000 elements using JavaScript (both tested on Chrome):

JQuery:      433  elements/ms
JavaScript:  2875 elements/ms

Difference:  664% in favor of plain ol' JavaScript

Note: Unless you have an incredibly large amount of elements on your page, this isn't going to make much of a difference. Also, you probably should time the logic in your loop, as that might be the limiting factor in all this.

Update:

Here is the updated results when considering much more elements (about 6500 per loop), I get about 648000 elements in 1500ms with JQuery, and 658000 elements in 170ms with JavaScript. (both tested on Chrome):

JQuery:      432  elements/ms
JavaScript:  3870 elements/ms

Difference:  895% in favor of plain ol' JavaScript

Looks like JavaScript sped up while JQuery stayed about the same.

Solution 3

It's not a good idea generally but this should work:

function walkDOM(main) {
    var arr = [];
    var loop = function(main) {
        do {
            arr.push(main);
            if(main.hasChildNodes())
                loop(main.firstChild);
        }
        while (main = main.nextSibling);
    }
    loop(main);
    return arr;
}
walkDOM(document.body);

Not including textnodes:

function walkDOM(main) {
    var arr = [];
    var loop = function(main) {
        do {
            if(main.nodeType == 1)
                arr.push(main);
            if(main.hasChildNodes())
                loop(main.firstChild);
        }
        while (main = main.nextSibling);
    }
    loop(main);
    return arr;
}

Edited!

Solution 4

The fastest way seems to be document.all (note that it's a property, not a method).

I've modified the fiddle of Briguy's answer to log these instead of jQuery, and it's consistently faster (than document.getElementsByTagName('*')).

The fiddle.

Solution 5

This is a solution to the problem as described in the comments (though not the actual question). I think it would be much faster the use elementFromPoint to test the area where you want to put your fixed-position element, and only worry about elements in that area. An example is here:

http://jsfiddle.net/pQgwE/4/

Basically, just set some minimum possible size of an element you're looking for, and scan the entire area that your new fixed position element wants to occupy. Build a list of unique elements found there, and only worry about checking the style of those elements.

Note that this technique assumes that the element you're looking for has the highest z-index (which seems a reasonable assumption for fixed position). If this is not good enough, then this could be adjusted to hide (or assign a minimum z-index) to each element after it's been discovered and test the point again, until nothing more is found (to be sure), and then restore them afterwards. This ought to happen so fast as to be imperceptible.

HTML:

<div style="position:fixed; left: 10px; top: 10px; background-color: #000000; 
    color: #FF0000;">I Am Fixed</div>
<div id="floater">OccupyJSFiddle!<br>for two lines</div>

JS:

var w = $(window).width(), h=$(window).height(),
    minWidth=10,
    minHeight=10, x,y;

var newFloat = $('#floater'), 
    maxHeight = newFloat.height(),
    el, 
    uniqueEls=[],
    i;

for (x=0;x<w;x+=minWidth) {
    for (y=0;y<h&& y<maxHeight;y+=minHeight) {
        el = document.elementFromPoint(x,y);
        if (el && $.inArray(el,uniqueEls)<0) {
            uniqueEls.push(el);
        }
    }
}
// just for the fiddle so you can see the position of the elements 
// before anything's done
// alert("click OK to move the floater into position.");
for (i=0;i<uniqueEls.length;i++) {
    el = $(uniqueEls[i]);
    if (el.css("position")==="fixed") {
        el.css("top",maxHeight+1);
    }
}

newFloat.css({'position': 'fixed',
             'top': 0,
             'left': 0});

View more solutions

Comments

[Jamie Treworgy]

This is a pretty unfair test because you're only iterting through a handful of elements. Of course jQuery will get killed since it has significant overhead for invoking any method. As you increase the number of elements the difference will diminish to almost nothing. (See the jsperf tests user1 & myself linked to in comments)

[Briguy37]

@jamietre: Ok, please stand by while I up the number of elements.

[Jamie Treworgy]

You are doing something in the jQuery loop that you aren't in the other one: converting each element to a jQuery object var $this = $(this);. Make the two iterators identical and I think you will find this difference largely vanishes.

[Jamie Treworgy]

(edit) you are also selecting "body *" for jquery and just "*" for js.

[Briguy37]

@jamietre: If you don't have access to the element object, you can't perform any tasks. Thus, var $this = $(this); in some form is a required part of the JQuery test. I'm open to suggestions about different ways of getting a handle on the object, though.

[Jamie Treworgy]

No, it's not. "this" is an element already in the loop... just like the one returned by the native method. Why would you have to convert it to a jQuery object in one situation, but not the other? They start out the same.

[Jamie Treworgy]

Here's a more fair test based on yours (using the same selector for both, and the same iteration method): jsfiddle.net/Pv8zm/4

[Briguy37]

@jamietre: Observe the same case with a selector of 'body *': jsfiddle.net/briguy37/Pv8zm/5. Looks like that's what's making it so slow, thought the initialization doesn't help either, as you pointed out.

[Jamie Treworgy]

If you change the JS to use querySelectorAll('body *') they're almost identical again. I am pretty sure that's the only method that jQuery uses, which probably explains the big difference seen in your last example. This is interesting because I wouldn't have guessed that using the element-targeted method as you did (body.getElements...) would be so much faster than document.querySelectorAll (at least in chrome as I've been running this). Of course it's a bit academic since one doesn't normally run the same selector a thousand times in a row :)

[kevzettler]

I've taken this method and integrated it with some of the benchmarks below. It appears to be significantly faster. Am I missing anything? jsfiddle.net/Pv8zm/7

[kevzettler]

I've implemented @petars solution from above stackoverflow.com/a/8747184/93212 it seems significantly faster am I missing anything?

[kevzettler]

thanks for this attempt. However I don't believe it will work in my case. I've updated your example to be more similar to what i'm seeing in production. jsfiddle.net/pQgwE/5 Two fixed positioned elements at top:0px overlapping. also in my case there are multiple fixed elements in the external design. Some of them positioned relative to others so doint an elementFromPoint method could get out of hand quickly.

[Jamie Treworgy]

Unless you have two overlapping elements that actually take up exactly the same real estate, it will still work, see: jsfiddle.net/pQgwE/14 -- the change you made turned the element that was supposed to be yours into something else. But if for some reason you expect your clients to have multiple fixed position elements in exactly the same real estate (which makes no sense, since they would interfere with each other) there's no reason you can't do what I already suggested above: after you detect each one, hide it or lower its z-index, and check again to see what was behind it.

[Jamie Treworgy]

btw i'm not sure what you mean by "elementFromPoint method could get out of hand quickly". It doesn't matter whether elements are positioned relatively, or anything else. That's what is so great about that method. It tells you what's at a specific point regardless of how it got there. What you do once you detect an element you need to move is exactly the same using this method, as it would be if you iterated through the entire DOM to find them. It's just a lot less work to find the stuff you're interested in this way.

[kevzettler]

I apologize. I played around with your example some more and it appears to do exactly what I need. I've updated the example to show the kind of layout i'm working with and it flows better than what i'd hope. jsfiddle.net/pQgwE/17

[Jamie Treworgy]

That looks pretty cool actually. It should be easy to adjust this logic to handle different situations - if you only have a titlebar-sized area to check, even checking like every other pixel (if you had to) is probably a good bit faster than iterating/checking calculated CSS through the whole DOM. But I bet every 10 px is plenty and should be virtually instantaneous. Let me know if you need any other help tweaking it.

[Briguy37]

@kevzettler: I think that method iterates over text nodes as well, so it is inflating the number of nodes processed. See this test.

[kevzettler]

Can This example be updated to not include textnodes? The recursion is interesting but its iterating over unnecessary nodes

[Jamie Treworgy]

I think that the real time suck is going to come from checking the calculated CSS of every single node, not from the selector. But to skip text nodes just use firstElementChild and nextElementSibling instead. I don't think this is going to be substantively different from using a selector once you add the rest of the logic (e.g. this isn't what's making it slow).

[Brian J]

I think you left out the conditional part of the for loop, but it looks like the code will actually just run forever, using i-- as the condition with no decrement. Is that correct?

[Paul]

@BrianJ The i-- is the conditional part of the loop. It's like saying i-- != 0, but since 0 is falsy you can leave that part off

[hoju]

unfortunately it is not a standard property: developer.mozilla.org/en-US/docs/Mozilla/…

[Yuvaraj V]

var i = 0, items = startElem.getElementsByTagName("*"); while(items[i]) {//dostuf ; i++ }

[Lamar]

I'm curious why would backwards iterating can be faster. May you explain or point out to an article?

[Paul]

@Lamar I don't think it is any faster anymore since JavaScript engines do a very good job of optimizing now. A long time ago it was every so slightly faster because instead of doing i++ on every iteration and then not using the result of that expression and instead separately evaluating i < length for the loop condition, you could use i--; (effectively i-- != 0) both to advance the iteration and as the loop condition.

[Jack G]

@Paulpro I believe the main reason has to do with the number of local variables. The decreasing iterator is faster because instead of the two variables (one for length, and one for index) involved in forwards iteration, there is only one variable involved in backwards iteration: the current index. If, however, Javascript had access to memory pointers like C/C++, then doing a forward iterator from the start memory address of the array to the end address should be even faster than backwards iteration because you would not have to add the start address to the index counter every iteration.