| name | software-transactional-memory |
| description | Implements software transactional memory. Use when: (1) Building concurrent data structures, (2) Simplifying lock-free code, (3) Composing atomic operations. |
| version | 1.0.0 |
| tags | ["concurrency","stm","transactions","synchronization"] |
| difficulty | intermediate |
| languages | ["haskell","rust"] |
| dependencies | [] |
Software Transactional Memory
Implements STM for lock-free concurrent programming.
When to Use
- Concurrent data structure design
- Simplifying lock-free algorithms
- Composing atomic operations
- Database-style transactions in memory
What This Skill Does
- Implements transactions - Atomic read/write blocks
- Handles conflicts - Conflict detection and retry
- Provides composability - Transactional composition
- Optimizes performance - Read/write sets
Key Concepts
| Concept | Description |
|---|
| Read set | Variables read in transaction |
| Write set | Variables written in transaction |
| Commit | Validate and apply writes |
| Abort | Discard changes, restart |
| Retry | Wait for condition, restart |
| OrElse | Alternative on abort |
STM Properties
- Atomicity: All or nothing
- Isolation: No intermediate states visible
- Consistency: Maintain invariants
- Composability: Combine operations
Tips
- Keep transactions short
- Avoid long-running operations
- Use retry for blocking
- Consider contention patterns
- Profile abort rates
Related Skills
actor-model-implementer - Actor concurrencyrace-detection-tool - Race detectionweak-memory-model-verifier - Verify concurrency
Research Tools & Artifacts
STM implementations:
| System | Language | What to Learn |
|---|
| Haskell STM | Haskell | Composable transactions |
| Clojure refs | Clojure | Production STM |
| Intel TSX | C/C++ | Hardware support |
| TinySTM | C | Fast STM |
Key Papers
- Shavit & Touitou (1997) - Original software transactional memory paper
- Herlihy & Moss (1993) - Hardware transactional memory
- Harris, Marlow, Peyton Jones, Herlihy (2005) - "Composable Memory Transactions" (PPoPP 2005)
Research Frontiers
1. Hardware Transactional Memory
- Goal: Hardware support for transactions
- Approach: TSX, HTM
- Tools: Intel TSX
Implementation Pitfalls
| Pitfall | Real Consequence | Solution |
|---|
| Starvation | Transactions never commit | Bounded retries |
| Contention | High abort rate | Careful design |
