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))

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 days ago)

User agent: Mozilla/5.0 (iPhone; CPU iPhone OS 18_7 like Mac OS X) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/26.3 Mobile/15E148 Safari/604.1

Browser/OS: Mobile Safari 26 on iOS 18.7

View result in a separate tab

Test name	Executions per second
NodeIterator	337271.1 Ops/sec
TreeWalker	309246.0 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.

Related benchmarks:

NodeIterator vs TreeWalker for Component Extraction (version: 0)

Comparing performance of: NodeIterator vs TreeWalker

Created: 3 years ago by: Guest

Jump to the latest result

NodeIterator

TreeWalker

Suite status: <idle, ready to run>

Fastest: N/A

Slowest: N/A

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