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

ⓘ Get performance results from real users on your website with Request Metrics.

Website Performance Monitoring by Request Metrics

Latest run results:

Run details: (Test run date: one year 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

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: one year 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