3

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?

Joshua
  • 2,431
  • 15
  • 23
  • @JoachimPileborg noted and fixed to average efficiency. – Joshua May 18 '14 at 19:56
  • possible duplicate of [How does one implement hash tables in a functional language?](http://stackoverflow.com/questions/6793259/how-does-one-implement-hash-tables-in-a-functional-language) (at least one answer writes about performance there) – Sylwester May 19 '14 at 17:16
  • 2
    possible duplicate of [Efficiency of purely functional programming](http://stackoverflow.com/questions/1990464/efficiency-of-purely-functional-programming) –  May 20 '14 at 09:50
  • 1
    TL;DR for strict purely functional languages (in a certain model of computation that may or may not be universally applicable), there is a O(log n) slowdown factor, for lazy purely functional language there is no proof or disprove of an asymptotic slowdown. –  May 20 '14 at 10:04

1 Answers1

2

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.

Zach Halle
  • 321
  • 1
  • 9