ES6 generators vs iterators performance
Tags: javascript, performance, benchmark
Published: 2020-09-07 19:30:01

# 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:

```typescript
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!

```typescript
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:

```typescript
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:


```typescript
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 `yield`s. 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!