性能:Immutable.js Map vs List vs plain JS

Question

题

我的基准测试有问题吗？Immutable.js find()如何比array.find()慢8倍？

好吧,不完全公平,因为我在Immutable.List中使用Immutable.Map.但对我来说,这是一个现实世界的例子.如果我使用Immutable.js,那就是保护不变性并在某些方面获得性能(结构共享起作用).仅在对象的根处使用Immutable.js是没有意义的.

以下基准实际上来自另一个问题(我的也是).我对结果感到非常惊讶,我不得不单独发布以使其顺利进行.我在基准测试中做错了什么,或者性能差异真的很大吗？

背景

我的应用中的一些数据可以被视为应用元数据.原始数据位于服务器的数据库中.不会经常更新元数据.该应用程序将在启动时检查更新的元数据.

我到处都在使用Immutable.js,但我会回到简单的js来获取元数据.对于这种数据,不需要花哨的结构共享.

测试是按集合中的键查找值

• 收集10件物品

• 找到一百万次的价值

• Mac mini核心i7 2.6

结果:

• 带有强制密钥的普通JS对象:8毫秒

• 使用find()的普通JS数组:127毫秒

• Immutable.Map与数字键:185毫秒

• 使用find()的Immutable.List:972毫秒 !! 我很困惑

因为我正在使用React Native,如果我想达到60 fps,我总是要注意16 ms的限制.基准值似乎不是线性的.仅使用100次查找运行测试需要1 ms的Map和2 ms的List.那太贵了.

测试代码

let Immutable = require('immutable');

let mapTest = Immutable.Map()
  .set(1, Immutable.Map({value: 'one'}))
  .set(2, Immutable.Map({value: 'two'}))
  .set(3, Immutable.Map({value: 'three'}))
  .set(4, Immutable.Map({value: 'four'}))
  .set(5, Immutable.Map({value: 'five'}))
  .set(6, Immutable.Map({value: 'six'}))
  .set(7, Immutable.Map({value: 'seven'}))
  .set(8, Immutable.Map({value: 'eight'}))
  .set(9, Immutable.Map({value: 'nine'}))
  .set(10, Immutable.Map({value: 'ten'}));

let listTest = Immutable.fromJS([
  {key: 1,  value: 'one'},
  {key: 2,  value: 'two'},
  {key: 3,  value: 'three'},
  {key: 4,  value: 'four'},
  {key: 5,  value: 'five'},
  {key: 6,  value: 'six'},
  {key: 7,  value: 'seven'},
  {key: 8,  value: 'eight'},
  {key: 9,  value: 'nine'},
  {key: 10, value: 'ten'}
])

let objTest = {
  1:  {value: 'one'},
  2:  {value: 'two'},
  3:  {value: 'three'},
  4:  {value: 'four'},
  5:  {value: 'five'},
  6:  {value: 'six'},
  7:  {value: 'seven'},
  8:  {value: 'eight'},
  9:  {value: 'nine'},
  10: {value: 'ten'}
};

let arrayTest = [
  {key: 1,  value: 'one'},
  {key: 2,  value: 'two'},
  {key: 3,  value: 'three'},
  {key: 4,  value: 'four'},
  {key: 5,  value: 'five'},
  {key: 6,  value: 'six'},
  {key: 7,  value: 'seven'},
  {key: 8,  value: 'eight'},
  {key: 9,  value: 'nine'},
  {key: 10, value: 'ten'}
];

const runs = 1e6;
let i;
let key;
let hrStart;

console.log(' ')
console.log('mapTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = mapTest.getIn([key, 'value'] )
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);


