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 TVar
s 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?
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-TVar
s 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With