High-Performance Software Transactional Memory (STM)

A custom C++ implementation of a Software Transactional Memory (STM) system inspired by the Transactional Locking II (TL2) algorithm. This library provides thread-safe, concurrent reads and writes to shared memory without relying on coarse-grained locks, allowing for high-throughput multi-threaded applications.

Note: The C++ interface (tm.hpp) was provided as part of Concurrent Computing (CS-453) at EPFL. The backend logic, transaction management, and algorithmic optimizations in tm.cpp are my original implementation.

Key Technical Features

• Versioned Locking (TL2): Uses a global clock and a lock table std::atomic_uint64_t to manage optimistic concurrency control and detect Read-After-Write hazards.
• Algorithmic Optimizations:
  • Bloom Filters: Transactions use a 64-bit local Bloom Filter to achieve $O(1)$ write-set lookups, drastically speeding up read operations during active transactions.
  • Thread-Local Storage (TLS): Implements a thread-local transaction pool (tx_pool_storage) to recycle transaction objects, minimizing expensive heap allocations during high-contention workloads.
• Custom Memory Management: Safely handles deferred allocations (tm_alloc) and frees (tm_free), ensuring memory is only modified globally upon a successful commit. Uses a recycle bin for fast reallocation of aborted transaction segments.
• Hardware-Aware Backoff: Implements exponential backoff using _mm_pause() (x86) or yield (ARM) to optimize CPU pipeline usage during spin-wait scenarios.

Project Structure

TL2-inspired-STM/
├── README.md
├── CMakeLists.txt
├── src/
│   └── tm.cpp           # Core STM implementation (My Code)
├── include/
│   └── tm.hpp           # Provided STM Interface (EPFL)
└── tests/
    └── benchmark.cpp    # Multi-threaded bank account transfer benchmark

Build and Run Instructions

This project uses CMake. A compiler supporting at least C++17 is required.

# 1. Clone the repository and navigate into it
# 2. Create a build directory
mkdir build && cd build

# 3. Generate Makefiles (Enable Release mode for accurate benchmarking)
cmake -DCMAKE_BUILD_TYPE=Release ..

# 4. Compile
make

# 5. Run the benchmark
./benchmark

📊 Benchmarking

The included benchmark simulates high-contention bank transfers across thousands of accounts. It spawns multiple threads attempting concurrent transfers and verifies data consistency at the end of the execution run.