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

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.