Performance: Immutable.js Map vs List vs plain JS
JS engines are very good at optimising 'hot' operations - ones that get repeated a lot and that are as simple as possible (for instance TurboFan in V8). Plain JS objects and array functions are always going to beat a library like Immutable.js, where List calls Collection calls Seq calls Operations (and so on), especially when the actions are repeated many times.
Immutable.js appears to be designed for convenience of use and avoiding a lot of the nastyness of mutable JS collections, rather than pure performance.
If you have a million things, use a low level JS object or array (or Web Assembly, if performance is critical). If you have a thousand things and need to be certain of not dropping a frame then plain JS is still the way to go. These are specialised cases though - for most use cases the convenience of Immutable.js is worth the speed reduction.
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:
- The difference between
List.findvs.Array.findis not simply due to native (i.e. interpreter built-in) implementations vs. JS implementations, because a JS implementation ofArray.ourFindperforms at least as well asArray.find. - 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.
Immutable.List.findis ~6-fold slower thanArray.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.
The benchmark does not consider all the data types that Immutable has to offer. Immutable actually has some features, that plain objects/arrays do not: OrderedSet and OrderedMap have the benefits of both indexed arrays/List and key-based structures like object/Map.
Below is an adapted version of the nicely done test of @Keith, which shows that we can actually become faster than Array.find, especially with large data sets.
Of course, this comes at some cost too:
- Set/Map does not allow duplicates (not different to object though).
- Behind the scenes, the ordered variants combine a Map/Set with a list, so it consume more memory.
Note that OrderedSet are more expensive than non-ordered Set and may consume more memory. OrderedSet#add is amortized O(log32 N), but not stable.
function arrayFind(coll, searchVal) {
return coll.find(item => item === searchVal);
}
function immutableSetGet(coll, searchVal) {
return coll.get(searchVal);
}
function arrayRange(len) {
return new Array(len).fill(null).map((_, i) => i);
}
function immutOrderedSetRange(len) {
return Immutable.OrderedSet(arrayRange(len));
}
function timeFind(what, coll, find, iters) {
let startTime = performance.now();
let size = coll.length || coll.size;
for (let i = 0; i < iters; i++) {
let searchVal = i % size,
result = find(coll, searchVal);
}
return Math.floor(performance.now() - startTime);
}
const MIN_LEN = 100,
MAX_LEN = 1e5,
ITERS = 50000;
console.log('\t\t\tArray.find\tOrderedSet.find');
for (let len = MIN_LEN; len <= MAX_LEN; len *= 10) {
console.log(`${len}\t\t\t` +
`${timeFind('find', arrayRange(len), arrayFind, ITERS)}\t\t` +
`${timeFind('set', immutOrderedSetRange(len), immutableSetGet, ITERS)}`)
}<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.js"></script>Example results, in Chrome 86:
Array.find OrderedSet.find
100 10 18
1000 10 6
10000 74 10
100000 346 11