Linked list: for-of iterator (non-generator) vs while loop vs plain for loop vs forEach (v4)

Revision 4 of this benchmark created on

Setup

/**
 * A mixin class to add linked list functionality to any class.
 */
function Link(BaseClass = class {}) {
    //
    return class Link extends BaseClass {
        next = null;
        prev = null;

        /**
         * Set this to true if the linked list is circular.
         */
        circular = false;

        insertAfter(link) {
            link.unlink(); // remove from previous list if any
            const next = this.next;
            this.next = link;
            link.prev = this;
            link.next = next;
            if (next)
                next.prev = link;
        }
        
        /**
         * Remove this Link from the linked list.
         */
        unlink() {
            const nextLink = this.next;
            const prevLink = this.prev;
            this.next = this.circular ? this : null;
            this.prev = this.circular ? this : null;
            if (prevLink) prevLink.next = nextLink;
            if (nextLink) nextLink.prev = prevLink;
        }
        
        forEach(fn) {
        	let link = startLink
			for (let i = 0, l = 100000; i < l; i += 1) {
				link
				fn(link)
				link = link.next
			}
        }

        /**
         * Returns an iterator for iterating over all Links in th linked list.
         *
         * @param forward - True to iterate forward, false to iterate backward.
         *
         * @param check - True to check for circularity (throws if not
         * circular), false to skip.
         */
        *links(forward = true, check = true) {
            let link = this;
            let next;
            let prev;
            let i = 0;

            do {
                if (!link)
                    throw new NonCircularError();
                next = link.next;
                prev = link.prev;
                
                yield [link, i++];
            } while ((link = forward ? next : prev) != this && (this.circular ? check || (!check && link) : link));
        }
        *linksReverse(check = true) {
            yield* this.links(false, check);
        }
        
        // [Symbol.iterator] = this.links;
        
        [Symbol.iterator]() {
            return this.iteratorCached();
        }
        iteratorCached() {
            // return a custom iterator without using the links() generator:
            let link = this;
            let i = 0;
            const iteratorResult = { done: false, value: link };
            return {
                [Symbol.iterator]() {
                    return this;
                },
                next: () => {
                    if (!link || (i !== 0 && link === this)) {
                        if (!link && this.circular)
                            throw new NonCircularError();
                        iteratorResult.done = true;
                        iteratorResult.value = undefined;
                        return iteratorResult;
                    }
                    iteratorResult.value = link;
                    link = link.next;
                    i++;
                    return iteratorResult;
                },
            };
        }
        iterator() {
            // return a custom iterator without using the links() generator:
            let link = this;
            let i = 0;
            return {
                [Symbol.iterator]() {
                    return this;
                },
                next: () => {
                    if (!link || (i !== 0 && link === this)) {
                        if (!link && this.circular)
                            throw new NonCircularError();
                        return { done: true, value: undefined };
                    }
                    const value = link;
                    link = link.next;
                    i++;
                    return { done: false, value };
                },
            };
        }
    };
}
class NonCircularError extends Error {
    constructor() {
        super('Expected linked list to be circular.');
    }
}

class MyLink extends Link() {
	next = this // circular
	prev = this // circular
	circular = true
}

let lastLink

for (const _ of Array.from({length: 100000})) {
	const link = new MyLink()
	lastLink?.insertAfter(link)
	lastLink = link
}

const startLink = lastLink.next

Test runner

Ready to run.

Testing in
TestOps/sec
for-of, Symbol.iterator -> iterator (cached)
for (const link of startLink) {
	link
	globalThis.window
}
ready
while loop
let link = startLink
do {
	link
	globalThis.window
} while ((link = link.next) !== startLink)
ready
plain for loop
let link = startLink
for (let i = 0, l = 100000; i < l; i += 1) {
	link
	link = link.next
	globalThis.window
}
ready
forEach
startLink.forEach(link => {
	link
	globalThis.window
})
ready
for-of, iterator() (no cache)
for (const link of startLink.iterator()) {
	link
	globalThis.window
}
ready
for-of, iteratorCached() (cached)
for (const link of startLink.iteratorCached()) {
	link
	globalThis.window
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.