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

Revision 6 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;
        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;
        }
        insertBefore(link) {
            link.unlink(); // remove from previous list if any
            const prev = this.prev;
            this.prev = link;
            link.next = this;
            link.prev = prev;
            if (prev)
                prev.next = 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 circular, and pointing to itself again, that's fine, it'll be GC'd
            if (nextLink)
                nextLink.prev = prevLink;
        }
        /**
         * Returns an iterator for iterating over all Links in th linked list.
         *
         * @param forward - True to iterate forward, false to iterate backward.
         *
         * @param checkCircular - True to check for circularity (throws if not
         * circular), false to skip. Skipping is useful when the list is in
         * process of being constructed.
         *
         * This handles several cases:
         * - circular linked list (throw if not circular)
         * - circular linked list but checkCircular is false (skip check, don't throw)
         * - non-circular linked list (stop at null)
         */
        // TODO handle deletion during iteration
        *links(forward = true, checkCircular = true) {
            let link = this;
            while (true) {
                yield link;
                link = forward ? link.next : link.prev;
                if (this.circular && checkCircular && !link)
                    throw new NonCircularError();
                if (link === this)
                    break; // circular done
                if (!link)
                    break; // non-circular done
            }
        }
        *linksReverse(checkCircular = true) {
            yield* this.links(false, checkCircular);
        }
        iterator(forward = true, checkCircular = true) {
            // return a custom iterator without using the links() generator:
            let link = this;
            let i = 0;
            const iterator = {
                [Symbol.iterator]: () => iterator,
                next: () => {
                    if (!link || (i !== 0 && link === this)) {
                        if (!link && this.circular && checkCircular)
                            throw new NonCircularError();
                        return { done: true, value: undefined };
                    }
                    const value = link;
                    link = forward ? link.next : link.prev;
                    i++;
                    return { done: false, value };
                },
            };
            return iterator;
        }
        iteratorCached(forward = true, checkCircular = true) {
            // return a custom iterator without using the links() generator:
            let link = this;
            let i = 0;
            const iteratorResult = { done: false, value: link };
            const iterator = {
                [Symbol.iterator]: () => iterator,
                next: () => {
                    if (!link || (i !== 0 && link === this)) {
                        if (!link && this.circular && checkCircular)
                            throw new NonCircularError();
                        iteratorResult.done = true;
                        iteratorResult.value = undefined;
                        return iteratorResult;
                    }
                    iteratorResult.value = link;
                    link = forward ? link.next : link.prev;
                    i++;
                    return iteratorResult;
                },
            };
            return iterator;
        }

        // 10 times slower than plain do-while loop (with for-of syntax).
        // [Symbol.iterator] = this.links

        // ~2.8 times slower than plain do-while loop (with for-of syntax).
        [Symbol.iterator] = this.iterator;

        // Surprisingly slower than iterator(), 3.3 times slower than plain do-while loop (with for-of syntax).
        // [Symbol.iterator] = this.iteratorCached;

        /**
         * Run a function for each Link in the linked list. If the function returns false, the loop stops.
         */
        // Also ~2.8 times slower than plain do-while loop.
        forEach(fn, forward = true, checkCircular = true) {
            let link = this;
            while (link) {
                const l = link;
                link = forward ? link.next : link.prev;
                if (this.circular && checkCircular && !link)
                    throw new NonCircularError();
                if (fn(l) === false)
                    break;
                if (link === this)
                    break; // circular done
            }
        }
        forEachReverse(fn, checkCircular = true) {
            this.forEach(fn, false, checkCircular);
        }
    };
}

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(), no-cache)
for (const link of startLink) {
	link
	globalThis.window
}
ready
do-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
while loop
let link = startLink
while (link) {
	link
	globalThis.window
	link = link.next
	if (link === startLink) break
}
ready
for-of generator
for (const link of startLink.links()) {
	link
	globalThis.window
}
ready

Revisions

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