17

Languages that are purely functional or near-purely functional benefit from persistent data structures because they are immutable and fit well with the stateless style of functional programming.

But from time to time we see libraries of persistent data structures for (state-based, OOP) languages like Java. A claim often heard in favor of persistent data structures is that because they are immutable, they are thread-safe.

However, the reason that persistent data structures are thread-safe is that if one thread were to "add" an element to a persistent collection, the operation returns a new collection like the original but with the element added. Other threads therefore see the original collection. The two collections share a lot of internal state, of course -- that's why these persistent structures are efficient.

But since different threads see different states of data, 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.

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? Or are PDSs simply a way to provide a stateless interface to an object in support of a functional programming style?

  • 3
    You keep saying "persistent". Do you really mean "persistent" as in "able to survive a restart of the program", or just "immutable" as in "never changes after its creation"? – Kilian Foth Jun 29 '13 at 9:37
  • 16
    @KilianFoth Persistent data structures have a well-established definition: "a persistent data structure is a data structure that always preserves the previous version of itself when it is modified". So it's about re-using the previous structure when a new structure based on it is created rather than persistency as in "able to survive the restart of a program". – Michał Kosmulski Jun 29 '13 at 10:02
  • 3
    Your question appears to be less about use of persistent data structures in non-functional languages and more about which parts of concurrency and parallelism aren't solved by them, regardless of paradigm. – user7043 Jun 29 '13 at 10:30
  • My mistake. I didn't know that "persistent data structure" is a technical term distinct from mere persistence. – Kilian Foth Jun 29 '13 at 12:04
  • @delnan Yes that is correct. – Ray Toal Jun 29 '13 at 17:52
14

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.

  • 2
    Ah, so "thread safety" in this context just means that one thread doesn't have to worry about other threads destroying the data they see, but has nothing to do with synchronization and dealing with data we want to be shared between threads. That's in line with what I thought, but +1 for elegantly stating "don't solve conurrency problems on their own." – Ray Toal Jun 29 '13 at 17:59
  • 2
    @RayToal Yes, in this context "thread safe" means exactly that. How data are shared between threads is a different problem, which has many solutions, as you've mentioned (personally I like STM for its composability). Thread safety ensures that you don't have to worry what happens with data after being shared. This is actually a big deal, because threads don't need to synchronize who works on a data structure and when. – Petr Pudlák Jun 29 '13 at 18:17
  • @RayToal This allows elegant concurrency models such as actors, which spare developers from having to deal with explicit locking and thread management, and which rely on immutability of messages - you don't know when a message is delivered and processed, or to what other actors it's forwarded to. – Petr Pudlák Jun 29 '13 at 18:18
  • Thanks Petr, I'll give actors another look. I'm familiar with all of the Clojure mechanisms, and did note that Rich Hickey explicitly chose to not use the actor model, at least as exemplified in Erlang. Still, the more you know the better. – Ray Toal Jun 29 '13 at 19:36
  • @RayToal An interesting link, thanks. I only used actors as an example, not that I'm saying it'd be the best solution. I haven't used Clojure, but it seems that it's preferred solution is STM, which I'd definitely prefer over actors. STM also relies on persistence/immutability - it wouldn't be possible to restart a transaction if it irrevocably modifies a data structure. – Petr Pudlák Jun 29 '13 at 21:00
4

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.

2

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.

  • Sometimes it's useful to have quasi-immutable objects in which all but one aspect of state is immutable: the ability to make an object whose state is almost like a given object. For example, an AppendOnlyList<T> backed by power-of-two growing arrays could produce immutable snapshots without having to copy any data for each snapshot, but one could not produce a list which contained the contents of such a snapshot, plus a new item, without recopying everything to a new array. – supercat Feb 27 '14 at 21:43
0

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.

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.