I've spent some time recently plying around with transducers (tool in functional programming meant to improve performance without losing readability/flexibility of code) and when I came to testing their actual speed, I got some quite disappointing results. Consider:
const inc = x => x + 1;
const isEven = x => x % 2 === 0;
// simplest, shortest way I would be comfortable with if performance wasn't an issue
const mapFilter = xs => xs.filter(isEven).map(inc);
// transducers way
// function composition
const compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x);
const map = f => step => (a, c) => step(a, f(c));
const filter = p => step => (a, c) => (p(c) ? step(a, c) : a);
// basic reducer for building array
const build = (acc, x) => {
acc.push(x);
return acc;
};
// transducer, it doesn't create intermediate arrays hence should theoretically be faster
const transducers = xs =>
xs.reduce(compose(filter(isEven), map(inc))(build), []);
// native loop for comparison
const nativeLoop = data => {
const result = [];
const l = data.length;
for (let i = 0; i < l; i++) {
const x = data[i];
if (isEven(x)) result.push(inc(x));
}
return result;
};
const data = Array(1000).fill(1);
const base = ["simplest, chained map and filter", () => mapFilter(data)];
const alternative = ["composed transducers", () => transducers(data)];
const alternative2 = ["native loop", () => nativeLoop(data)];
/* console.log(Benchmark) */
console.log("Running benchmarks....");
const suite = new Benchmark.Suite();
suite
.add(...base)
.add(...alternative)
.add(...alternative2)
.on("cycle", function(event) {
console.log(String(event.target));
})
.on("complete", function() {
console.log("Fastest is " + this.filter("fastest").map("name").join(", "));
})
// run async
.run({ async: true });<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>I would expect that the order of performance will be
native loop > transducers > chained map/filter
Meanwhile, besides native approach which is way faster than any other, it turned out, to my great astonishment, that reduce/transduce way is much slower than using map/filter and creating intermediate arrays (slower, like an order of magnitude in Chrome). Could someone explain to me the origin of this result?
Your benchmark is wrong because you're building a new transducer chain on each run.
const inc = x => x + 1;
const isEven = x => x % 2 === 0;
// simplest, shortest way I would be comfortable with if performance wasn't an issue
const mapFilter = xs => xs.filter(isEven).map(inc);
// transducers way
// function composition
const compose = (...fns) => x => fns.reduceRight((y, f) => f(y), x);
const map = f => step => (a, c) => step(a, f(c));
const filter = p => step => (a, c) => (p(c) ? step(a, c) : a);
// basic reducer for building array
const build = (acc, x) => {
acc.push(x);
return acc;
};
// transducer, it doesn't create intermediate arrays hence should theoretically be faster
const reducer = compose(filter(isEven), map(inc))(build);
const transducers = xs => xs.reduce(reducer, []);
// native loop for comparison
const nativeLoop = data => {
const result = [];
const l = data.length;
for (let i = 0; i < l; i++) {
const x = data[i];
if (isEven(x)) result.push(inc(x));
}
return result;
};
const data = Array(1000).fill(1);
const base = ["simplest, chained map and filter", () => mapFilter(data)];
const alternative = ["composed transducers", () => transducers(data)];
const alternative2 = ["native loop", () => nativeLoop(data)];
/* console.log(Benchmark) */
console.log("Running benchmarks....");
const suite = new Benchmark.Suite();
suite
.add(...base)
.add(...alternative)
.add(...alternative2)
.on("cycle", function(event) {
console.log(String(event.target));
})
.on("complete", function() {
console.log("Fastest is " + this.filter("fastest").map("name").join(", "));
})
// run async
.run({ async: true });<script src="https://cdnjs.cloudflare.com/ajax/libs/lodash.js/4.17.15/lodash.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/benchmark/2.1.4/benchmark.min.js"></script>As you can see, transducers are indeed faster than chained map and filter methods.