software transactional memory
**Software Transactional Memory (STM)** is a **concurrency control mechanism that allows memory operations to be grouped into atomic transactions** — a transaction either commits (all changes visible atomically) or aborts (no changes visible), without explicit locks.
**The Transaction Analogy**
- Database transactions: GROUP operations into atomic units (ACID).
- STM: Apply same concept to shared memory operations in multi-threaded code.
**STM Semantics**
```
atomic {
x = x + 1; // Read x into transaction local copy
y = y - 1; // Read y
// All changes visible atomically when block exits
}
```
- If no conflict: Commit — writes become visible atomically.
- If conflict (another thread modified same data): Abort + retry.
**How STM Works**
1. **Speculative execution**: Transaction runs speculatively on thread-local copies.
2. **Read/write logging**: Track all addresses read and written.
3. **Validation**: Before commit, check read set is still valid (no other thread modified reads).
4. **Commit or Abort**: Valid → commit writes atomically. Invalid → abort + retry.
**STM vs. Locks**
| Aspect | Locks | STM |
|--------|-------|-----|
| Deadlock | Possible | Impossible |
| Composability | Hard | Natural (nest transactions) |
| Scalability | Good under low contention | Good under low contention |
| Overhead | Low (fast path) | Higher (log overhead) |
| Priority inversion | Possible | No |
**Hardware Transactional Memory (HTM)**
- Intel TSX (Transactional Synchronization Extensions): Hardware support in CPU.
- Small transactions (fit in L1 cache): Very low overhead.
- Fallback: Software path when transaction capacity exceeded.
**Practical STM Implementations**
- Clojure STM: Language-level STM with persistent data structures.
- GCC `__transaction_atomic`: C++ experimental.
- Haskell STM: `STM` monad, composable atomic blocks.
**Limitations**
- Performance overhead vs. fine-grained locks for simple cases.
- I/O within transactions: Cannot undo I/O on abort.
- Contention: High-conflict workloads → many aborts → performance degradation.
STM offers **a higher-level, composable alternative to lock-based concurrency** — particularly valuable for complex data structure updates where lock granularity is difficult to determine correctly.