Benchmark: NodeIterator vs TreeWalker for Component Extraction

Script Preparation code:

// language=HTML
const html = `
<body>
  <h1>Doc with mix of light and shadow DOM custom elements</h1>
  <p>NOTE: we rely on Chrome's support for "declarative shadow DOM"</p>
  <x-light id="1">
    <!-- comment -->
    Lorem ipsum dolor sit amet consectetur adipisicing elit. Rerum deserunt
    dolor nesciunt ab placeat nostrum. Laborum rem quisquam ullam, officiis
    maiores fugiat fuga animi quos. Ex earum a alias magni.
  </x-light>
  <x-shadow id="2">
    <template shadowroot="open">
      <!-- comment -->
      <p>
        Lorem ipsum, dolor sit amet consectetur adipisicing elit. Ullam amet
        error delectus...
      </p>
      <slot></slot>
    </template>
    <!-- comment -->
    Impedit nesciunt excepturi perferendis quis in debitis vitae soluta
    voluptatibus praesentium repellat labore quas. Cum unde consectetur
    maiores.
  </x-shadow>
  <x-light id="3">
    Lorem ipsum dolor sit amet consectetur adipisicing elit. Rerum deserunt
    dolor nesciunt ab placeat nostrum. Laborum rem quisquam ullam, officiis
    maiores fugiat fuga animi quos. Ex earum a alias magni.
    <x-light id="3.1">
      <span>Lorem ipsum dolor sit amet</span> consectetur adipisicing elit.
      Rerum deserunt dolor nesciunt ab placeat nostrum. Laborum rem quisquam
      ullam, officiis maiores fugiat fuga animi quos. Ex earum a alias magni.
      <x-light id="3.1.1">
        Lorem ipsum dolor sit amet consectetur adipisicing elit. Rerum
        deserunt dolor nesciunt ab placeat nostrum. Laborum rem quisquam
        ullam, officiis maiores fugiat fuga animi quos. Ex earum a alias
        magni.
      </x-light>
    </x-light>
  </x-light>
  <x-shadow id="4">
    <template shadowroot="open">
      <x-shadow id="4.1">
        <template shadowroot="open">
          Lorem ipsum, dolor sit amet consectetur adipisicing elit. Ullam amet
          error delectus...
          <slot></slot>
          <x-shadow id="4.1.1">
            <template shadowroot="open">
              Lorem ipsum, dolor sit amet consectetur adipisicing elit. Ullam
              amet error delectus...
              <slot></slot>
            </template>
            Impedit nesciunt excepturi perferendis quis in debitis vitae
            soluta voluptatibus praesentium repellat labore quas. Cum unde
            consectetur maiores.
            <x-light id="4.1.1.1">
              <p>
                Lorem ipsum dolor sit amet consectetur adipisicing elit. Rerum
                deserunt dolor nesciunt ab placeat nostrum. Laborum rem
                quisquam ullam, officiis maiores fugiat fuga animi quos. Ex
                earum a alias magni.
              </p>
            </x-light>
          </x-shadow>
        </template>
        Impedit nesciunt excepturi perferendis quis in debitis vitae soluta
        voluptatibus praesentium repellat labore quas. Cum unde consectetur
        maiores.
      </x-shadow>
      <slot></slot>
    </template>
    <x-shadow id="5">
      <template shadowroot="open">
        Lorem ipsum, dolor sit amet consectetur adipisicing elit. Ullam amet
        error delectus...
        <slot></slot>
      </template>
      Impedit nesciunt excepturi perferendis quis in debitis vitae soluta
      voluptatibus praesentium repellat labore quas. Cum unde consectetur
      maiores.
    </x-shadow>
  </x-shadow>
</body>
`;
const fragment = new DOMParser().parseFromString(html, 'text/html', {
	includeShadowRoots: true
});
document.body.replaceChildren(fragment.body);

function getAllComponents(walkerFunc, root = document.body, shadowParent) {
  const components = []
  const lightParentStack = []
  let element, customElementType, customElementName, customElement
  const walker = walkerFunc(root)

  while ((element = walker.nextNode())) {
    if (
      (hasShadowRoot = !!element.shadowRoot) ||
      (customElementType = getCustomElementType(element))
    ) {
      while (
        lightParentStack.length &&
        !isAncestor(element, lightParentStack[0].element)
      ) {
        lightParentStack.shift()
      }

      lightParent = lightParentStack[0]

      if (customElementType) {
        customElementName =
          customElementType === 'built-in'
            ? element.getAttribute('is')
            : element.tagName.toLowerCase()

        customElement = {
          type: customElementType,
          name: customElementName,
          definition: customElements.get(customElementName),
        }
      } else {
        customElement = false
      }

      const component = {
        element,
        hasShadowRoot,
        customElement,
        shadowParent,
        lightParent,
        shadowChildren: [],
        lightChildren: [],
      }

      if (shadowParent) {
        shadowParent.shadowChildren.push(component)
      }

      if (lightParent) {
        lightParent.lightChildren.push(component)
      }

      components.push(component)

      // regardless of hasShadowRoot, an element can have light DOM children
      lightParentStack.unshift(component)

      if (component.hasShadowRoot) {
        components.push(
          ...getAllComponents(walkerFunc, element.shadowRoot, component)
        )
      }
    }
  }

  return components
}

