6

Okay so I read through this:

Does immutability entirely eliminate the need for locks in multi-processor programming?

And this was the main takeaway for me:

Now, what does it get you? Immutability gets you one thing: you can read the immutable object freely, without worrying about its state changing underneath you

But that was only regarding reading.

What happens when two threads are trying to generate a new shared state? Lets say they're both reading some immutable number N, and want to increment it. They can't mutate it directly so the both generate two completely new values at the same time both of which are just N + 1.

How do you reconcile this problem so that the shared state becomes N + 2? Or am I missing something and that's not how it works?

  • Would the algorithm not be completely different with multiple threads calculating their results then a summation etc – Richard Tingle Apr 26 '16 at 20:54
  • Why are multiple threads needing to increment this number? – Winston Ewert Apr 26 '16 at 20:59
  • 2
    I suspect that your question has more to do with atomicity and how it relates to immutable types in a multithreaded environment. Consider reading the following: blogs.msdn.microsoft.com/ericlippert/2011/05/26/… – ravibhagw Apr 26 '16 at 21:04
  • 1
    @ar7 - the thing is that you don't know how other threads are using your data if it is mutable. You need to lock even for non-atomic reads then. The reason people only talk about reading is because that is all immutability helps. – Telastyn Apr 26 '16 at 23:35
  • 1
    Yeah, and with concurrency, you need 0%, or else you're chasing random failures forever. Also, I updated my answer to better include some of the comments from here and elsewhere. – Telastyn Apr 27 '16 at 1:28
8

So I think that we need to eliminate the term "shared state" from your question, because shared state is almost diametrically opposed to the notion of using immutability to avoid locking.

In your example, you basically said that both read some value "N" and both create a new object with a value "N+1".

The key is that you wouldn't necessarily save the value "N+1". Rather, you would save the values "N" and "+1" inside both threads 1 and 2. In other words, you would save a reference to the original value you read as well as the modification that you made to it.

Now, the "shared state" should instead be a 3rd thread that reconciles the two (very often this 3rd thread is the thread that originally created the first 2). When reconciling the two "N+1" values, it should see that both started with "N" and both did a modification of "+1". The final result is "N+2".

It is important to recognize that "N+2", when saved, will also be a new immutable object that cannot be changed. It is this lack of this "shared state" that allows you to avoid the need for locks.

  • Why do you need immutability to achieve this? If the operation is decoupled from the value can't you pass around the (+1)s like you described and mutate the original value anyways? Is there a better, more complex situation that better conveys the benefits? – m0meni Apr 26 '16 at 21:27
  • 2
    @AR7, Passing around values is the most common way I've seen this done (whenever I do this pattern, I just accept immutable function parameters and return results). When you do this however, you are still not modifying the original values, and therefore your algorithm is still basically immutable. The basic idea is that if you are never changing memory, you can automatically parallelize with no limitations. On a quad core machine, this doesn't sound like a big deal. But the potential to do super-computer scale algorithm work with no race conditions or corrupt values is ... appealing :) – riwalk Apr 26 '16 at 21:35
  • @AR7 there is a related discussion: Performance of single-assignment ADT oriented code on modern CPUs – gnat Apr 27 '16 at 0:11
  • With one thread aggregating data you lose parallelism at this stage though. – Stephan Schmidt Jun 12 at 10:12
  • @StephanSchmidt Depends heavily on how you are aggregating data. A typical divide-and-conquer style algorithm (like map/reduce) will allow you to keep parallelism for quite a long time. – riwalk Jun 12 at 21:40
6

What happens when two threads are trying to generate a new shared state?

Let's be clear about what I understand your question to be:

You have some mutable variable of immutable state. Let's use an int for simplicity:

int x = 42;

Then you want two threads to both try to increment x by 1.

Then you get to synchronize them. Immutability provides little value here.

All immutability guarantees is that the variable you're reading from isn't in some half-way state when read. Since x is atomic, this doesn't make much sense. Any read you do will get the whole value.

But since you're mutating the variable x, you need synchronization even though the value is immutable. Each thread is making 2 atomic operations:

y = read x;
write x with y+1;

If both threads read before write, then both threads will see x, not x+1. So you need to synchronize things

But what if x was a pair?

Pair x = {2,4};

Then having immutable Pairs will guarantee that both values are changed at the same time.

But the threads have 4 atomic operations with mutable Pairs:

y = read x.x;
write x.x with y+1;
y = read x.y;
write x.y with y+1;

Every one of them can be interrupted depending on the concurrency of the threads. With immutable Pairs, it forces you to do something like this:

tmp = x;
y = new Pair(tmp.x+1, tmp.y+1);
x = y;

