Run results for: Traverse Elements in DOM tree 3

Run details:

User agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36

Browser: Chrome 107

Operating system: Mac OS X 10.15.7

Device Platform: Desktop

Date tested: one year ago

Test name	Executions per second
Recursive traversal function	5764.8 Ops/sec
Queue-based traversal function	4674.8 Ops/sec
Array-based traversal function	5538.6 Ops/sec

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

Run results for: Traverse Elements in DOM tree 3

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

Recursive traversal function

Queue-based traversal function

Array-based traversal function