为什么在这个 Immutable JS 测试中 equals 很慢？

Question

在更新某些状态以使用 ImmutableJS 之前，我正在对个人项目进行一些健全性测试。我写了一个小测试来确保 Immutable.List.equals 像我期望的那样执行——O(1).

https://github.com/naddeoa/immutablejs-slow-equals.git

重要部分如下

function compareImmutableMany(l1, l2) {
  let result = false;
  for (let i = 0; i < iterations; i++) {
    result = l1.equals(l2);
  }
  return result;
}

i1 = createImmutableList();
i2 = createImmutableList();
console.log("immutable lists are equal", compareImmutableMany(i1, i2));

测试正在比较两个大小为 100,000 的原生 js 列表，然后比较两个大小为 100,000 的 Immutable.List，每个 1000 次。我肯定错过了什么。我发现 Immutable.List 样本相对于本机列表样本表现非常糟糕。

starting
immutable lists are equal true
Seconds: 11.423
starting
normal lists are equal: true
Seconds: 0.109

您可以运行在本地使用以下内容。

git clone https://github.com/naddeoa/immutablejs-slow-equals.git
cd immutablejs-slow-equals
npm i
node main.js

如果我犯了一个简单的错误，那么我会感谢一些眼睛让我知道它在哪里。我绝对希望这会非常快。特别是因为用对 l1.hashCode() 的调用替换 l1.equals(l2) 真的很快。

Answer 1

根据 docs:

Two immutable collections are considered value equal (via .equals() or is()) if they represent the same collection of values. This differs from JavaScript's typical reference equal (via === or ==) for Objects and Arrays which only determines if two variables represent references to the same object instance.

这意味着它不能是 O(1) 因为它需要检查列表中所有值的相等性。这将大大降低速度（如您所见）。

还记录了性能权衡：

When comparing two collections, value equality may require considering every item in each collection, on an O(N) time complexity. For large collections of values, this could become a costly operation. Though if the two are not equal and hardly similar, the inequality is determined very quickly. In contrast, when comparing two collections with reference equality, only the initial references to memory need to be compared which is not based on the size of the collections, which has an O(1) time complexity. Checking reference equality is always very fast, however just because two collections are not reference-equal does not rule out the possibility that they may be value-equal.

Answer 2

我认为这可能 class我认为是用户错误。我已经习惯了语言中的不变性，它是第一个 class 公民，它没有使用 ImmutableJS 将意志映射到 JS 上。我的错误（至少）如下。

首先，.equals() 是一个深度相等的设计，它不是你应该依赖的东西来实现性能相等检查，比如 React 中的 shouldComponentUpdate 调用。

其次，要充分利用 ImmutableJS，您需要正确使用它的 API。这是一个例子。

const Foo = Immutable.Record({a:1})

const foo1 = Foo({a:2})
const foo2 = Foo({a:2})

const cache = Immutable.Map({'key': foo1})

// Doing it this way will force you to either use .equals() or .hashCode() 
// to check for changes later
const wrongWay = cache.set('key', foo2)
console.log('This is false', wrongWay === cache) 
console.log('This is true', wrongWay.hashCode() === cache.hashCode()) 
console.log('This is true and slow', wrongWay.equals(cache))  

// Doing it this way will let you rely in reference equality
const rightWay = cache.mergeDeep({'key': foo2})
console.log('This is true', rightWay === cache) 
console.log('This is true, but not needed', rightWay.hashCode() === cache.hashCode()) 
console.log('This is true and slow, but not needed', rightWay.equals(cache))

第三，当将此与 React 一起使用并打算使用 PureComponent 进行浅层引用相等性检查时，您需要确保最终会得到引用相等性（如上例所示） .

最后，有时您需要在 React 中对您的应用程序状态执行昂贵的功能，以便能够为您的组件获取 props。为了避免无缘无故地这样做，您可以将 Lodash 的 memoize 之类的东西与不可变对象的引用相等性结合使用，如以下人为设计的示例。

const myFunction = _.memoize((immutableAppState) => {
    return immutableAppState.immutableList.map(/* really expensive stuff returning new immutable objects based on other selectors */)
}, (immutableAppState) => immutableAppState.specificRecordThatChanges )

如果有人发现这里有错误（或遗漏的错误）请指出，我会更新解释。

为什么在这个 Immutable JS 测试中 equals 很慢？

Why is equals slow in this Immutable JS test?

javascript

performance

immutable.js