Benchmark: Traverse Elements in DOM tree 3

HTML Preparation code:

<div id="traversal-root">
	<div>
    	<div>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><section></section></div></div></div>
      	</div>
		<div>
        	<div><section><section><div></div></section></section></div>
         	<div><div><div><div></div></div></div></div>
          	<section><div><div><div></div></div></div></section>
      	</div>
    	<section>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><div></div></div></div></div>
      	</section>
    	<div>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><div></div></div></div></div>
      	</div>
	</div>
	<div>
    	<div>
        	<div><div><section><div></div></section></div></div>
         	<div><div><section><div></div></section></div></div>
          	<div><div><div><div></div></div></div></div>
      	</div>
		<div>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><section></section></div></div></div>
      	</div>
    	<div>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><div></div></div></div></div>
      	</div>
    	<section>
        	<div><div><div><div></div></div></div></div>
         	<div><div><div><div></div></div></div></div>
          	<div><div><div><div></div></div></div></div>
      	</section>
	</div>
	<section>
    	<section>
        	<section><section><section><section></section></section></section></section>
         	<div><div><div><section></section></div></div></div>
          	<div><section><div><div></div></div></section></div>
      	</section>
		<section>
        	<div><div><div><section></section></div></div></div>
         	<div><div><div><section></section></div></div></div>
          	<section><div><section><section></section></section></div></section>
      	</section>
    	<div>
        	<div><div><div><section></section></div></div></div>
         	<div><section><div><div></div></div></section></div>
          	<section><div><div><div></div></div></div></section>
      	</div>
    	<div>
        	<div><section><div><div></div></div></section></div>
         	<div><div><div><section></section></div></div></div>
          	<section><div><section><div></div></section></div></section>
      	</div>
	</section>
</div>

Script Preparation code:

class FastQueue {
	
	constructor() {
		this._array = new Array(16);
		this._length = 0;
		this._front = 0;
	}
	
	push(value) {
		const arr = this._array;
		if (arr.length === this._length) {
			arr.length *= 2;
			arrayMove(arr, this._length, this._front);
		}
		arr[(this._front + this._length++) & (arr.length - 1)] = value;
	}
	
	shift() {
		if (this._length === 0) return;
		const arr = this._array;
		const frontIndex = this._front;
		const ret = arr[frontIndex];
		arr[frontIndex] = undefined;
		this._front = (frontIndex + 1) & (arr.length - 1);
		this._length -= 1;
		return ret;
	}
}

const arrayMove = (arr, moveBy, len) => {
	for (let i = 0; i < len; ++i) {
		arr[i + moveBy] = arr[i];
		arr[i] = undefined;
	}
};


window.symbol = Symbol('symbol');
window.traversalRoot = document.getElementById('traversal-root');
for (const el of traversalRoot.getElementsByTagName('section')) {
	Object.defineProperty(el, window.symbol, { value: {} });
}

window.isMatch = function isMatch(element) {
	return element[symbol] !== undefined;
}

window.traverse = function traverse(element, callback) {
	if (isMatch(element)) {
		callback(element);
	} else if (element instanceof HTMLSlotElement && element.assignedNodes().length) {
		for (const child of element.assignedElements()) {
			traverse(child, callback);
		}
	} else {
		for (const child of element.children) {
			traverse(child, callback);
		}
	}
};

window.traverseQueue = function traverseQueue(initialElement, callback) {
	const queue = new FastQueue();
	queue.push(initialElement);

	let element;
	while (element = queue.shift()) {
		if (isMatch(element)) {
            callback(element);
        } else if (element instanceof HTMLSlotElement && element.assignedNodes().length) {
            for (const child of element.assignedElements()) {
                queue.push(child);
            }
        } else {
            for (const child of element.children) {
                queue.push(child);
            }
        }
	}	
};

window.traverseArray = function traverseArray(initialElement, callback) {
	const queue = [];
	queue.push(initialElement);

	let element;
	while (element = queue.shift()) {
		if (isMatch(element)) {
            callback(element);
        } else if (element instanceof HTMLSlotElement && element.assignedNodes().length) {
            for (const child of element.assignedElements()) {
                queue.push(child);
            }
        } else {
            for (const child of element.children) {
                queue.push(child);
            }
        }
	}	
};

Tests:

Recursive traversal function
const results = []; traverse(traversalRoot, function callback(element) { for (const child of element.children) { traverse(child, callback); } results.push(element); })
Queue-based traversal function
const results = []; traverseQueue(traversalRoot, function callback(element) { for (const child of element.children) { traverseQueue(child, callback); } results.push(element); })
Array-based traversal function
const results = []; traverseArray(traversalRoot, function callback(element) { for (const child of element.children) { traverseArray(child, callback); } results.push(element); })

Rendered benchmark preparation results:

Suite status: <idle, ready to run>

Previous results

Test case name	Result
Recursive traversal function
Queue-based traversal function
Array-based traversal function

Fastest: N/A

Slowest: N/A

Latest run results:

Run details: (Test run date: 2 years ago)

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

Browser/OS: Mobile Safari 15 on iOS 15.6.1

View result in a separate tab

Test name	Executions per second
Recursive traversal function	12012.3 Ops/sec
Queue-based traversal function	9277.9 Ops/sec
Array-based traversal function	10922.6 Ops/sec

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

LLMs can make mistakes. Check important info.

I'll do my best to provide a solution.

It seems like you have a large HTML document with nested `<div>` elements, and you want to traverse the DOM tree recursively using different algorithms (Recursive Traversal Function, Queue-Based Traversal Function, Array-Based Traversal Function).

To solve this problem, I would suggest the following steps:

1. **Write a recursive function** that traverses the DOM tree using recursion. This function will take an element as input and call itself for each of its child elements.
2. **Implement the queue-based traversal function**, which uses a queue data structure to traverse the DOM tree. This function will also take an element as input and add it to the queue, then process all elements in the queue until it's empty.
3. **Implement the array-based traversal function**, which uses an array to store the elements to be traversed. This function will take an element as input, add it to the array, and then traverse all elements in the array using a loop.

To write the actual code, I would need more information about the structure of your HTML document and the specific requirements for each traversal algorithm. However, here's some sample code to get you started:
```javascript
// Recursive Traversal Function
function traverseRecursive(element) {
  console.log(element);
  for (const child of element.children) {
    traverseRecursive(child);
  }
}

// Queue-Based Traversal Function
function traverseQueue(element) {
  const queue = [element];
  while (queue.length > 0) {
    const currentElement = queue.shift();
    console.log(currentElement);
    for (const child of currentElement.children) {
      queue.push(child);
    }
  }
}

// Array-Based Traversal Function
function traverseArray(element, array) {
  array.push(element);
  for (const child of element.children) {
    traverseArray(child, array);
  }
}
```
Note that these are simplified examples and may not cover all edge cases. Additionally, the performance of each algorithm will depend on the specific structure of your HTML document.

Please let me know if you'd like me to elaborate on any part of this solution or provide more code snippets!

Related benchmarks:

Traverse Elements in DOM tree 3 (version: 0)

What's the fastest way to find all elements of a certain criteria within a DOM tree?

Comparing performance of: Recursive traversal function vs Queue-based traversal function vs Array-based traversal function

Created: 2 years ago by: Guest

Jump to the latest result

Recursive traversal function

Queue-based traversal function

Array-based traversal function

Suite status: <idle, ready to run>

Experimental features:

Fastest: N/A

Slowest: N/A

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