Persistent/immutable data structures don’t solve concurrency problems on their own, but they make solving them much easier.

Consider a thread T1 that passes a set S to another thread T2. If S is mutable, T1 has a problem: It loses control of what happens with S. Thread T2 can modify it, so T1 can’t rely at all on content of S. And vice versa – T2 can’t be sure that T1 doesn’t modify S while T2 operates on it.

One solution is to add some kind of a contract to the communication of T1 and T2 so that only one of the threads is allowed to modify S. This is error prone and burdens both the design and implementation.

Another solution is that T1 or T2 clone the data structure (or both of them, if they aren’t coordinated). However, if S isn’t persistent, this is an expensive O(n) operation.

If you have a persistent data structure, you’re free of this burden. You can pass a structure to another thread and you don’t have to care what it does with it. Both threads have access to the original version and can do arbitrary operations on it – it doesn’t influence what the other thread sees.

See also: persistent vs immutable data structure.

Why then, is the immutability of PDSs touted as something beneficial
for “thread safety”? Are there any real examples where PDSs help in
synchronization, or solving concurrency problems?

Main benefit of a PDS in that case is that you can modify a portion of data without making everything unique (without deep copying everything, so to speak). That has many potential benefits besides allowing you to write cheap functions free of side effects: instancing copy and pasted data, trivial undo systems, trivial replay features in games, trivial non-destructive editing, trivial exception safety, etc. etc. etc.

One can imagine a data structure which would be persistent but mutable. For example, you could take a linked list, represented by a pointer to the first node, and a prepend-operation which would return a new list, consisting of a new head node plus the previous list. Since you still have the reference to the previous head, you can access and modify this list, which has meanwhile become also embedded inside the new list. While possible, such a paradigm doesn’t offer the benefits of persistent and immutable data structures, e.g. it is certainly not thread safe by default. However, it may have its uses as long as the developer knows what they’re doing, e.g. for space efficiency. Also note that while the structure may be mutable at the language level in that nothing prevents the code from modifying it, it may in practice be used as if it were immutable: the application logic may by convention not mutate the state even though theoretically it could.

So long story short, without immutability (enforced by the language or by convention), persistence od data structures loses some of its benefits (thread safety) but not others (space efficiency for some scenarios).

As for examples from non-functional languages, Java’s String.substring() uses what I would call a persistent data structure. The String is represented by an array of characters plus the start and end offsets of the range of the array which is actually used. When a substring is created, the new object re-uses the same character array, only with modified start and end offsets. Since String is immutable, it is (with respect to the substring() operation, not others) an immutable persistent data structure.

The immutability of data structures is the part relevant to thread safety. Their persistence (re-use of existing chunks when a new structure is created) is relevant to efficiency when working with such collections. Since they are immutable, an operation like adding an item doesn’t modify the existing structure but returns a new one, with the additional element appended. If each time the whole structure was copied, starting with an empty collection and adding 1000 elements one by one in order to end up with a 1000-element collection, would create temporary objects with 0+1+2+…+999 = 500000 elements total which would be a huge waste. With persistent data structures, this can be avoided as the 1-element collection is re-used in the 2-element one, which is re-used in the 3-element one and so on, so that in the end no garbage nodes are allocated – each one is at the end used in the final state of the data structure.

I am admittedly biased as one applying such concepts in C++ by the language and its nature, as well as my domain, and even the way we use the language. But given these things, I think immutable designs are the least interesting aspect when it comes to reaping a bulk of the benefits associated with functional programming, like thread safety, ease of reasoning about the system, finding more reuse for functions (and finding we can combine them in any order without unpleasant surprises), etc.

Take this simplistic C++ example (admittedly not optimized for simplicity to avoid embarrassing myself in front of any image processing experts out there):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

While the implementation of that function mutates local (and temporary) state in the form of two counter variables and a temporary local image to output, it has no external side effects. It inputs an image and outputs a new one. We can multithread it to our hearts’ content. It’s easy to reason about, easy to thoroughly test. It’s exception-safe since if anything throws, the new image is automatically discarded and we don’t have to worry about rolling back external side effects (there are no external images being modified outside the function’s scope, so to speak).

