DEV Community

Aleksei Berezkin
Aleksei Berezkin

Posted on

ES6 generators vs iterators performance

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>
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

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]();
                    }
                }
            };
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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');
}
Enter fullscreen mode Exit fullscreen mode

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.

Happy coding!

Top comments (2)

Collapse
 
beqa profile image
beqa

very helpful article! (If you received another notification from me on this article, never mind, I did stupid)

Collapse
 
alekseiberezkin profile image
Aleksei Berezkin

Happy you liked it