Does STM provide fine-grained locking for existing data structures?

Question

Reading Bartosz Milewski's fantastic blog post on STM, I was excited to read the following:

But take into account an important fact: STM is very fine grained. For instance, when you’re inserting an item into a tree, the STM transaction will only lock the nodes that you are actually modifying. STM will easily beat a solution that uses one global lock per whole tree.

However, as I understand it, this behavior is not automatic, is it? If I use a TVar (Map k a), will it not act as a single global lock on the whole map? And to gain the benefit of this fine-grained behavior, I (or someone) would have to implement a map replacement (TMap, for example) that contains TVars internally, correct?

This might seem like an obvious question, but reading up on STM implementation I was confused between reads of TVars and reads of memory locations. I just want to make sure I have it right!

Bartosz goes further to say:

Per-node manual locking is hard to implement correctly because of the risk of deadlocks.

The difference with STM, as I understand it, is that while the STM implementation in effect uses locks the way a manually-locked solution might, the actual acquiry and release of locks is handled by the runtime, not the programmer - correct?

Halcomb

It depends on the implementation but there are many lock-free ways to implement STM (atomic compare and swap, for example). As for your first question, yes you would need maps of TVars and not a TVar (Map k v). – Goldsberry

@ThomasM.DuBuisson thanks for that. Do you mean that I can actually have a fine-grained Map, or would I need to completely re-implement Map to use TVars internally? – Halcomb

Also, I just learned that 'acquiry' is actually a word. Lucky guess. – Halcomb

You can simply have a normal map with values that are TVars. More specifically, Map k (TVar v). – Goldsberry

Answer 1

A TVar is a mutable cell. With immutable structures no two threads can transmit modifications back and forth, so we need some notion of mutable cell to cause the effect. In particular, we have

writeTVar :: TVar a -> a -> STM ()

which creates an SMT action replacing the value inside the mutable cell. We can sequence a few of these operations together, building a bigger and more complex STM action, and then call

atomically :: STM a -> IO a

to atomically commit the whole STM action at once. This is the "transactional" part of software transactional memory: other threads with their own references to these mutable cells will only ever witness the entirety of the atomically-performed STM action, no subparts. To achieve this Haskell might use locking, or something more clever—it's a mere implementation detail. The only thing STM asks you be cognizant of is that the actions within your STM block may be run repeatedly as necessary—and so side effects outside of modification of some shared memory cells are prohibited.

So how do we achieve fine-grained concurrency? Easily: we just provide more mutable cells for various threads to synchronize upon. For instance, we can read at least 3 different Map types.

TVar (Map k v)
Map k (TVar v)
TVar (Map k (TVar v))

The first will allow concurrent threads to make modifications to the entire Map all at once such that no partial changes are visible. The second, allows changes at any stored value, but maintains that the structure of the map itself—the choice of keys and the selection of stored values—is immutable and changes cannot be easily propagated to other threads.

The final choice, TVar (Map k (TVar v)) is the most flexible. We can make wholesale modifications to the Map by synchronizing on the outer TVar and we can make changes to the values stored in the map by reading down to the value-TVars and synchronizing on actions within them. The full set of possible semantics available for such a tree is myriad allowing both "whole Map locking" and "individual value locking" to happen together.

Whalebone

Fantastic answer! Thanks for the explanation. So just to be clear, even TVar (Map k (TVar a)) does not achieve the fine-grained locking that Bartosz describes - that would require implementing a totally new TMap data structure which puts TVars around the internal nodes of the tree (if that is indeed the storage structure used), not just the leaves. – Halcomb

Yup, your granularity is exactly the same as the locations of your TVars. – Whalebone