I see little to be gained, and potentially much to be lost, by making Image immutable in the above context, in C++, except to potentially make the above function more unwieldy to implement, and possibly a bit less efficient.

Purity

So pure functions (free of external side effects) are very interesting to me, and I emphasize the importance of favoring them often to team members even in C++. But immutable designs, applied just generally absent context and nuance, are not nearly as interesting to me since, given the imperative nature of the language, it’s often useful and practical to be able to mutate some local temporary objects in the process of efficiently (both for developer and hardware) implementing a pure function.

Cheap Copying of Hefty Structures

The second most useful property I find is the ability cheaply copy the really hefty data structures around when the cost of doing so, as would often be incurred to make functions pure given their strict input/output nature, would be non-trivial. These wouldn’t be small structures that can fit on the stack. They’d be big, hefty structures, like the entire Scene for a video game.

In that case the copying overhead could prevent opportunities for effective parallelism, because it might be difficult to parallelize physics and rendering effectively without locking and bottlenecking each other if physics is mutating the scene that the renderer is simultaneously trying to draw, while simultaneously having physics deep copy the entire game scene around just to output one frame with physics applied might be equally ineffective. However, if the physics system was ‘pure’ in the sense that it merely inputted a scene and outputted a new one with physics applied, and such purity did not come at the cost of astronomical copying overhead, it could safely operate in parallel with the renderer without one waiting on the other.

So the ability to cheaply copy the really hefty data of your application state around and output new, modified versions with minimal cost to processing and memory use can really open up new doors for purity and effective parallelism, and there I find lots of lessons to learn from how persistent data structures are implemented. But whatever we create using such lessons doesn’t have to be fully persistent, or offer immutable interfaces (it might use copy-on-write, for example, or a “builder/transient”), to achieve this ability to be dirt cheap to copy around and modify just sections of the copy without doubling up memory use and memory access in our quest for parallelism and purity in our functions/systems/pipeline.

Immutability

Finally there’s immutability which I consider the least interesting of these three, but it can enforce, with an iron fist, when certain object designs are not meant to be used as local temporaries to a pure function, and instead in a broader context, a valuable kind of “object-level purity”, as in all methods no longer cause external side effects (no longer mutate member variables outside the immediate local scope of the method).

And while I consider it the least interesting of these three in languages like C++, it can certainly simplify the testing and thread-safety and reasoning of non-trivial objects. It can be a load off to work with the guarantee that an object cannot be given any unique state combination outside of its constructor, for example, and that we can freely pass it around, even by reference/pointer without leaning on constness and read-only iterators and handles and such, while guaranteeing (well, at least as much as we can within the language) that its original contents will not be mutated.

But I find this the least interesting property because most objects I see as beneficial as being used temporarily, in mutable form, to implement a pure function (or even a broader concept, like a “pure system” which might be an object or series of functions with the ultimate effect of merely inputting something and outputting something new without touching anything else), and I think immutability taken to the extremities in a largely imperative language is a rather counter-productive goal. I’d apply it sparingly for the parts of the codebase where it really helps the most.

Finally:

[…] it would seem that persistent data structures are not in themselves sufficient to handle scenarios where one thread makes a change that is visible to other threads. For this, it seems we must use devices such as atoms, references, software transactional memory, or even classic locks and synchronization mechanisms.

Naturally if your design calls for modifications (in a user-end design sense) to be visible to multiple threads simultaneously as they occur, we’re back to synchronization or at least the drawing board to work out some sophisticated ways to deal with this (I’ve seen some very elaborate examples used by experts dealing with these sorts of problems in functional programming).

But I have found, once you get that sort of copying and ability to output partially-modified versions of hefty structures dirt cheap, as you would get with persistent data structures as an example, it does often open up lots of doors and opportunities you might not have thought about before to parallelize code that can run completely independently of each other in a strict I/O sort of parallel pipeline. Even if some parts of the algorithm have to be serial in nature, you might defer that processing to a single thread but find that leaning on these concepts has opened up doors to easily, and without worry, parallelize 90% of the hefty work, e.g.