function getCustomElementType(el) {
  return el.tagName.includes('-')
    ? 'autonomous'
    : el.hasAttribute('is')
    ? 'built-in'
    : null
}

function isAncestor(child, ancestor) {
  let parent = child.parentNode

  while (parent) {
    if (parent === ancestor) {
      return true
    }

    parent = parent.parentNode
  }

  return false
}

function createComponentTreeWalker(root) {
  return document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT, null)
}

function createComponentIterator(root) {
  return document.createTreeWalker(root, NodeFilter.SHOW_ELEMENT, null)
}

Tests:

NodeIterator
console.log(getAllComponents(createComponentIterator))
TreeWalker
console.log(getAllComponents(createComponentTreeWalker))

Historical Performance Data aggregated from 14 community runs

Desktop Results:

Chrome 9 runs

TreeWalker

103K/s

NodeIterator

100K/s

View exact numbers

✓ TreeWalker: 102,569 ops/sec
• NodeIterator: 100,049 ops/sec

Firefox 5 runs

NodeIterator

35K/s

TreeWalker

34K/s

View exact numbers

✓ NodeIterator: 35,450 ops/sec
• TreeWalker: 33,553 ops/sec

Results show median performance across all community submissions. Run this benchmark yourself to verify on your device.

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
NodeIterator
TreeWalker

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 3 months ago)

User agent: Mozilla/5.0 (X11; Linux x86_64; rv:151.0) Gecko/20100101 Firefox/151.0

Browser/OS: Firefox 151 on Linux

View result in a separate tab

NodeIterator

35K/s

TreeWalker

34K/s

View exact numbers

Test name	Executions per second
✓ NodeIterator	35,450 Ops/sec
TreeWalker	33,553 Ops/sec

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

LLMs can make mistakes. Check important info.

It appears that you are providing code and benchmark results for two different approaches to traversing an HTML document: `createComponentTreeWalker` (which uses the `NodeFilter.SHOW_ELEMENT` approach) and `createComponentIterator` (which uses the `NodeIterator` approach).

The benchmark results show that the Tree Walker approach outperforms the Node Iterator approach, with a significantly higher number of executions per second.

To answer your question:

**What is the optimal approach for traversing an HTML document?**

Based on the benchmark results, it seems that the `createComponentTreeWalker` function (which uses the Tree Walker approach) is the more efficient option. This is likely because the Tree Walker approach allows for a more optimized traversal of the DOM tree, as it only visits elements that have been explicitly requested by the user agent.

**Why does this happen?**

The reason why the Tree Walker approach outperforms the Node Iterator approach may be due to the following factors:

*   The `createComponentTreeWalker` function is designed to traverse the DOM tree in a more optimized way, using the `NodeFilter.SHOW_ELEMENT` approach. This allows it to skip over elements that are not relevant to the traversal, which can reduce overhead and improve performance.
*   The Tree Walker approach may also be able to take advantage of certain optimizations provided by modern browsers, such as caching and memoization.

However, without more information about the specific requirements and constraints of your use case, it's difficult to provide a definitive answer. You may want to consider profiling and benchmarking both approaches to determine which one is best suited for your particular needs.

NodeIterator vs TreeWalker for Component Extraction (version: 0) Benchmark.js

Comparing performance of: `NodeIterator vs TreeWalker`

Created: 4 years ago by: Guest

Go to the latest result

NodeIterator

TreeWalker

Historical Performance Data aggregated from 14 community runs

Desktop Results:

Chrome 9 runs

Firefox 5 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

NodeIterator vs TreeWalker for Component Extraction (version: 0) Benchmark.js

Comparing performance of: NodeIterator vs TreeWalker

Created: 4 years ago by: Guest

Go to the latest result

NodeIterator

TreeWalker

Historical Performance Data aggregated from 14 community runs

Desktop Results:

Chrome 9 runs

Firefox 5 runs

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

Autogenerated LLM Summary (model llama3.2:3b, generated one year ago):

Related benchmarks

Comparing performance of: `NodeIterator vs TreeWalker`