You still need synchronization, because you have the mutable variable x, but the reference copy to tmp is atomic. Since tmp is local, and you know it's not being modified, it doesn't need synchronized even though you're doing two different operations (to read tmp.x and tmp.y).

If you think about how objects are used, most of the time, you just want some snapshot and do some operations on it. If you weren't updating x above, you wouldn't need synchronization. The copy to tmp will happen automatically when you pass x into some function.

But since you were asking specifically about updating a mutable reference, you don't get the immutability benefits. If the reference was also read only, then there would be no need to synchronize anything since nothing can change.

  • So does immutability not remove the need for locks? What makes people say it does? – m0meni Apr 26 '16 at 21:23
  • 4
    "If you have two threads trying to read and update" -- what you just describe is not immutable!! – riwalk Apr 26 '16 at 21:24
  • 1
    @Stargazer712 - in every single modern language it is. Immutable objects != immutable references. – Telastyn Apr 26 '16 at 23:05
  • 1
    @ar7 - if you'll note, I am the answerer of the question you linked. Immutability means that two fields of an object can never be out of sync when you read them (or indexes in a collection). The read can't catch another thread in the middle of mutation. You don't need locks there like you would with a mutable object. – Telastyn Apr 26 '16 at 23:11
  • 1
    @ar7 - yeah, it is not atomic, but as long as tmp isn't changed, it doesn't matter. – Telastyn Apr 27 '16 at 2:17
4

The problem that you have is that you're looking at simplified example, which is so far simplified that you've entirely removed the immutable state from it and left only a single (albeit atomic) mutable value. That's not a realistic example of an immutable system.

To bring some immutability back into it, consider a different example. Two threads are generating objects somehow and inserting them into a shared map structure. The map is implemented as an immutable map, I.e. it has an insert operation that returns a modified copy of the map, leaving the original intact. In this case, what happens is that each thread, when it wants to add something, has a few different options:

  1. It could use a lock, create an updated copy and replace it, then unlock it for other threads. This is a simple approach, and is similar to how you'd perform the operation with a non-immutable map, other than that reader threads don't need to acquire the lock. But we can do better:

  2. It can grab the reference to the current map into private storage, make a new map by inserting into it, and then performing an atomic test and set operation to change the reference. If the value has changed while it has been working, it must redo the operation, but because the operation is a pure function of immutable state we know that it has had no side-effects so can be repeated as many times as necessary to make the update work. If too many threads are trying to update the same state it can become a bottleneck, so falling back on locking if too much contention is detected is a good idea. In many scenarios this can perform better than locking

  3. Passing off the operations to be performed on mutable state to a third thread that can serialise them so that the generator threads do not need to worry about concurrency. This offers the highest throughput of all options, but comes at the expense of system resources for maintaining the serialisation thread.

In an environment where we can package up pure mutation operations like this you can write a library that manages all of this automatically, so you just need to pass it a function for updating the value and it can decide which strategy to take. Many languages have libraries that implement "software transactional memory" (which is the name of the technique number 2 above) - some of them will also perform locking and/or serialisation as and when they feel it appropriate. But all of this is made possible because the objects in use are immutable and there are only a small number of mutable references to them.

  • That's the most easy to understand description of STM I've ever heard. Does approach 3 have a name? – m0meni Apr 27 '16 at 11:24
3

Aren't locks only needed if you're changing state?

There is a subtlety here. Locks are needed not only if the current thread wants to modify the state, but if any any other thread might modify the state. This means that you can only safely elide the object if you know that no other part of the system will modify it. In other words, you can only elide the lock if the object is immutable.

Saying that locks aren't needed for immutable objects is just the same as saying that locks aren't needed if you only read the object.

But additionally, it also means that by restructuring your code to use immutable objects, we can get rid of locks. Let's consider a simple case, implemented using mutable objects:

List list = new List();
void worker() {
   for(...) {
      synchronized(list) {
         list.add(...)
      }
   }
}

for (...) {
    start(worker)
}

for (...) {
   waitForWorkerToFinish();
}

This will work, but not very well because all the threads will be fighting over the lock. Here's the immutable solution:

List worker() {
   List list;
   for(...) {
      list.add(...)
   }
   return list;
}

for (...) {
    start(worker)
}

List list;
for (...) {
   list.addAll(waitForWorkerToFinish());
}

