ES6 generators vs iterators performance

#javascript #performance #benchmark

tldr;

ES6 generators allow iteration with very compact and clear code. However, this convenience comes with a price.

The example

Suppose we are writing general-purpose flatMap over iterables with the following signature:

function flatMap<T, U>(
    items: Iterable<T>,
    mapper: (item: T) => Iterable<U>
): Iterable<U>

Let's implement it with generators and iterators and make some races!

Generators

Look how nice and short is generators implementation. There's certainly no room for bugs!

function *flatMap<T, U>(
    items: Iterable<T>,
    mapper: (item: T) => Iterable<U>
): Iterable<U> {
    for (const item of items) {
        yield* mapper(item);
    }
}

Iterators

The implementation is somewhat more convoluted. A reader has to make few approaches to get it:

function flatMap<T, U>(
    items: Iterable<T>,
    mapper: (item: T) => Iterable<U>
): Iterable<U> {
    return {
        [Symbol.iterator]() {
            const outer = items[Symbol.iterator]();
            let inner: Iterator<U>;
            return {
                next() {
                    for ( ; ; ) {
                        if (inner) {
                            const i = inner.next();
                            if (!i.done) return i;
                        }

                        const o = outer.next();
                        if (o.done) {
                            return {
                                done: true,
                                value: undefined,
                            };
                        }
                        inner = mapper(o.value)[Symbol.iterator]();
                    }
                }
            };
        }
    }
}

Races!

Let's write a benchmark:

import * as Benchmark from 'benchmark';

import { flatMap as flatMapGen } from './flatMapGen';
import { flatMap as flatMapItr } from './flatMapItr';

let suite = new Benchmark.Suite();

[1, 10, 100, 1000, 10000, 100000].map(makeInput).forEach(input => {
    suite = suite.add(
        `Gen[${input.length}]`,
        () => consume(flatMapGen(input, i => [i, i + 1, i + 2])),
    );
    suite = suite.add(
        `Itr[${input.length}]`,
        () => consume(flatMapItr(input, i => [i, i + 1, i + 2])),
    );
});


suite
    .on('cycle', (event: Event) => console.log(String(event.target)))
    .run();

function makeInput(n: number) {
    const a = [];
    for (let i = 0; i < n; i++) a[i] = i * Math.random();
    return a;
}

function consume(itr: Iterable<number>) {
    let x = 0;
    for (const i of itr) x += i;
    if (x > 1e12) console.log('Never happens');
}

Results

Numbers are ops/s

n	Generators	Iterators	Winner
1	3,466,783	1,438,388	Generators are 2.4x faster
10	486,073	621,149	Iterators are 1.2x faster
100	58,009	102,465	Iterators are 1.8x faster
1,000	5,600	10,699	Iterators are 1.9x faster
10,000	557	1,115	Iterators are 2.0x faster
100,000	54.15	106	Iterators are 2.0x faster

Notes:

Node version is 14.8.0
Heap size is 4GB
Your numbers may differ, but for recent Node and Chrome proportions should be the same
In other browsers numbers are completely different, and generators are yet more slow

Why generators doing seemingly same are slower?

Unlike iterators, which are simple objects with state and closures, generators are suspended functions. Like threads in C++ or Java, they have their own execution stack, yet they don't run in parallel with the main thread: interpreter starts or resumes generator execution on next(), and resumes to the main thread on yields. This is sometimes called a “coroutine”, however it's not very common term in JS.

As n=1 shows, forking current stack is very cheap, even cheaper than creating several objects and closures. However, it turns out that switching stacks is more expensive than just dereferencing links and calling normal JS functions.

Conclusion: should I use generators?

If you feel that your code is complex and hard to understand if written otherwise — use generators! Remember, a good code is one that can be understood (and optimized if necessary).

However, for straightforward tasks like flatMap, for libs, and for frequently executed routines simple iterators are still a preferred option.