Return to Answer

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.

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:

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:

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. 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 provided it's not shared among threads, with each thread inputting a copy and outputting a new, modified version.

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:

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:

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.

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:

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:

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 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.

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:

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:

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. 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 provided it's not shared among threads, with each thread inputting a copy and outputting a new, modified version.