Old Comparative Performance

Let's start off by stating the obvious. Mutable collections are generally faster than immutable ones. That's a basic fact of life. Consider a hash table for example. A mutable hash map can simply replace a value in an internal array in response to a put() call while an immutable one has to create a number of new objects to build a new version of the map reflecting the change. So, yes, mutable collections are generally faster.

The real questions are: how much faster are mutable collections and will you really notice the difference. Based on benchmark runs a JImmutableHashMap is about 2-3 times slower than a HashMap but is about 1.5x faster than a TreeMap. Unless your application spends most of its time CPU bound updating collections you generally won't notice much of a difference using an immutable collection.

JMH Benchmarks

The following results from a JMH benchmark provide a broader notion of the relative performance of the java.util and jimmutable collections. The benchmarks perform a long series (about 500k) of insert/delete/get operations on each data type. In each case roughly 70% of the operations are gets, 20% are inserts, and the rest are deletes. The Score column contains the average number of complete loops per second.

Maps

Class/Factory	Mode	Count	Score	Error	Units
java.util.HashMap	thrpt	10	22.462	± 2.347	ops/s
JImmutables.array	thrpt	10	10.723	± 0.147	ops/s
JImmutables.map	thrpt	10	10.099	± 0.483	ops/s
---	---	---	---	---	---
java.util.LinkedHashMap	thrpt	10	21.785	± 1.310	ops/s
JImmutables.insertOrderMap	thrpt	10	8.049	± 0.086	ops/s
---	---	---	---	---	---
java.util.TreeMap	thrpt	10	4.528	± 0.413	ops/s
JImmutables.sortedMap	thrpt	10	2.678	± 0.030	ops/s

Sets

Class/Factory	Mode	Count	Score	Error	Units
java.util.HashSet	thrpt	10	23.573	± 2.720	ops/s
JImmutables.set	thrpt	10	10.384	± 0.124	ops/s
---	---	---	---	---	---
java.util.LinkedHashSet	thrpt	10	23.163	± 1.927	ops/s
JImmutables.insertOrderSet	thrpt	10	8.121	± 0.069	ops/s
---	---	---	---	---	---
java.util.TreeSet	thrpt	10	5.254	± 0.179	ops/s
JImmutables.sortedSet	thrpt	10	2.755	± 0.041	ops/s

Lists

Class/Factory	Mode	Count	Score	Error	Units
java.util.ArrayList	thrpt	10	37.136	± 0.128	ops/s
JImmutables.list	thrpt	10	25.004	± 0.121	ops/s

Relative Map performance

Here is a sample run using the org.javimmutable.collections.hash.TimingComparison benchmark program that comes with javimmutable-collections. The program uses a random number generator to create sequences of puts, gets, and deletes. The program can be tweaked in a variety of ways but the primary setting is the number of loops (operations) to perform. The program repeats the same series of random operations on a TreeMap<Inetger, Integer>, a JImmutables.map(), and a JImmutables.array(). These test runs were performed on a MacBook Pro with heap settings -Xms384m -Xmx512m.

-- subset of results for 250k ops run using TreeMap averages include many other runs
java map adds 74847 removes 24925 gets 150228 size 74814 elapsed 80
jimm map adds 74847 removes 24925 gets 150228 size 74814 elapsed 57
jimm ary adds 74847 removes 24925 gets 150228 size 74814 elapsed 50

java map adds 75044 removes 24846 gets 150110 size 75013 elapsed 80
jimm map adds 75044 removes 24846 gets 150110 size 75013 elapsed 55
jimm ary adds 75044 removes 24846 gets 150110 size 75013 elapsed 50

java map adds 75093 removes 24995 gets 149912 size 75050 elapsed 81
jimm map adds 75093 removes 24995 gets 149912 size 75050 elapsed 55
jimm ary adds 75093 removes 24995 gets 149912 size 75050 elapsed 51

java avg: 79.6  hash avg: 55.6  array avg: 50.0

As you can see the TreeMap completed 250,000 operations in about 80 milliseconds on average winding up with a map containing 75k elements. JImmutables.map() completed the same operations in 55 ms and JImmutables.array() in 50 ms. Using the same program a HashMap averages around 21 ms.

Increasing the number of operations to 500k (double) the average times are 52 ms for HashMap, 200 ms for TreeMap, 128 ms for JImmutables.map() and 118 ms for JImmutables.array(). The resulting collections contain approximately 150k elements. For the same run JImmutables.sortedMap() takes approximately 375 ms.

