JavaScript的 `reduce` 性能

Question

最近我花了一些时间研究转换器（函数式编程中的工具，旨在提高性能并保持代码的可读性和灵活性），但当我测试它们的实际速度时，得到了一些令人失望的结果。比如：

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>

我预计性能顺序将是：

本地循环 > 转换器 > 链式map/filter

同时，除了本地方法比其他方法要快得多之外，令我惊讶的是，结果表明 reduce/transduce 方法比使用 map/filter 和创建中间数组要慢得多（在 Chrome 中慢一个数量级）。能否有人解释一下这个结果的起源？

- Michał Kaczanowicz

---

当你对微优化感兴趣时，只需坚持使用本地循环即可。这没有任何问题。 - user5536315

我的猜测是内置的Array#map和Array#filter等函数都是高度优化的本地代码，但转换器会受到许多函数调用开销的影响。必须在符号表中查找函数，创建堆栈帧，推送参数，跳转，返回结果...如果性能很重要，我同意Bob的观点-坚持使用本地和朴素的代码。即使性能不重要，转换器对我来说也不太可读，尽管我不是Scheme语言专家。const mapFilter = xs => xs.filter(isEven).map(inc);是惯用的、直接的和非巧妙的写法。 - ggorlen

顺便提一下，将 build 替换为 const build = (acc, x) => { return [...acc, x]; }; 以使其成为一个纯函数。 - Jawi

@MichałKaczanowicz 你说得对，只是我已经厌倦了所有与 FP 相关的性能问题。但你的具体问题并不属于这个范畴。我的错。 - user5536315

我认为你会喜欢如何正确顺序地链接、映射和过滤函数？ - Mulan

Answer 1

您的基准测试结果不准确，因为您每次运行时都在建立一个新的传输器链。

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>

正如您所看到的，传感器确实比链式的 map 和 filter 方法更快。

- Aadit M Shah

---

哇，我从来没有想过这几个简单的调用来构建一个reducer会对性能产生如此大的影响。谢谢！ - Michał Kaczanowicz

Answer 2

基准测试存在缺陷。 减少器不需要做任何工作。

创建一个统一的数组，其中包含奇数1。 然后对每个元素运行isEven函数。 总是返回一个空数组。

我们正在对返回空数组的性能进行基准测试。

如果我们使用真实数据预填数组，则本机方法将获胜。 尽管如此，Aadit的转换器是两个转换器实现中最快的。

const data = [];

for (let i = 0; i < 1000; i++) {
    data.push(Math.floor(Math.random() * 10));
}

- James Laux