Notice how there are no locks in the second example. (Well, there are probably locks implementing start and waitForWorkerToFinish, but worker doesn't have to acquire locks). Because it has gotten rid of the lock, it will be faster.

  • This is a nice simple example. Note that waitForWorkerToFinish() probably doesn't do a lock, but rather just does some form of Thread.join(), which is different. – riwalk Apr 26 '16 at 21:44
  • @Stargazer712, its an implementation detail, but in my experience, the workers are usually launched in a thread pool and I've got some sort of future which uses a lock of some sort to implement its waiting logic. – Winston Ewert Apr 26 '16 at 21:52
1

The answer is pretty easy, with immutability, you don't change state rather you create new state(s).

So you have 2 processes both getting input from the same state. What you end up with is 3 things: first the original state, and 2 new states which is the output from the 2 processes.

What you need now is a third process dedicated to putting those states from the other two processes together and come up with a final answer.

  • I assumed that's the case but how does that actually take place? What if the order of the state changes matters like one thread does multiplication and the other does addition? – m0meni Apr 26 '16 at 21:10
  • 2
    While this answer makes sense to me, I suspect for many this sounds like you've merely replaced the synchronization problem with a messier version of exactly the same synchronization problem. Could you add some more detail to clarify how this actually solves the problem? – Ixrec Apr 26 '16 at 21:10
0

That's not how it works.

If you have two threads reading and incrementing a shared variable, it's not immutable. When you mark something as immutable, you're telling everyone (and yourself) that the value isn't going to change.

  • 2
    True, but read the last paragraph of his question. – Robert Harvey Apr 26 '16 at 20:56
  • 1
    You didn't fully read the question. – Pieter B Apr 26 '16 at 21:02
0

If you'll forgive me for using a more complex example with hefty work worth parallelizing and not just atomic operations to a numeric variable, consider a video game loop which has to apply artificial intelligence, then physics, then rendering in that order:

enter image description here

Here even mutable concurrent data structures for the game state won't let us effectively evaluate this as a true pipeline without just locking and bottlenecking and causing everything to still wait on each other, because artificial intelligence needs to be applied completely before physics and make its changes visible to it before it can be applied, and both need to be applied completely before rendering a frame to avoid artifacts. We might be able to use multiple threads to speed up one of these in their implementation to prevent the other two from waiting as long, but we cannot evaluate it in parallel.

But what happens if our game state becomes immutable? In that case we no longer have "shared state". We have a pipeline focusing on inputting a former game state and outputting a new game state:

enter image description here

And while the first pass would require that physics wait for the first output from AI, and for the renderer to wait for the first output from physics, at this stage the parts of the pipeline can now be running in parallel cranking out new outputs as a true, parallel pipeline rather than a serial executor.

And this can potentially be done in a lock-free way with guaranteed system-wise throughput. So this is just one example but it's one very familiar to me, and one where I benefited quite a bit (with huge improvements to frame rates, not just in terms of faster frame rates but more consistent and smoother frame rates) by making each stage of the pipeline pure (free of external, observable side effects), for which immutability also helped to enforce.

If you can't help but make thread B depend on thread A to finish and see its modified output with that sort of order dependency, then you can still at least turn that into a true pipeline where the two can be running in parallel (thread B can be focused on cranking out a new output for thread C, perhaps, while thread A is simultaneously working on cranking out a new output for thread B), and all without locks, provided we are not mutating shared state.

With that said, whether the state is mutable or not is actually not so relevant to achieving this type of concurrency and lock-free thread-safety, and I hope I don't upset the functional purists out there by saying that (I'm coming at this pursuing purity in imperatives languages like C and C++ where practicality forces me to take a relaxed view about immutability). There are lots of benefits to immutability that help enforce purity and help simplify maintaining invariants, but the ultimate thing that helps here is to make the state no longer shared among threads. Immutability enforces that very strictly, but you can achieve this kind of pipeline with a mutable interface design for your game state provided it's not shared among threads, with each thread inputting a copy and outputting a new, modified version.

How do you reconcile this problem so that the shared state becomes N + 2? Or am I missing something and that's not how it works?

That normally becomes a matter of atomic operations. But I imagine for a more complex example and what you're really after, if one thread must make its output visible to the other conceptually, then you still don't need to lock on shared state because you can apply the pipeline approach mentioned above. The second thread will initially need to wait (it doesn't need to lock necessarily) on the first thread to feed it the initial output, but then the first thread can start churning out new outputs in parallel right after while the second thread is doing its thing. You can at least achieve a true, parallel pipeline in these cases by avoiding shared state and favoring a pure I/O nature (as opposed to a mutating nature causing external side effects) to the design.

0

There's an immutable object with a value of N. Two threads each want to create an immutable object with a value of N+1. They can do that without any locking just fine.

What you didn't mention, is that quite likely there is somewhere a shared mutable reference to the first object, and two threads want to change that shared mutable reference to point to a new immutable object with a higher value. Changing that mutable reference is where you will need a lock. If you never store a reference to the new objects in a shared place, you don't need locks.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.