Why is equals slow in this Immutable JS test?

Question

I'm doing some sanity testing on a personal project before updating some state to use ImmutableJS. I have a small test I wrote to make sure that Immutable.List.equals performs like I expect it should -- O(1).

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

The important part is below

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));

The test is comparing two native js lists of size 100,000 and then two Immutable.List of size 100,000, each 1000 times. I must be missing something. I'm seeing the Immutable.List sample perform very bad relative to the native list sample.

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

You can run this locally with the following.

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

If I'm making a simple mistake then I'd appreciate some eyes to let me know where it is. I definitely expected this to be very fast. Especially because replacing l1.equals(l2) with a call to l1.hashCode() is really fast.

Answer 1

According to the 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.

This means that it can't be O(1) because it needs to check the equality of all the values in the list. This is going to be substantially slower (as you have found).

The performance tradeoff is also documented:

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

I think this could be classified as user error on my part. I was used to immutability in languages where it's a first class citizen and it didn't map will onto JS with ImmutableJS. My mistakes were (at least) as follows.

First, .equals() is a deep equal by design and it isn't what you should be relying on to implement performant equality checks in something like a shouldComponentUpdate call in React.

Second, to get the most out of ImmutableJS, you need to use its API correctly. Here is an example.

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))  

Third, when using this with React with the intention of using PureComponent which does a shallow, reference equality check, you need to make sure that you're going to end up with reference equality (like in the example above).

Finally, sometimes you need to execute expensive functions on your app state in React just to be able to get the props for your component. In order to avoid doing that for no reason you can use something like Lodash's memoize in combination with reference equality on immutable objects like in the following contrived example.

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

If someone spots some errors here (or missing errors) then please point them out and I'll update the explanation.