Performance: Immutable.js Map vs List vs plain JS

Question

Question

Is there something wrong with my benchmark? How can Immutable.js find() be 8 times slower than array.find()?

Ok, not entirely fair, since I'm using Immutable.Map inside of the Immutable.List. But to me this is a real world example. If I use Immutable.js it's to protect immutability and to gain performance in some aspects (where structural sharing come to play). The would be no point in using Immutable.js only at the root of the object.

The below benchmark is actually from another question (mine as well). I was so surprised by the results, I had to post it separately to get it straight. Have I done something wrong in my benchmarks, or is the performance difference really this big?

Background

Some of the data in my app could be considered app metadata. The original data lives in a database at the server. Updates to the metadata will not be done often. The app will check for updated metadata on startup.

I'm using Immutable.js everywhere, but I will go back to plain js for the metadata. There is no need for fancy structural sharing for this kind of data.

The test is to find values by key in a collection

• Collection of 10 items

• Find a value one million times

• Mac mini core i7 2.6

Result:

• Plain JS object with coerced keys: 8 ms

• Plain JS array using find(): 127 ms

• Immutable.Map with numeric keys: 185 ms

• Immutable.List using find(): 972 ms !! I'm baffled

As I'm using React Native I always have to look out for the 16 ms limit if I want to achieve 60 fps. The benchmark values does not seem to be linear. Running the test with only 100 lookups takes 1 ms with Map and 2 ms with List. That's quite expensive.

Test code

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

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.