console.log(' ')
console.log('listTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = listTest
    .find(item => item.get('key') === key)
    .get('value');
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

console.log(' ')
console.log('arrayTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = arrayTest
    .find(item => item.key === key)
    .value

  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);


console.log(' ')
console.log('objTest -----------------------------')
key = 1;
hrstart = process.hrtime();
for(i=0; i<runs; i++) {
  let result = objTest[key].value
  key = (key >= 10) ? 1 : key + 1;
}
hrend = process.hrtime(hrstart);
console.info("Execution time (hr): %dms", hrend[0] * 1000 + hrend[1]/1000000);

Answer 1

简而言之,与原生JS数组相比,Immutable.js使用的数据结构的表示需要大量额外开销来迭代List的元素.

对Immutable.List.find和Array.find进行基准测试

你的基准测试很好,但我们可以通过摆脱嵌套的地图来简化一些事情; 你应该考虑现实问题的性能,但它有助于理解性能差异,以尽可能简化问题.在基准测试中,通常也可以考虑性能如何随不同输入大小而变化.例如,在Immutable.js中,List.prototype.find有可能以这样的方式实现,即初始调用和设置需要一段时间,但后续迭代通过List执行类似于本机JS数组; 在这种情况下,对于长输入长度,本机JS数组和Immutable.js列表之间的性能差异会减小(事实证明并非如此).

我们还为本机JS数组创建自己的查找函数,与本机Array.prototype.ourFind进行比较,Array.prototype.find以确定差异是否部分归因于JS函数本身的性能与内置于实现的函数的性能.

Array.prototype.ourFind = function(predicate) {
  for (let i = 0; i < this.length; i++) {
    if (predicate(this[i])) return this[i];
  }
}

function arrayRange(len) {
  return new Array(len).fill(null).map((_, i) => i);
}

function immutListRange(len) {
  return Immutable.fromJS(arrayRange(len));
}

function timeFind(coll, find, iters) {
  let startTime = performance.now();
  for (let i = 0; i < iters; i++) {
    let searchVal = i % coll.length,
      result = find.call(coll, item => item === searchVal);
  }
  return Math.floor(performance.now() - startTime);
}

const MIN_LEN = 10,
  MAX_LEN = 1e4,
  ITERS = 1e5;

console.log('\t\tArray.find\tArray.ourFind\tList.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
  console.log(`${len}\t\t\t` +
    `${timeFind(arrayRange(len), Array.prototype.find, ITERS)}\t\t\t` +
    `${timeFind(arrayRange(len), Array.prototype.ourFind, ITERS)}\t\t\t` +
    `${timeFind(immutListRange(len), Immutable.List.prototype.find, ITERS)}`)
}

<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>

在Chrome中,我得到:

Length .    Array.find  Array.ourFind   List.find
10          28          13              96
100         60          44              342
1000        549         342             3016
10000       5533        3142            36423

我在Firefox和Safari中获得了大致相似的结果.需要注意的几点:

1. List.findvs 之间的区别Array.find不仅仅是由于本机(即内置解释器)实现与JS实现,因为JS实现的Array.ourFind性能至少与Array.find.
2. 所有实现都在O(n)时间内工作(即,执行时间相对于输入长度是线性的).这是可以预料到的,因为find算法总是必须通过遍历集合元素来工作,直到找到谓词返回true的那个元素.
3. Immutable.List.find比Array.find您的基准测试结果慢约6倍.

Immutable.List数据表示

要理解为什么Immutable.List.find这么慢,首先要考虑如何Immutable.List表示列表内容.

快速执行此操作的方法是Immutable.List在控制台中生成并检查它:

console.log(immutListRange(1000));  // immutListRange defined above

所以基本上它看起来像Immutable.List将树的内容表示为分支因子为32的树.

现在考虑对以这种方式表示的数据运行查找操作需要什么.您必须从根节点开始,并将树遍历到第一个叶节点(其中包含具有实际数据的Array),并遍历叶的内容; 如果找不到该元素,则必须转到下一个叶节点并搜索该数组,依此类推.这比仅仅搜索单个数组更复杂,并且需要执行开销.

在工作中观察Immutable.List.find

欣赏这项工作的一个好方法Immutable.List.find是在您选择的调试器中设置一个断点并逐步完成操作.您将看到,这Immutable.List.Find不仅仅是循环单个数组的操作.

附加评论

Immutable.js中的数据树表示可能会加速其他操作,但会导致某些函数(例如find)的性能损失.

作为旁注,我认为在大多数情况下,使用不可变数据结构的选择是由性能考虑因素驱动的.可能存在一些情况,其中不可变数据结构比可变数据结构表现更好(当然,不可变数据结构使并行计算不那么复杂,这可以显着提高性能),但是在相反的情况下会有很多情况.相反,在大多数情况下,不可变性的选择是由设计考虑因素驱动的 - 即使用不可变数据结构迫使程序设计更加健壮,并且从长远来看,可以提高开发人员的工作效率.

Answer 2

JS引擎非常擅长优化"热"操作 - 那些重复很多且尽可能简单的操作(例如V8中的TurboFan).简单的JS对象和数组函数总是打败像Immutable.js这样的库,其中List调用Collection调用Seq调用Operations(等等),特别是当动作重复多次时.

Immutable.js似乎是为了方便使用而设计的,并且避免了可变JS集合的许多讨厌,而不是纯粹的性能.

如果您有一百万件事,请使用低级JS对象或数组(或Web组件,如果性能至关重要).如果你有一千件东西需要确定不丢帧,那么普通的JS仍然是要走的路.这些是特殊情况 - 对于大多数用例,Immutable.js的便利性值得降低速度.