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 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.
Top comments (2)
very helpful article! (If you received another notification from me on this article, never mind, I did stupid)
Happy you liked it