3

I always hear people saying that it's easier to manage immutable objects when working with multiple threads since when one thread accessed an immutable object, it doesn't have to worry that another thread is changing it.

Well, what happens if I have an immutable list of all employees in a company and a new employee is hired? In this case the immutable list has to be duplicated and the new copy of it has to include another employee object. Then the reference to list of employees should be directed to the new list.

When this scenario happens, the list itself doesn't change, but the reference to this list changes, and therefore the code "sees" different data.

If so, I don't understand why immutable objects makes our lives easier when working with multi-threads. What am I missing?

CrazySynthax
  • 13,662
  • 34
  • 99
  • 183
  • 1
    There is no possibility of an inconsistency. Any thread will work on either, the old reference or the new reference, but never a mixture of new and old data. – Holger Aug 27 '18 at 11:18
  • http://jeremymanson.blogspot.com/2008/04/immutability-in-java.html – Eugene Aug 27 '18 at 12:23

2 Answers2

4

The main problem concurrent updates of mutable data, is that threads may perceive variable values stemming from different versions, i.e. a mixture of old and new values when speaking of a single update, forming an inconsistent state, violating the invariants of these variables.

See, for example, Java’s ArrayList. It has an int field holding the current size and a reference to an array whose elements are references to the contained objects. The values of these variables have to fulfill certain invariants, e.g. if the size is non-zero, the array reference is never null and the array length is always greater or equal to the size. When seeing values of different updates for these variables, these invariants do not hold anymore, so threads may see a list contents which never existed in this form or fail with spurious exceptions, reporting an illegal state that should be impossible (like NullPointerException or ArrayIndexOutOfBoundeException).

Note that thread safe or concurrent data structures only solve the problem regarding the internals of the data structure, so operations do not fail with spurious exceptions anymore (regarding the collection’s state, we’ve not talked about the contained element’s state yet), but operations iterating over these collections or looking at more than one contained element in any form, are still subject to possibly observing an inconsistent state regarding the contained elements. This also applies to the check-then-act anti-pattern, where an application first checks for a condition (e.g. using contains), before acting upon it (like fetching, adding or removing an element), whereas the condition might change in-between.

In contrast, a thread working on an immutable data structure may work on an outdated version of it, but all variables belonging to that structure are consistent to each other, reflecting the same version. When performing an update, you don’t need to think about exclusion of other threads, it’s simply not necessary, as the new data structures are not seen by other threads. The entire task of publishing a new version reduces to the task of publishing the root reference to the new version of your data structure. If you can’t stop the other threads processing the old version, the worst thing that can happen, is that you may have to repeat the operation using the new data afterwards, in other words, just a performance issue, in the worst case.

This works smooth with programming languages with garbage collection, as these allow it to let the new data structure refer to old objects, just replacing the changed objects (and their parents), without needing to worry about which objects are still in use and which not.

Holger
  • 285,553
  • 42
  • 434
  • 765
  • Say I have 3 threads adding to the same immutable list. So each thread will have its own list (all they share is an initial empty list) - and now what? You still need some form of synchronization to evaluate collected data. What is a difference with having per-thread mutable list? – uuu777 Jan 19 '19 at 01:58
  • 1
    @zzz777 you can’t have “3 threads adding to the same immutable list”. Being an immutable list implies that adding to it is impossible. Redesigning software to not work by mutating data is a big challenge and not necessarily possible for all kind of tasks. Of course, for a thread which wants to manipulate a list, a local, mutable list is a great tool and also immune to data races, but that’s not connected to the discussion about shared data structures, concurrently accessed by multiple threads. – Holger Jan 21 '19 at 07:58
  • It seems to me that it possible to add to immutable list - you will get reference to a new list after each addition. – uuu777 Jan 25 '19 at 01:10
  • 1
    @zzz777 you can perform arbitrary operations producing a new list, including producing a new list with more elements than the old. As said in the answer, the critical operation is the publishing of the new list, typically an atomic exchange of the references. If a compare-and-set fails, it implies that your operation was based on outdated data, hence, you have to do it again. As the answer said, “*the worst thing that can happen, is that you may have to repeat the operation using the new data afterwards*”. Readers will always see a consistent list. So this works best with only a few updaters. – Holger Jan 25 '19 at 11:15
  • Some pointer to some expanded real-life like examples may help. I did a fair share of scala classes to understand the basics, but the real life benefits are still unclear. – uuu777 Jan 25 '19 at 18:22
0

Here is an example: (a) we have a immutable list, (b) we have writer thread that adds elements to the list and (c) 1000 read threads that read the list without changing it.

It will work without locks.

If we have more than one writer thread we will still need a write lock. If we have to remove entries from the list we will need read-write lock.

Is it valuable? Do not know.

uuu777
  • 765
  • 4
  • 21