Cranking the number of operations up some more (1.5 million) we get these times: HashMap 262 ms, JImmutables.map() 530 ms, JImmutables.array() 476 ms. The final collection contained 448k elements. For these I used heap settings -Xms384m -Xmx768m.

-- subset of results for 1.5 million ops run using HashMap averages include many other runs
java map adds 449849 removes 149741 gets 900410 size 448534 elapsed 269
jimm map adds 449849 removes 149741 gets 900410 size 448534 elapsed 521
jimm ary adds 449849 removes 149741 gets 900410 size 448534 elapsed 466

java map adds 449889 removes 149428 gets 900683 size 448581 elapsed 267
jimm map adds 449889 removes 149428 gets 900683 size 448581 elapsed 517
jimm ary adds 449889 removes 149428 gets 900683 size 448581 elapsed 465

java map adds 450106 removes 149794 gets 900100 size 448768 elapsed 265
jimm map adds 450106 removes 149794 gets 900100 size 448768 elapsed 522
jimm ary adds 450106 removes 149794 gets 900100 size 448768 elapsed 462

java avg: 260.0  hash avg: 505.9  array avg: 456.2

Conclusions

From these test runs with maps it's clear that java.util.HashMap is wicked fast as would be expected but the fully immutable alternatives are still within a factor of 2-3 of it even for collections as large as 448k elements. Saying something is 2-3 times slower than something else sounds bad but keep in mind that this test performed one and a half million operations, wound up with a collection of 448k elements, and the difference in execution time between the best mutable and immutable versions was only about 245 milliseconds! In exchange for that quarter second your program would have all the benefits of immutability including:

• elimination of the need for locking or any potential for lock contention impacting performance
• elimination of the need for defensive copying or any potential for different parts of the program using the same map changing the data unexpectedly and breaking other parts of the program
• improvements in maintainability from ability to reason about how and when collections might change

If your program is CPU bound and works with enormous data structures it might require the use of mutable data structures. However for most programs switching to fully immutable data structures would have no noticeable effect on performance but would provide major benefits in the design and maintainability of the system.

Footnote - Sometimes immutable collections are faster

At the start of this article I said that mutable collections are generally faster than immutable ones. Sometimes they can be slower. Consider for example this extract from the RAListTimingComparison program.

STARTING TEST WITH seed 1001 loops 1000000 maxSize 1000 maxCommand 8
jlist adds 126812 sets 372285 removes 250384 gets 250519 size 1002 elapsed 154
ilist adds 126812 sets 372285 removes 250384 gets 250519 size 1002 elapsed 319

STARTING TEST WITH seed 1001 loops 1000000 maxSize 10000 maxCommand 8
jlist adds 135849 sets 363316 removes 250384 gets 250451 size 10000 elapsed 139
ilist adds 135849 sets 363316 removes 250384 gets 250451 size 10000 elapsed 275

STARTING TEST WITH seed 1001 loops 1000000 maxSize 17500 maxCommand 8
jlist adds 143323 sets 355915 removes 250345 gets 250417 size 17500 elapsed 264
ilist adds 143323 sets 355915 removes 250345 gets 250417 size 17500 elapsed 262

STARTING TEST WITH seed 1001 loops 1000000 maxSize 100000 maxCommand 8
jlist adds 225347 sets 274156 removes 250023 gets 250474 size 100000 elapsed 1113
ilist adds 225347 sets 274156 removes 250023 gets 250474 size 100000 elapsed 391

In this output the jlist lines give results for using the mutable java.util.ArrayList and ilist lines give results for using the immutable JImmutableBtreeList. This benchmark performs random inserts, deletes, and gets at random indexes in the list. It tests the ability of a collection to handle mutations within the middle of a list, not just at the ends.

Notice that for small lists the ArrayList class is, as expected, faster than its immutable rival. But for large lists the immutable collection is significantly faster than ArrayList! How is this possible? This is an example of when algorithm wins over implementation. The ArrayList class maintains a single large array of values so whenever inserts and deletes are done in the middle of the array values have to be shifted left or right. In contrast JImmutableBtreeList uses a b-tree as its data structure. Unlike an array a b-tree doesn't have any preference for where values are added. Inserting a value in the middle of a b-tree is no more expensive than inserting one at the beginning or end. The break-even point on my Macbook is ~17.5k elements.