querySelectorAll vs NodeIterator vs TreeWalker - fastest pure JS flat DOM iterator

user_1724228 0
Viewed 1254

I'd like to flatten a DOM tree into an Array. The result should include the root as the first entry. Plain JS solution is preferred. What's the fastest way to achieve that?

HTML structure example:

<div class="tested-root">
    <span></span>
    <span></span>
    <div>
        <span></span>
        <span></span>
    </div>
    <div>
        <span></span>
        <span></span>
    </div>
</div>

The output expected to be: [div.tested-root, span, span, div, span, span, div, span, span] or alike (this one is DFS, but doesn't really matter for sake of this question).

From the three methods below which is the fastest:

  • querySelectorAll
  • NodeIterator
  • TreeWalker
traversal dom html javascript performance
1 Answers

I've came to try another few just recently. Below the results from slowest to fastest, while specifying how the one slower than the fastest.

Chrome based results. Safari shows roughly the same numbers. Firefox has issues with that perf app and was not verified.

Method 1 (unshift) ~81% slower

const list = Array.from(root.querySelectorAll('*'));
list.unshift(root);

Method 2 (spread) ~77% slower

const list = [root, ...root.querySelectorAll('*')];

Method 3 (NodeIterator) ~32% slower

const list = [];
const ni = document.createNodeIterator(root, NodeFilter.SHOW_ELEMENT);
let next;
while (next = ni.nextNode()) {
    list.push(next);
}

Method 4 (TreeWalker) fastest

const list = [root];
const tw = document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT);
let next;
while (next = tw.nextNode()) {
    list.push(next);
}

Bonus (empty root check) ~1% slower (~98% faster for empty root)

const list = [root];
if (root.childElementCount) {
    const tw = document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT);
    let next;
    while (next = tw.nextNode()) {
        list.push(next);
    }
}

Observation and conclusions

  • array operations, if/when considered, show that spread (...) operator way is faster than unshift method
  • main performance gain comes from using the native iterators, TreeWalker being the fastest by far
  • it is almost always reasonable to implement that special speed-up bonus, for nested structures, the impact is neglectable but for an empty tree it runs twice faster

Bench tests can be found here.

user_17242280
Related