Are Immutable Collections Inherently Less Efficient

Question

Immutable objects are objects that cannot change state. They can be easier to test and debug, and are very useful in concurrent programming. However, current implementations of immutable collections have poor performance compared to their mutable relatives. For example, implementing an associative array as an immutable red-black tree has on average O(log(n)) Insert/Delete, while a hash table has on average O(1) Insert/Delete.

In general, are immutable collections provably less efficient than their mutable cousins, or will we someday find immutable implementations that are just as fast?

Answer 1

Okasaki demonstrates that it is often possible to develop immutable data structures "with equivalent asymptotic performance" as their imperative counterparts. Likely the immutables structures have worse constants, however. But what you may pay for in performance you do get back in programmer time; as you said, it is much easier to work with and understand immutable collections. In this way the question is somewhat similar to the recurring question as to why we use other languages when C is so fast. Because it is easier and we value programmer time.