Performance: Immutable.js Map vs List vs plain JS

The short answer is that the representation of data structures used by Immutable.js requires a lot of additional overhead to iterate through the elements of a List, compared to a native JS array.

Benchmarking Immutable.List.find and Array.find

Your benchmark is good, but we can simplify matters a bit by getting rid of the nested map; you’re right to consider performance for realistic problems, but it can be helpful in understanding performance differences to simplify the problem as much as possible. It’s also often useful in benchmarking to consider how performance changes over different input sizes. For instance, it’s possible that in Immutable.js, List.prototype.find is implemented in such a way that the intitial call and setup take awhile but that the subsequent iterating through the List performs similarly to native JS Arrays; in this case, the difference in performance between native JS Arrays and Immutable.js lists would decrease for long input lengths (this turns out not to be the case).

Let’s also create our own find function for native JS arrays, Array.prototype.ourFind to compare to the native Array.prototype.find to determine if the difference could in part be due to the performance of JS functions themselves vs. performance of functions built-in to the implementation.

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>

In Chrome, I get:

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

I got roughly similar results in Firefox and Safari. A few points to note:

1. The difference between List.find vs. Array.find is not simply due to native (i.e. interpreter built-in) implementations vs. JS implementations, because a JS implementation of Array.ourFind performs at least as well as Array.find.
2. All implementations work in O(n) time (i.e. execution time is linear with respect to input length). This is to be expected, since a find algorithm will always have to work by iterating through the collection elements until it finds one for which the predicate returns true.
3. Immutable.List.find is ~6-fold slower than Array.find, consistent with your benchmarking results.

Immutable.List data representation

To understand why Immutable.List.find is so much slower, you first have to consider how Immutable.List represents the list contents.

A quick way to do this is to generate an Immutable.List and examine it in the console:

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

So essentially it looks like Immutable.List represents the contents as a tree with a branching factor of 32.

Now consider what it will take to run a find operation on data that are represented in this way. You will have to start at the root node, and traverse the tree down to the first leaf node (which contains an Array with the actual data), and iterate through the contents of the leaf; if the element is not found, you have to go to the next leaf node and search that Array, and so on. It’s a more complex operation than merely searching through a single array, and it requires overhead to execute.

Watching Immutable.List.find at work

A great way to appreciate the work that Immutable.List.find does is to set a break point in your debugger of choice and step through the operation. You’ll see that Immutable.List.Find is not nearly as simple an operation as merely looping through a single Array.

Additional comments

The tree representation of data in Immutable.js presumably accelerates other operations, but entails a performance penalty with some functions, such as find.

As a side note, I don’t think in most cases that the choice to use immutable data structures is driven by performance considerations. There may be some cases where immutable data structures perform better than mutable ones (and certainly immutable data structures make parallel computing less complex, which enables significant performance gain), but there will be many cases when the opposite is true. Rather, the choice of immutability is, in most cases, driven by design considerations–i.e. using immutable data structures forces program designs that will be more robust and, in the long run, increase developer productivity.