arXiv CSopen access

uSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts

arXiv:2607.18178v1 [cs.DC] 20 Jul 2026

µSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts Zachary Kent

Guy E. Blelloch

André Costa

Carnegie Mellon University Pittsburgh, PA, USA [email protected]

Carnegie Mellon University Pittsburgh, PA, USA [email protected]

Carnegie Mellon University Pittsburgh, PA, USA [email protected]

Abstract

1

Software Transactional Memory (STM) systems allow developers to more easily exploit multicore architectures by wrapping arbitrary sequential code in transactions that are executed concurrently. In recent years, the performance of STM systems has approached that of hand-tuned data structures through techniques that avoid unnecessary aborts and exploit the semantics of underlying data structures. Despite achieving excellent performance, most STM systems do not fully address the concerns they targeted in the first place: safety, usability, and generality. In particular, these systems place restrictions on the data types that may be updated transactionally, such as requiring that these types fit within a word, and can require modification of data layout. Moreover, most STM systems abort transactions in the middle of client code to ensure correctness. This can cause space leaks and other bugs not present in the original code. We present µSTM, a novel STM system addressing all of these shortcomings while still maintaining excellent performance, all within ∼300 lines of code. µSTM supports general types while maintaining data layout. Aborts are deferred until the end of the transaction, allowing client code within a transaction to terminate normally. To ensure that µSTM guarantees opacity, we implement a novel timestamping algorithm we call split-increment timestamps. We compare the performance of µSTM to a variety of state-ofthe-art (SOTA) STM systems, demonstrating that µSTM matches or outperforms the SOTA on a variety of workloads.

Transactional memory (TM) allows developers to wrap code in transactions such that all accesses to shared memory within the code appear as if they happen atomically even when other threads are concurrently accessing the memory. TM has long been suggested as a way to greatly simplify concurrent programming on shared-memory multicore architectures. However, early libraries for transactional memory did not perform well and had various restrictions that made them difficult to use in practice [9]. Over the years there have been many advances that have improved performance. Such improvements include removing levels of indirection, supporting opacity [15], more efficient locks [46], better contention management [52], efficient multiversioning [37, 38, 42, 57], efficient timestamping [15, 45], and efficient memory management [37, 56]. Software Transactional Memory (STM) libraries are in many cases quite efficient, and experiments have shown that data structures based on STM libraries can approach the efficiency of hand-coded concurrent data structures in several situations [4, 45]. Such modern STM libraries, however, still have notable limitations with regards to general usage. Limitations include requiring indirection for anything other than trivial types, relying on unsafe long jumps (unsafe aborts), requiring modification of the underlying data structures (intrusive), performing badly under high contention (contention intolerant), and requiring all reads and writes to STM variables to be in a transaction (no publication or privatization). Table 1 summarizes these limitations across a variety of state-of-theart STM libraries. More details on these limitations and implications are given in Section 2. In this paper we present µSTM, a header-only STM library addressing each of these limitations. For this purpose we introduce new techniques, including deferred aborts, split-increment timestamps, and allocate-swap-retire. µSTM uses multiversioning [48] and optimistic concurrency control [31], where a speculative phase runs the user code buffering any writes, and a commit phase validates and executes the writes if successful. Our experiments show that µSTM is the fastest publicly available STM across a broad set of workloads. Furthermore our STM consists of only around 300 lines of pure C++ code (measured by cloc), plus another 150 lines for an epoch-based reclamation scheme1 . µSTM should therefore be reasonably easy to adapt and extend. Here we briefly go through the techniques we introduce and how they help alleviate the limitations; more details are given in Section 2. Our deferred aborts are used to avoid any exceptional control flow in user code. Most prior STMs rely on unsafe system longjumps to exit user code. These longjumps, or other exceptional control, are necessary in the systems to ensure opacity [20] (i.e., even aborted

CCS Concepts • Theory of computation → Concurrent algorithms.

Keywords software transactional memory, concurrent algorithms ACM Reference Format: Zachary Kent, Guy E. Blelloch, and André Costa. 2026. µSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts . In 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26), July 06–10, 2026, London, United Kingdom. ACM, New York, NY, USA, 17 pages. https://doi.org/10.1145/3816782.3819198

This work is licensed under a Creative Commons Attribution 4.0 International License. SPAA ’26, London, United Kingdom © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2761-0/2026/07 https://doi.org/10.1145/3816782.3819198

Introduction

1 https://github.com/cmuparlay/ustm

SPAA ’26, July 06–10, 2026, London, United Kingdom

System TinySTM [17] tl2 [15] 2PLSF [46] dctl [45] multiverse [10] fuse [4] µSTM (this paper)

General Types ✘ ✘ ✘ ✘ ✘ ✘ ✔

Zachary Kent, Guy E. Blelloch, and André Costa

Safe Aborts ✘ ✘ ✘ ✘ ✘ ✔4 ✔

Nonintrusive ✘ ✘ ✘ ✘ ✘ ✘ ✔

Contention Tolerant ✘ ✘ ✘ ✘1 ✘ ✔ ✔

Privatization Safety ✘2 ✘2 ✔ ✘2 ✘2 ✔ ✔

Multi Versioned ✘ ✘ ✘ ✘ ✔ ✔ ✔

Starvation Free ✘ ✘ ✔ ✘3 ✘ ✘ ✘

Table 1: Properties of various STM systems. All these systems support opaque serializable transactions, and support allocation and frees within a transaction. The last three are all from within the past three years. (1) The contention status of DCTL is unknown, as its implementation is proprietary. (2) We discuss how these STMs could efficiently support privatization safety in the full version of this paper [26]. (3) DCTL has a version that is starvation free. (4) For safe aborts fuse requires hardware timestamps. transactions must see a snapshot of the state). Instead, our deferred aborts continue running the user code until finished, and then abort, if needed, before committing any writes. The challenge is to maintain opacity. We support this with a combination of multiversioning and a new form of efficient timestamping which we refer to as split-increment timestamps. These timestamps solve a problem with prior methods for efficient timestamps, e.g. used in TL2 [15], Verlib [5], and DCTL [45], while maintaining their efficiency. In particular, these prior methods do not allow deferred aborts since they cannot capture a snapshot for aborted transactions even with multiversioning. Our allocate-swap-retire approach is used for two purposes: supporting multiversioning and non-intrusive indirection-free general types. The idea of the approach is that during a transaction when a value is stored, we allocate a cell to hold it and add a pointer to the cell to a per-transaction write log. Later when committing the transaction we swap the value in the cell with the value in the location, immediately retire the cell, and then link the cell into a version list, which is stored separately in a hash table. A key efficiency is achieved by using the same mechanism for supporting general types and multiversioning—multiversioned STMs have to allocate such cells in any case. Importantly, the approach is nonintrusive since we just use the original layout of the data and all meta information (locks and version lists) is kept separately. Care is required to safely read locations. Beyond the above-mentioned approaches µSTM uses variants on standard approaches to achieve functionality and performance. It supports publication and privatization safety using fences [28], supporting both global and per-variable fences (see the full version [26]). With regards to reducing contention costs, our allocateswap-retire and split-increment timestamps both improve contention costs, as discussed later. We have implemented µSTM in pure C++, and make no use of longjumps or exceptions. We have tested portability across x86, ARM and PowerPC processors. µSTM was designed to be easily incorporated into existing C++ code and extended. Its public interface is given in the full version [26]. In the experimental section we compare performance to several existing STM systems. We compare on eight different data structures supporting dictionaries using YCSB-like workloads, and on the widely used TPC-C benchmark suite. The workloads vary table

size, update rates, contention (using a zipfian distribution), transaction size, and thread counts. We report both on geometric mean across workloads, and graphs for each parameter. To see the advantage of multiversioning we also report on range query performance. We outperform other systems in almost all scenarios. To better understand the effect of our split-increment timestamps we compare across a variety of timestamp approaches including hardware stamps (only available on Intel x86 machines), eager stamps, and lazy stamps (only safe with longjumps). To better understand the cost of our deferred aborts, and allocate-swap-retire technique, we do an ablation study where we compare two versions of µSTM that use longjumps instead of deferred aborts, and one that additionally only supports single-version trivial types and does not need any allocation on writes. These stripped down versions do perform slightly better on the structures they can deal with, but with much less functionality.

2

Overview and Related Work

In this section we describe why the features we support are important, present more detail on how we address the issue, and how it relates to prior work.

2.1

Multiversion and Optimistic Transactions

Multiversion transactional systems date back to the 1970s [48] and are widely used in both transactional database systems and transactional memory [3, 4, 8, 10, 13, 16, 18, 29, 34, 38, 41–44, 48, 49, 57]. Multiversioning keeps old versions of values when overwritten, typically in per-location version lists, so ongoing transactions can make use of them. Their main advantage is allowing large read-only transactions to proceed concurrently with updating transactions, and in several of these systems the read-only transactions never abort. We also use multiversioning to support deferred aborts. Optimistic concurrency control dates back to the early 1980s [31] and is used in the majority of both transactional database systems and transactional memory systems (a citation list would be too long but Harris, Larus and Rajwar describe several such systems [22]). The idea is to split a transaction into a speculative phase that runs the user code and a commit phase to check for consistency by validating the reads, and if successful committing the writes. This

µSTM: A Lightweight and Efficient STM

compares to pessimistic concurrency, which takes locks on all memory accesses during the user code and never has to validate. The advantage of optimistic concurrency is that it does not require any locks on the reads. However it is the lack of read locks that makes handling non-trivial types difficult.

2.2

General Types and Non-intrusion

General-types and non-intrusion are two related but orthogonal concepts requiring that the STM system support transactions over general types without data-layout changes to these types. Most existing STMs fail these requirements. For example, many require that the underlying type fit into a word, or further that the type itself be a pointer (T* for some type T). Some STMs further require intrusive data layout changes to this type T, requiring that it inherit from a base class provided by the STM. For example, fuse requires that types T inherit from the fuse::versioned struct. These characteristics have implications for both performance and usability. In particular, we are concerned with transactions that access inlined objects, i.e., objects that are placed adjacently in memory within the containing structure. Boxed objects, on the other hand, are ones that are stored in the heap with a pointer to them in the containing structure. In languages such as C++ and Rust all objects are inlined, while in other languages, such as Java and Haskell, the compiler decides when to inline [21, 24, 40]. Inlining can greatly reduce space and time, since it avoids allocations and a level of indirection, which can often incur a cache miss. Consider, for example, an array of 16 4-byte objects. Assuming 64 byte cache lines, this would require a single cache line if stored inlined, but significantly more if stored boxed. Furthermore, scanning the array values would touch one cache line inlined instead of 17 if boxed. Boxed objects are relatively easy to support in an STM if the STM supports memory allocation within a transaction. This is because pointers fit in a single word and can be atomically updated with hardware instructions. Hence general types can be supported in most STMs, by creating a wrapper that boxes objects. The wrapper would convert an inlined store of an object, for example, to an indirect one, by allocating a “box” in which to put the new object, reading the pointer to the current box and retiring it, and writing in the pointer to the new box. The boxing, however, will incur significant cost both for loads (reading indirectly) and stores. Furthermore boxing objects would be intrusive requiring changes to the existing data layout. Unless integrated with a compiler, these changes are likely to make the structure incompatible with any existing code that uses it. Unlike boxed objects, supporting non-trivial inlined objects in STMs can be tricky, especially with optimistic concurrency control. Much of the efficiency of optimistic STMs comes from avoiding taking locks when reading. Instead they detect read-write conflicts later during an opacity check or during validation. For non-trivial types this can lead to situations where the readers see partially written values. Another issue is that the write logs need to store arbitrary objects so that writes can be buffered. Our allocate-swap-retire approach aims to support inlined objects for most types in a way that can be used safely in an optimistic STM. Furthermore, the approach also supports multiversioning with the same mechanism, avoiding a double cost. The approach requires

SPAA ’26, July 06–10, 2026, London, United Kingdom

that the type is copyable and relocatable. This second condition has been discussed in the C++ community [36, 39] and effectively means that two inlined objects can be swapped or moved by just swapping or moving their bytes. This is true for most implementations of C++ classes, including e.g., std::vector. Allocate-swap-retire works, roughly, as follows. Each store in user code, which is run during the speculative phase, allocates an object to hold a copy of the stored value, and adds a pointer to the object to the write log. Later, during the commit phase, if the transaction succeeds, we use a bytewise swap of the current value (in the location) and the new value (in the allocated object). The object is then tagged with the version number of the transaction, added to a version list for the location, and retired. To be non-intrusive, we store the version lists elsewhere by keeping a fixed number of buckets, and hashing the location’s address to one of these buckets to store the version [37]. This is also where we store locks. A version list can therefore be associated with multiple location addresses. We prove that the immediate retiring is safe (Theorem 3.1). Since the cells are short-lived, they are recycled quickly and are “warm” in the cache for reuse (assuming a decent memory allocator with thread local pools). On a load, the allocate-swap-retire idiom needs to properly load the value even though another thread could be concurrently updating it. To implement this we use a variant of sequence locks [6, 23, 32, 55] and can take advantage of the timestamp already used for multiversioning. In particular the read first reads the timestamp from the head of the hashed version list, copies the bytes of the type to a buffer, and then reads the timestamp again. It checks that the two timestamps are equal, are not locked, and are less than the start stamp associated with the transaction. If so it has properly read the bytes and it can now copy the value out of the buffer (using e.g., a copy constructor in C++) and return the copy. Note this is where being relocatable is important since it must be the case that the copy constructor acts equivalently whether the value is in its original location or the buffer. If the timestamps are not equal or locked we repeat. If the timestamps are not less than the start stamp, then we traverse the version list searching for the correct version. The details of this mechanism, and how it handles the other cases are described in Section 3.

2.3

Deferred Aborts

Most TM systems we know of use longjumps within user code to implement aborts (e.g., 2PLSF [46], TinySTM [17], TL2 [15], DCTL [45], Multiverse [10], Trinity [47], tl4x [2]). Some form of exceptional control flow (either long jumps, exceptions, or having users thread the errors themselves) is required to support opacity [20] in singleversion systems. This is because the user might load a variable that has been updated since its transaction started and hence be inconsistent with prior reads. In principle this problem can be alleviated in a multiversion system since the load could retrieve the value valid at the start of the transaction presenting user code with a snapshot of the state. In practice, however, this is more difficult, as discussed below, but let’s start with why longjumps and other exceptional control flow are bad for general use. A longjump [27] works, roughly, by saving the register state at a given point in the code and then allowing the user to “jump”

SPAA ’26, July 06–10, 2026, London, United Kingdom

back to that point by restoring that state. The jump could pop up many layers of function calls. This is extremely dangerous in the RAII style of programming [54] of C++ or Rust since none of the destructors on the stack will be called, potentially leaking memory, leaving streams unclosed, or locks held (although we hope users do not put locks in a transaction). Indeed we found that our B-tree code had a memory leak when used with many of the systems we experimented with since the constructor for a node copied from another node using transactional loads. If one of these loads aborted, the memory for the new node would not be collected. Even more dangerous, and used by 2PLSF, is to add the object to a retire-on-abort list before calling the constructor. This would destruct the node on abort, but the node could only be partially filled when it takes the longjump so the destructor is later applied to an inconsistent state. Using exceptions in C++ (or other languages) is much safer since they “unravel” the stack when an exception is thrown, applying all destructors on the way up the stack to the catch point. Exceptions, however, have the opposite problem—to perform correctly they require judicious use of RAII programming. This requires, for example, replacing all raw pointers with smart pointers. Additionally, since exceptions are designed for uncommon cases, they are expensive when actually thrown. However, aborts are not necessarily exceptional—in some of our high-contention benchmarks we get 30x more aborts than successes. Furthermore, replacing pointers with smart shared pointers can be extremely costly in a concurrent environment since concurrent reads would contend on incrementing the reference counter [1]. We have hence never seen data structures designed for transactional memory that use smart pointers. The last option is to have users thread the errors “up the stack”, but this is also not a satisfactory solution.

2.4

Split Timestamps

All methods to abort user code in the middle have significant problems, at least for general use. µSTM therefore runs user code to completion, but, as mentioned, this requires that the user sees a consistent snapshot even if it aborts, requiring, at least, multiversioning. The problem is that all the multiversioning systems require maintaining timestamps. As has been noted by many, incrementing timestamps on every transaction is prohibitively expensive [5, 15, 34, 45, 57, 58]. Therefore all practical systems we are aware of use some form of lazy or imprecise timestamp [5, 15, 34, 45, 58]. The idea of a lazy timestamp [5, 15, 45] is that timestamps are not incremented when the transaction is successful, but are when they fail (in the case of TL2 [15] they are sometimes incremented when successful). Instead, these systems detect when reading a value that the timestamp ordering is ambiguous—in particular that there is no way to properly order an update that is read relative to the ongoing transaction. If such an ambiguous ordering is detected, the transaction must abort immediately (i.e., with exceptional control flow) to preserve opacity. This is true even in a multiversion TM since the system cannot decide which version to use. This problem also occurs with imprecise timestamps [34, 58] and seems inherent with all relaxed timestamp approaches. In addition to forcing exceptional control flow (e.g., a longjump) in the middle of user

Zachary Kent, Guy E. Blelloch, and André Costa

T1 lock validate unlock end T3 lock validate unlock end speculative speculative read read start write x cleanup write y cleanup start stamp stamp t = 23 t = 23 t = 23 t = 23 read x t = 23 start T2 speculative start read y t = 24 T4 lock speculative start

validate read stamp t = 23

unlock

write x t = 23

inc stamp?

cleanup

end

T5 lock speculative start

validate read stamp t = 24

unlock

write y t = 24

inc stamp?

cleanup

end

Figure 1: Example of lazy vs. split-increment stamps. Time from left to right. T1 and T3 use lazy stamps. With them there is no way for T2, which starts at 𝑡 = 23, to determine which version of 𝑥 to read. To be strictly serializable it must read from T1, but it cannot see the 𝑦 from T3 since it has not yet happened, but the write of 𝑦 happened at the “same time” as the write to 𝑥. To be opaque, T2 must abort on reading 𝑥, increment the stamp, and restart. T4 and T5 use split-increment stamps. In this case T2 starts at 𝑡 = 24 and it is safe for it to use the value of 𝑥 from T4. T4 will not need to increment the stamp if another transaction has incremented it since its read stamp. code, it can force read-only transactions to abort even when using multiversioning. We introduce split-increment timestamps to avoid this problem. As with lazy stamps, they typically avoid increments, but they ensure that the ordering of a read is never ambiguous. This allows the system to defer the aborts, and also avoids any aborts on read-only transactions. The idea is to read the stamp early during the commit phase, and then increment it at the very end of the transaction (after all locks are released and cleanup is complete), but only if it has not been incremented by another transaction in the meantime. Under high contention on the clock most transactions do not need to do the increment since some other thread has incremented the stamp in the meantime. The correctness is subtle. We prove that this is safe (Section 4) and show experimentally that it is efficient—not quite as efficient as lazy stamps, but much more efficient than eager stamps. Figure 1 illustrates the problem with lazy stamps, and how split-increment stamps avoid the problem.

2.5

Privatization and Contention

An issue that is understood in the literature [14, 28, 53], but not commonly addressed by existing STM systems is the interoperability of transactional and non-transactional code. In particular, user programs might require that variables previously accessed inside a transaction be used outside of the STM context (privatization) or vice versa (publication). The question is how can an STM provide privatization (and publication) safety. This is more of a problem with optimistic systems than pessimistic ones [28]. Based on ideas of Khyzha, Attiya, Gotsman and Rinetzky (KAGR) [28] we supply fence operations. In addition to a global fence suggested by KAGR, we supply a per location fence. This is discussed further in the full version [26]. With regards to contention, there are several features of µSTM that are designed to improve performance under high contention.

µSTM: A Lightweight and Efficient STM

Firstly µSTM aims to minimize the work that is performed in the critical region in the commit phase when locks are taken. Under high contention, the critical regions sequentialize and hence reducing the time in the region reduces the critical path of the computation. To this end, we ensure that no memory management is performed in the critical region. In the allocate-swap-retire approach the allocate is performed before the critical region and the retire after. All user allocations and deletes are performed in the speculative phase. Also, with split-increment timestamps any increments of the stamp are performed outside of the critical region. Within the critical region we only read the stamp. Secondly, we use try locks with early validates and aborts. In particular, before even trying to take a lock we check that the location is still valid and abort if not. Although not strictly necessary for correctness, in practice most locations that are written are also read. This means that if the validate on a write location fails, the transaction is most likely to abort during the read validations. Hence, taking the lock was a waste, possibly delaying other threads. Using try locks instead of strict locks has a similar benefit. If a lock is busy when encountered, the transaction with the lock will update the location. Hence the transaction that sees the busy lock will, again, likely abort due to a validation failure on the location.

3

Algorithm

Here we describe our algorithm. We first describe the data structures we use and then how we implement the various operations. We present pseudocode in this section, and the full C++ code is given in the appendix. They do not match exactly since we can make some simplifications in the pseudocode (e.g. the C++ code has to account for the fact that the memory is not sequentially consistent).

3.1

Data structures

In contrast to most other multiversioned STMs, µSTM allows the client to read and write directly to normal memory locations. That is, the most recent version of every value is stored not in a version list, but rather at the location itself. In a sense, the location is the head of the version list, which is detached from the remainder of the list. Every location is hashed to a lock that protects that location; this function is not necessarily injective, however, and multiple distinct locations may hash to the same lock. Thus, a single lock may protect multiple locations. Every lock maintains its status—whether locked or unlocked— plus either the thread id of its owner (if locked), or the timestamp of the transaction that most recently updated some location hashing to that lock (if unlocked). Every lock also maintains a version list of all previous accessible versions of locations hashing to that lock, sorted in non-increasing order of timestamp. Because these version lists are heterogeneous— multiple locations may hash to the same lock—every version link also maintains not only a value and timestamp, but also the location holding that value at the timestamp. The implementation of these version locks is described in Figure 2. A transaction descriptor maintains information describing the current state of a transaction. It records various information and statistics, including whether the transaction is read-only, a flag to indicate whether some of the reads

SPAA ’26, July 06–10, 2026, London, United Kingdom

1 2 3 4 5

struct version_link = next // pointer to next link data // value of this version stamp // timestamp of that link loc // pointer to location versioned by this link

7

global_stamp = 0

9 10 11

thread_local tid thread_local late_read = false thread_local start_stamp = load(global_stamp)

13 14 15 16 17

next_stamp(prev_stamp) = let (curr_stamp, success) = CmpX(global_stamp, prev_stamp, prev_stamp + 1) if success return prev_stamp + 1 else return curr_stamp

19 20 21 22 23

enum lock_status = // Lock acquired by thread with tid | Locked tid // Lock not acquired, store most recent timestamp | Unlocked stamp

25 26 27 28 29

struct lock = // whether lock currently acquired, and if so by whom status : atomic<lock_status> // Version list protected by lock verlist : atomic<version_link*>

31 32 33 34 35

// cons a new link onto the version list protected by a lock add_link(lck : lock, link : version_link*, prev_stamp) = link->next = load(lck.verlist) link->stamp = prev_stamp store(lck.verlist, link)

37

enum lock_result = SelfLocked | Acquired stamp | Failed

39 40 41 42 43 44 45 46 47 48

try_lock(lck) : lock_result = status = load(lck.status) case status of | Locked tid' => if tid = tid' then return SelfLocked else return Failed | Unlocked stamp => if stamp < start_stamp and CAS(lck.status, status, Locked tid) return Acquired stamp else return Failed

50

unlock(lck, stamp) = store(lck.status, Unlocked stamp)

Figure 2: Versioned Lock Pseudocode and API may have been out of date, whether the transaction is currently in a constructor, the identifier of the thread, and the start timestamp of the transaction. Additionally, every transaction descriptor maintains read and write logs. Every read log entry just maintains the location read itself, whereas every write log entry also maintains the timestamp of the previous update to that location and a pointer to a (detached) version link that contains the value written to the location within the transaction. Finally, every transaction also maintains an allocation log that records locations allocated within a transaction (which must be deleted to avoid a memory leak if the transaction is aborted). It also maintains a delete log comprising all locations deleted within a transaction—these locations are retired upon commit.

3.2

Loads

A load on location 𝑙 first checks whether 𝑙 is in the write log; if so, it just returns the corresponding value so that the transaction correctly reads its own writes. Otherwise, it adds the location to

SPAA ’26, July 06–10, 2026, London, United Kingdom

the read log so that the read can be validated later. Loads then attempt to read out the current value from the location. Doing so naively—by simply reading the bytes from the location—would be unsafe, as a concurrent writer could update the location during the read. Thus, every load must ensure that no concurrent write occurred during the course of this read. It accomplishes this by first recording the timestamp of the most recent update to the lock protecting 𝑙, reading the bytes out of 𝑙, and then examining the timestamp again. If the timestamp has not changed and the lock is not acquired, then no write was concurrent with the read, and the bytes read out were valid. Furthermore, if the timestamp is less than the start timestamp of the transaction, the value read corresponds to the most recent value committed before the transaction began, and thus is the correct value to return. Otherwise, some other transaction may have updated the location since the start timestamp, and the transaction must eventually be aborted if it is not read-only. We record this fact by setting the late_read flag rather than aborting immediately. This ensures that our system is indeed “abort-free” and waits until the client code completes to abort the transaction. The load then chases down the version list of the lock for location 𝑙 to find the most recent version link earlier than the start timestamp 𝑡𝑖 that matches the location, and returns the associated value.

3.3

Stores

Storing value 𝑣 to a location 𝑙 first allocates a new, detached version link that temporarily stores 𝑣. Then, a log entry containing this new version link, the location 𝑙, and value 𝑣 is appended to the write log. This version link is then immediately added to the delete log for the transaction. This at first glance seems unsafe, but the fact that (1) the delete log is not processed until the transaction completes, and (2) when processed it is retired rather than deleted, and (3) our integration of epoch-based memory reclamation within the system ensures that this location will never be freed while another transaction is still reading it. This is implemented by pseudocode in Figure 4.

3.4

Commit

We now describe the commit phase for a transaction 𝑇1 beginning at timestamp 𝑡𝑖 . If 𝑇1 ’s write log is empty, there is nothing to do besides retiring all of the locations freed by the client code during the speculative phase. Otherwise, if the transaction performed an “out of date” read—that is, some transaction 𝑇2 following 𝑇1 wrote some location read by 𝑇1 , then 𝑇1 is aborted. Otherwise, the transaction tries to acquire every lock protecting a location in the write log. Acquiring a lock lck fails if the most recent update to a location protected by lck occurred at a time following 𝑡𝑖 , or if the lock is already taken. If acquiring any of the locks fails, the transaction aborts. The transaction then reads the timestamp, which becomes the commit timestamp and is assigned to all writes if the commit succeeds. The read set of 𝑇1 is then validated. To do so, every lock protecting a location in the read log is inspected. If no update following timestamp 𝑡𝑖 has written to some location protected by any of these locks, then the validation succeeds. Otherwise, validation fails, and the transaction aborts. If all of the locks are acquired, then

Zachary Kent, Guy E. Blelloch, and André Costa

1

enum last_update = Self | Other stamp

3 4 5 6 7

struct write_log_entry = loc // pointer to location written to old_stamp // stamp of previous write to location link // version link to be added for previous write size // size in bytes of data stored to location

9

thread_local tid

11

thread_local start_stamp

13 14 15 16

validate_read(lck) : bool = case load(lck.status) of | Locked tid' => return tid = tid' | Unlocked stamp => return stamp < start_stamp

18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

commit() : bool = if read_only // Never abort return true if late_read return false for every entry `e` in write log case try_lock(lock(e.loc)) of | Failed => return false | Acquired prev_stamp => e.old_stamp <- Other prev_stamp | SelfLocked => e.old_stamp <- Self commit_stamp = load(global_stamp) for every entry `e` in read log // validate all reads if not validate_read(lock(e.loc)) then return false for every entry `e` in write log Swap the bytes of `e.loc` and `e.link.data` let prev_stamp = case e.old_stamp of | Self => commit_stamp | Other prev_stamp => prev_stamp add_link(lock(e.loc), e.link, prev_stamp) Release all acquired locks Retire every location in delete log // Ensure global stamp is greater than commit stamp next_stamp(commit_stamp)

43 44 45 46

abort_transaction(stm, desc) = Release all acquired locks Retire all locations in allocation log next_stamp(start_stamp)

Figure 3: Transaction Commit and Abort the transaction will commit. It first fetches the end timestamp 𝑡 𝑓 . With all of the write locks acquired, the entries in the write log are published globally. When a write log entry for location 𝑙 is applied, the corresponding value 𝑣 written during the speculative phase is stored in a detached version link. It then swaps the data within the version link and location, so that the version link contains the previous value, and the location itself stores the new value written by the transaction. This version link is prepended to the version list for the lock protecting location 𝑙 (that is currently held by the transaction). Finally, after all writes are applied, the locks held by the transaction are released and the global clock is incremented if it is still equal to the commit stamp. This algorithm is implemented in pseudocode in Figure 3. If a transaction is aborted, all locks held by the transaction are released, every allocation in the allocation log is freed, and the global clock is incremented if it is equal to the transaction’s start timestamp.

3.5

Transactions

We now describe the process for running a thunk 𝑓 containing client code within a transaction 𝑇 . First, the start timestamp 𝑡𝑖 is

µSTM: A Lightweight and Efficient STM

fetched. Then, the thunk 𝑓 is executed. Recall that a late_read flag is set during transaction execution if the transaction performed an out-of-date read—in particular a transaction serializing after 𝑡𝑖 committed a data item that was read by the transaction. If so, and furthermore 𝑇 is not a read-only transaction, then 𝑇 is aborted and retried. Otherwise, the transaction attempts to commit according to the logic in Section 3.4. If this process succeeds, then the transaction has committed its writes (if any). Otherwise, the transaction is aborted and retried.

3.6

Memory Management

We employ epoch-based memory reclamation (EBR) [19] to manage shared pointers. Every thread participating in EBR announces when it enters a critical section, and unannounces when it exits the critical section. A global epoch approximates real time, and is incremented whenever every thread has announced the current epoch. When a thread retires a memory location, this location is placed into a limbo list for the current epoch. A limbo list maintaining retired pointers from the previous epoch is also maintained. When the global epoch is incremented, all of the locations in the oldest limbo list are freed, and the current limbo list becomes that for the previous epoch (which was just incremented). The limbo list for the previous epoch is reset to empty. We employ a custom implementation of EBR uepoch that uses thread-local limbo lists and only frees pointers from epoch at most 𝑒 −3 where 𝑒 is the current global epoch. Inside a transaction, an epoch is announced before taking a start timestamp and then unannounced after running client code.

3.7

Synchronization Between Memory Management and the Global Clock

Recall that when a transactional write of value 𝑣 to location 𝑙 is performed, a tentative version link with value 𝑣 is created and then immediately placed in the delete log. When (if) the transaction is committed, every item in the delete log is retired, including version links for previous values of locations that were written to by the transaction. We must ensure that no transaction attempts to read a version link that has already been freed. In particular, consider a transaction 𝑇 beginning at 𝑡𝑖 that scans down the version list for location 𝑙. It searches for the most recent version link with timestamp less than 𝑡𝑖 . The worry is that this version link could be retired, which is indeed possible with split timestamps. In particular, another transaction 𝑇 ′ committing a data item read by 𝑇 could serialize at 𝑡𝑖 , in which case 𝑇 continues scanning down the version list past that committed by 𝑇 ′ , which may be garbage. We resolve this by incrementing the timestamp before incrementing the epoch. Intuitively, this ensures memory safety by maintaining the invariant that the global clock is always at least the epoch so that transactions do not attempt to read too far into the past. Formally, we have the following theorem: Theorem 3.1 (Memory Safety). No transaction accesses a freed link. Proof (Sketch). Consider a transaction 𝑇 with start stamp 𝑡𝑖 traversing a version list and any link ℓ this traversal reaches. Let 𝑐 be the commit stamp of the transaction 𝑇 ′ that committed ℓ, and let 𝑒 be the value of the global epoch when 𝑐 was read from the global clock.

SPAA ’26, July 06–10, 2026, London, United Kingdom

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

load(loc) = if loc is in write log return data stored in associated version link let lck = lock(loc) Let buf be a temporary buffer hd <- nullptr // Pointer to head of version list for lck // Timestamp of most recent update to lck last_stamp <- -1 while true do initial_status = load(lck.status) case initial_status of | Locked _ => // version lock acquired, try again continue | Unlocked stamp => Copy the bytes of loc to buf hd <- load(lck.verlist) let final_status = load(lck.status) if initial_status != final_status // lock state changed during read continue last_stamp <- stamp if last_stamp < start_stamp // last update serialized before txn start return buf // Otherwise read was consistent but out of date break done // Another transaction committed a write after we began late_read <- true // Chase down version list to find correct version result <- buf while last_stamp >= start_stamp and hd != null if hd->loc = loc then result <- hd->data last_stamp <- hd->stamp hd <- hd->next // Deepest matching link holds the correct version return result

40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

store(loc, val) = // Allocate version link storing new value to write let link = new version_link { next = nullptr, data = val, stamp = None, loc = loc } // Alloc-swap-retire: retired when txn completes Add link to delete log let entry = { loc = loc, data = val, old_stamp = None, link = link, } Add `entry` to write log

Figure 4: Transactional Load and Store Pseudocode

Because ℓ is traversed, it must be the case that 𝑡𝑖 ≤ 𝑐, as the stamp associated with ℓ is at most 𝑐. Every increment of the epoch past 𝑐 (beyond at most one that may have been in-flight prior to the read of 𝑐 by 𝑇 ′ ) is preceded by an increment of the clock. 𝑇 read start stamp 𝑡𝑖 ≤ 𝑐 after announcing its epoch, so 𝑇 announces epoch at most 𝑒 + 1. The epoch cannot advance beyond epoch 𝑒 + 2 during the execution of 𝑇 , and uepoch only frees pointers from epochs that are older than 2 less than the global epoch, so 𝑇 never traverses a freed link. The full proof is given in the full version [26]. □

SPAA ’26, July 06–10, 2026, London, United Kingdom

4

Correctness

In this section we outline a proof of correctness of the approach. Various different correctness criteria exist for transactional systems, including (strict) serializability, and opacity. Serializability requires that all transactions appear to take place atomically in some serialized order. Strict serializability furthermore requires that this serialized order preserves the real-time order of transactions—i.e. if 𝑇𝑎 commits before the invocation of 𝑇𝑏 , then 𝑇𝑎 precedes 𝑇𝑏 in the serialized order. Strict serializability is typically given as the strongest correctness criterion within the database community, but is too weak for STM systems. (Strict) serializability speaks only of committed transactions, whereas the semantics of STM systems must also consider the behavior of aborted transactions. In particular it is desirable that even aborted transactions see only a “consistent” snapshot of shared state. Otherwise, programmers may make assumptions that do not hold inside of aborting transactions. Opacity guarantees exactly this [20], requiring that even aborted transactions serialize at some point between invocation and abort. As stated by the following theorem, µSTM guarantees opacity. Theorem 4.1 (Opacity). Any history of µSTM transactions is opaque. Proof (Sketch). It suffices to show that all transactions serialize at some point between their invocation and response, including aborted transactions. Read-only transactions serialize when they read the start stamp. Aborted (update) transactions also serialize when they read the start stamp. A committed update transaction with commit stamp 𝑡 𝑓 serializes when the global clock is incremented from 𝑡 𝑓 to 𝑡 𝑓 + 1, as this is when the writes become globally visible to readers. Note that this may be after the locks are released by the updating transaction, as the update transaction invokes next_stamp after the locks are released. Regardless, this increment must occur before the transaction returns. Intuitively, these serialization points are consistent because a read by a transaction with start stamp 𝑡𝑖 will only observe the writes performed by an update transaction with commit stamp 𝑡 𝑓 < 𝑡𝑖 . Hence when the global clock advances beyond 𝑡 𝑓 , all writes installed by that update become globally visible. Note that multiple transactions may share the same commit stamp, and thus one clock increment may serialize multiple updaters. The write sets of such transactions must be disjoint, as otherwise lock acquisition would fail. There can still exist anti-dependencies between transactions sharing the same timestamp. Consider transactions 𝑇1 and 𝑇2 that read and write location 𝑥, respectively. If 𝑇1 validates the lock protecting 𝑥 before 𝑇2 acquires it, then this orders 𝑇1 before 𝑇2 yet they share the same commit stamp. However, these (anti) dependencies are acyclic, and such transactions may be serialized topologically. The full proof is given in the full version [26]. □

5

Experiments

We evaluate µSTM on a variety of different workloads, comparing its performance to other state of the art STMs, demonstrating that

Zachary Kent, Guy E. Blelloch, and André Costa

µSTM matches or exceeds performance of these systems without sacrificing simplicity or generality. Setup. All experiments are run on a 96-core Amazon Web Services c7i-metal instance with 2x Intel(R) Xeon(R) Platinum 8488C (48 cores and 3.2 GHz), and 384 GB memory. Each core is 2-way hyperthreaded, giving 192 hyperthreads. The machine runs with Ubuntu 22.04.1 LTS, and the code was compiled using g++11 with -O3. Systems Tested. We benchmark against fuse [4], Multiverse [10], and 2PLSF [46]. The first two are state of the art optimistic multiversioned TMs, whereas 2PLSF is a state of the art pessimistic single-versioned TM, allowing for a robust comparison across different design spaces. We do not present experiments for DCTL [45], as its implementation is proprietary, or TinySTM [17], because it could not execute without crashing in most experiments. Workloads. Our workloads are based on those from YCSB benchmark suite [11], which is commonly used to benchmark key-value stores2 . Our benchmarks consist of measuring the throughput of transactions consisting of inserts, finds, and deletes to random keys within a key-value store. We implement this store using various data structures and vary different YCSB parameters, measuring the throughput over this mix. In particular, we implement the keyvalue store (in different experiments) using a Linked List, Skip List, B-tree, Adaptive Radix Tree (ART) [33], Treap, AVL tree, Leaf Tree, and Hash Table. The leaf tree is a simple binary tree where data is only stored at the leaves. All of these data structures are simply sequential implementations. For each backing data structure, we vary (a) data structure size (denoted by 𝑛), (b) update percentage, (c) number of operations per transaction, (d) number of threads, and (e) zipfian parameter. Every data structure is initially prefilled to size 𝑛 with keys selected uniformly at random from a universe 𝑈 of 2𝑛 64-bit keys total. Every key is associated with a corresponding 64-bit value. In the timed portion of the code, each thread executes transactions consisting of inserts and deletes (in equal numbers) and finds. Keys for these operations are also sampled from 𝑈 , but according to a zipfian distribution specified by 𝑧. 𝑧 ranges from 0 (uniform) to 0.99 (highly skewed). This models common access patterns to databases, in which most accesses are concentrated around “hot” keys. We measure the throughput in operations per second over different mixes of parameters and backing data structures. When unspecified, we fix every parameter at its default. The default size for list data structures is 300, whereas for all others it is 106 . These remaining default values are 𝑢 = 5% updates, 𝑡 = 4 operations per transaction, 𝑝 = 192 threads, and zipfian 𝑧 = 0.75.

5.1

Geometric Mean Performance

Our first set of experiments aim to compare the average performance of the STM systems under test over a wide variety of different workloads. To this end, we measure the throughput of every system for every combination of the following parameters: • Update Percentage ∈ {0%, 5%, 50%} • 𝑛 ∈ {102, 103 } for linked list, 𝑛 ∈ {105, 106, 107 } for all other structures 2 Our workloads are not literally taken from YCSB, since we do not classify different

parameter regimes into workloads A/B/C/D/E as in YCSB

µSTM: A Lightweight and Efficient STM

SPAA ’26, July 06–10, 2026, London, United Kingdom

(a) Varying Thread Count

Figure 5: Geometric mean of throughput across 3 sizes, 3 zipfian parameters, 3 update%, and 3 transaction sizes. Normalized to the highest throughput per structure. • Transaction Size ∈ {1, 4, 16} • Zipfian ∈ {0, 0.75, 0.99}. For every STM system and backing data structure, we then calculate the geometric mean of the throughputs across this mix of parameters. The results are shown in Figure 5, where the geometric means are grouped by data structure and normalized to the max per structure. As we can see, µSTM achieves the highest throughput across all data structures over this parameter mix.

5.2

(b) Varying data structure size

(c) Varying skew

Varying Parameters

Our next set of experiments fixes all but one YCSB parameter, which is varied across a range of different values. We then measure how the performance of each system changes as this parameter changes, allowing us to compare the relative performance of different STMs on different workloads. We evaluate one data structure with high fanout (the B-tree), another with low fanout (the AVL tree), and the hashtable; scaling within each class is similar. Thread Count. Figure 6a displays the scalability of the different STM systems with respect to thread count. We see that all STM systems scale well with thread count except 2PLSF, which levels off around 128 threads. This is because their implementation of readerwriter locks is not scalable. In particular, for 𝑝 threads, acquiring a write lock requires scanning 𝑝 read indicators to ensure that no thread has taken a read lock. Multiverse also does not scale well beyond 128 threads on data structures with high fanout like the B-tree. Because these trees have wide fanout and are thus shallow, most writes are concentrated on a few select nodes along the root to leaf path. Furthermore, Multiverse employs eager locking for writes, acquiring write locks during the traversal phase. Readers will abort if they encounter a lock acquired by a writer even if that writer will later abort. Hence writers can starve readers even if they later abort, and this is more likely to occur in data structures with high fanout. Data structure size. We examine how the throughput of different STM systems changes with data structure size in Figure 6b. We see that µSTM scales well up to ∼ 106 . At this point, the data structure likely no longer fits in L2 cache, and beyond 107 the working set can no longer fit in the L3 cache. µSTM is designed so that the lock table fits in L3 cache, so this is expected beyond this point. The program becomes memory bound, and the throughput of all STMs degrades as expected. Zipfian. Figure 6c compares the throughput of different systems while increasing the skew of the key distribution. When keys are

(d) Varying update rate

(e) Varying transaction size

Figure 6: Comparison of throughput between 2PLSF, fuse, Multiverse, and µSTM (higher is better). uniformly distributed, all STM systems achieve high throughput, with Multiverse outperforming all other systems on some data structures, like in the Hash Table. The throughput of µSTM and fuse is mostly stable as zipfian increases, whereas the throughput of Multiverse and 2PLSF falls significantly even at the relatively low default update rate (5%). Again, this is especially pronounced for data structures with high fanout where the average traversal is short. We believe that this is due to 2PLSF and Multiverse’s eager acquisition of locks. Additionally, we see that Multiverse performs extremely well for data structures with a short traversal at low contention—this is especially noticeable for the Hash Table, where Multiverse achieves twice the throughput of µSTM at low zipfian. This is one regime in which lazy timestamping performs much better than split timestamping. In µSTM, an update transaction must increment the global clock if it has not changed between when the commit stamp is taken and when the locks are released. This is more likely for data structures with a short traversal, as transactions over these data structures will have a small read log to validate and write log to apply. In contrast, in the lazy timestamp algorithm employed by

SPAA ’26, July 06–10, 2026, London, United Kingdom

Multiverse, the global clock is only incremented on abort, which at low zipfians is highly infrequent. Furthermore, in hash tables there is a lower likelihood of two transactions conflicting due to hash buckets being independent components. Thus in this regime the heartbeat of the global clock is a bottleneck for µSTM but not Multiverse. Update Rate. Figure 6d compares the throughput of different systems for increasing update rates. For read-only transactions, Multiverse often achieves the highest throughput of any STM. Because locations are only versioned when contended, Multiverse operates in single-versioned mode for the read-only workload, achieving high throughput. 2PLSF also performs well for read-only workloads; the implementation of scalable read indicators distributes the read indicators for different threads across uncontended cache lines, minimizing overhead for read-only transactions. However, the throughput of 2PLSF and Multiverse quickly declines as update rate increases. This is because, as discussed, both 2PLSF and Multiverse suffer at high contention. Furthermore, 2PLSF’s implementation of scalable reader-writer locks penalizes writers by forcing every writer to scan 𝑝 read indicators to acquire a write lock. Again, the decline in Multiverse’s throughput is not uniform across data structures, and is more pronounced for data structures with higher fanout like the B-tree. Transaction Size. In Figure 6e, we compare the throughput of different implementations against varying transaction size. We see that the performance of 2PLSF and µSTM decays only modestly with an increasing number of operations per transaction, whereas that of fuse and Multiverse quickly drops off. Again this is because Multiverse suffers under contention, and a larger number of operations per transaction increases conflicts. Additionally, we see that µSTM performs relatively poorly at a small number of operations per transaction for the chaining hash table, but improves markedly with a larger number of operations per transaction. This is because lazy-timestamping generally performs better than split-timestamping under low contention with shortrunning transactions. Under such workloads—especially those with few operations per transaction—the commit phase of every transaction is very short. For µSTM, this means that it is less likely that the global clock was incremented between the point when the commit stamp of a transaction is read and when it is later possibly incremented after the locks are released, and more transactions have to increment the global clock.

5.3

Range Queries

We compare the throughput of different STMs for range queries. For this experiment, 50% of threads (the writers) execute transactions consisting of four update operations at keys uniformly sampled from 𝑈 (𝑧 = 0). The remaining 50% of threads execute range queries, which are read-only transactions that uniformly sample a start key from 𝑈 and perform contiguous read operations starting from that key for a specified range size. A range query samples a start key 𝑘 and reads keys [𝑘, 𝑘 + 𝑟𝑎𝑛𝑔𝑒_𝑠𝑖𝑧𝑒]. In Figure 7, we examine how the throughput of both the range queries and update transactions change with increasing range size on the B-tree—the data structure supporting most efficient range scans. fuse and µSTM generally achieve the highest range query

Zachary Kent, Guy E. Blelloch, and André Costa

Figure 7: Range Query Throughput. Left is the throughput of the range queries themselves, right is the throughput of updaters across increasing range sizes throughput across all sizes. We see that the range query throughput scales inversely with range query size, as expected. However, the range query throughput of 2PLSF does not scale significantly worse than the other multiversioned STMs, which may be surprising. In contrast, the update throughput of 2PLSF falls greatly with higher range size, whereas that of other STMs is stable. This is because of how 2PLSF arbitrates conflicts between different transactions to ensure starvation-freedom. Transactions with earlier start timestamps are given priority, and can abort those with later timestamps. Long-running range queries will generally have lower timestamps than newer update transactions, giving the range queries priority and aborting the short-lived writers.

5.4

Ablation Studies

We now perform two ablation studies to determine how removing different features of fuse and µSTM affects throughput. The results are shown in Figure 8.

Figure 8: Ablation studies Timestamp Algorithms. In one ablation study we compare the performance of variants of fuse and µSTM that employ different timestamp algorithms. We measure the throughput of these variants on the same YCSB-like benchmark for the B-tree across increasing update rate. The two variants fuse-HWStamp and µSTM-HWStamp use a hardware counter (based on the x86 rdtsc instruction). The default variant of fuse uses an eager timestamp mechanism, incrementing the clock on every transaction. We also include a variant of µSTM that employs the lazy timestamp algorithm introduced by [45], and two eager variants that increment the clock on every transaction. One simply uses a hardware fetch and add, while the other employs a more complex software implementation of fetch-and-add, aggregating funnels [50]. Aggregating funnels use software combining to batch different fetch-and-add operations. We see that both hardware timestamp algorithms are the fastest across all update rates, as expected. The split and lazy timestamp algorithms achieve basically equal performance, and are only ∼20%

µSTM: A Lightweight and Efficient STM

5.5

Comparison to Fine-Grained Concurrency

In this section we demonstrate that µSTM does not introduce significant overhead relative to fine-grained concurrent data structures— in particular, a B-tree, AVL tree, and hashtable implemented using optimistic locking (OL) [30]. OL is a technique that allows most of the traversal in these search structures to proceed without locks. Our baseline measures the throughput of singular OL operations on the same YCSB workload not wrapped in any transaction. We compare this to the throughput of transactions over the corresponding STM data structures comprising 𝑡 operations. For this experiment, we set 𝑛 = 106 and 𝑧 = 0 to measure transactional overhead and reduce the confounding effects introduced by contention-induced aborts; the results over increasing 𝑡 are shown in Figure 9. We see that the throughput of the baseline is relatively stable across increasing 𝑡, whereas for the various STM systems it increases up to 𝑡 = 8 and then stabilizes; at this point, the cost of the operations themselves dominates the startup cost. Overall, the disparity between µSTM and the baseline is relatively low, stabilizing at about 20% for the B-tree and the Hashtable.

5.6

Non-trivial Types

We now evaluate the performance of µSTM over the same YCSBlike benchmark when used with non-trivial types. The key-value store for this experiment is backed by a probing hashtable that stores buckets inline. We compare the throughput of this hashtable with three types of keys and values: integers, short strings, and long strings. The strings are implemented using a parlay::sequence that supports the same API as std::vector. The container uses a short string optimization (SSO) that stores the string itself inline

STM

Throughput (MOps/s)

2PLSF

Multiverse

OL (no wrap)

AVL Tree

Hash Table

250

400

200

300

150

200

100

100

50

0

Fuse

B-tree

500

0

5

10

15

20

25

Ops per Transaction

0

30

2000 1500 1000 500 0

5

10

15

20

25

Ops per Transaction

30

0

0

5

10

15

20

25

Ops per Transaction

30

Figure 9: Evaluation of the transactional overhead of different STM systems over different numbers of operations per transaction on different Optimistic Locking (OL) data structures. The green line represents the throughput of OL operations not wrapped in transactions.

Non-trivial types Integer Long String Short String

600

Throughput (MOps/s)

slower than the hardware variants. Moreover, they scale well with update rate—the drop in throughput is not greater than the hardware timestamp variants. Hence the heartbeat of the central software clock is not a bottleneck, even at high contention. Finally, we see that all eager variants, including the default timestamp variant of fuse and both eager variants of µSTM, achieve relatively poor performance with increasing update rate. The vanilla eager variant of µSTM achieves especially poor performance, with performance dropping dramatically even at 5% updates. The variant based on aggregating funnels achieves throughput that is generally twice as high across increasing update rate, but is still comparably low. Thus, the bottleneck in STMs that use eager timestamp algorithms is the heartbeat of the central clock. Abort variants. Our second ablation study compares the throughput of variants of µSTM employing different abort strategies across increasing update rate. We include the default multiversioned abortfree variant, a multiversioned variant with early aborts implemented using longjmp, and two single-versioned variants which by necessity must abort early. One variant also uses longjmp to implement aborts, while the other uses exceptions. Overall, the throughput of all versions is comparable. The single-versioned implementations achieve slightly higher throughput for read-only workloads, but fall off with higher update rate. For all update rates, we see that the overhead of multiversioning is relatively low. Moreover, early aborts do not achieve higher throughput by avoiding wasted work.

SPAA ’26, July 06–10, 2026, London, United Kingdom

400 200 0

0

20

40

60

80

Update Rate (%)

100

Figure 10: Throughput of a Figure 11: TPC-C Benchmark probing hash table on a YCSBlike benchmark with different key/value sizes. with the container, whereas the long string must be stored through a level of indirection. In both cases the size of the parlay::sequence is 16 bytes (but with the long string stored via an additional indirect slot). The integer key is 8 bytes. For each class of value, the value itself is fixed at an arbitrary value: a 1-byte string for short string and 20-byte string for long string. For short strings, the key space is the set of string representations of every integer in the range [0, 2𝑛), whereas for long strings it is the string representation of the hash of every integer in this range. For 𝑛 = 106 , every short string key fits inline, whereas it is highly likely that every long string value does not. Results are shown in Figure 10 across increasing update rate where the other YCSB-like parameters are fixed at their defaults. We see, as expected, that the variant employing integer keys achieves the highest throughput, with the variant employing short strings achieving about 20% lower throughput. This disparity is due to several factors. Each bucket consists of one 8-byte integer key plus the size of the value; thus each bucket employing integer values requires 16 bytes, whereas that employing short strings requires 32. Hence the data structure is twice as large, and more of it resides in L3 vs. L2 cache. Additionally, the cost of transactional reads to larger data types is higher, especially under contention; the sequence lock mechanism of reads requires reading the value until it is stable. The disparity in throughput between short and long strings is much greater; every insert of a long string entry requires two allocations (one for the key, and one for the value), and hashing/probing this key requires a level of indirection to access the string itself.

SPAA ’26, July 06–10, 2026, London, United Kingdom

Zachary Kent, Guy E. Blelloch, and André Costa

6.1

Figure 12: Comparing AVL Tree, B-Tree and Hash Table on Intel, AMD and ARM.

5.7

TPC-C Benchmarks

We evaluate the three highest-performing transactional data structures on a TPC-C-like benchmark suite [12]. TPC-C is commonly used to benchmark Online Transactional Processing (OLTP) systems. TPC-C tables maintain data for different warehouses, like the stock of items available there, and transactions mutate these data. For our experiments, the number of warehouses is fixed at 192 (the number of hardware threads). The results of our TPC-C benchmark are shown in Figure 11, which measures the throughput of databases backed by an ART, B-tree, and hash table. µSTM achieves the highest throughput across all data structures—this is particularly notable for the ART.

5.8

Comparing Architectures

Finally, we benchmark each system on two additional architectures. These results include the Intel machine used in previous experiments, an 80-core ARM Neoverse N1 (up to 3GHz, 1 NUMA socket, no hyperthreading, and no L3 cache) and a 96-core AMD EPYC 9R14 (up to 3.3GHz, 1 NUMA socket, 256 MB L3 Cache, 2-way hyperthreading). These machines present a diverse architectural spectrum as the AMD and Intel machines implement the same ISA but with different microarchitectural choices, and the ARM machine has a different ISA and design philosophy (e.g., relaxed memory ordering and no L3 cache). Results for each machine on AVL Tree, B-Tree, and Hash Table structures can be seen in Figure 12. On both Intel and AMD µSTM completely outmatches the other STMs, performing 33% − 47.5% better when compared to the next best system in each benchmark. Surprisingly, while on Intel there is a clear hierarchy, on AMD the story changes and fuse, 2PLSF and Multiverse have relatively equivalent performance. Lastly, on ARM fuse becomes a close competitor on all data structures and Multiverse performs just as well as µSTM on the hash table. We note that µSTM had significant performance degradation for read-heavy workloads on ARM, due to designing the lock table to fit in L3 cache (which the ARM machine does not possess). Indeed in our experiments, making the lock table smaller improved µSTM performance in these cases. Still, we decided not to show results with this modification in order to refrain from hyper-optimizing to a certain hardware.

6

Discussion

We discuss some of the implementation details and limitations that guided our design of µSTM.

Hardware Timestamps

Timestamping is most commonly implemented as a single shared counter that is incremented atomically. Yet, as we show in Section 5.4, a more performant variant involves utilizing hardware cycle counters to establish a happens-before relation. However, a cycle counter is required to fulfill two key properties to qualify [51]: 1) processors see their own clock as strictly monotonic (locally monotonic) and 2) if two instructions executed concurrently are ordered, then their clock values must reflect the same ordering (globally monotonic). The problem lies in ensuring that the hardware actually provides these properties. Ruan et al. [51] cite private conversations with an Intel engineer regarding the guarantees provided by the rdtscp instruction. Although on Intel we have indeed experimentally observed these properties, the same cannot be said for AMD machines, even though they implement the same ISA. Similarly, Kashyap et al. [25] cite private conversations when mentioning that clocks in Intel machines have constant skews, an assumption they heavily rely on. On ARM machines, we were able to successfully use hardware cycle counters (based on Linux Kernel’s implementation [35]) and observed similar results to the ones in Section 5.4. Since these properties remain undocumented, we view hardware stamping as a non-portable alternative to lazy or split timestamping that should be used when available and appropriate.

6.2

Sequence Locking

To load and store non-atomic user data bytewise atomically we use an idiom often used with sequence locks [6, 23, 32, 55]. Until C++20 there was no effective way to implement this so that it had fully defined behavior [6, 7]. Since C++20 std::atomic_ref can be used, although for efficiency this makes for complicated code with many special cases. We hope that C++ adopts the proposal for bytewise atomic loads and stores like that suggested by Hans Boehm [7].

7

Conclusion

In this paper, we have presented µSTM, a simple STM system that achieves both usability and generality while maintaining state-ofthe-art performance. To avoid memory leaks and other errors arising from adapting existing sequential code, we introduced and implemented deferred aborts, ensuring that user code is never aborted during the speculative phase of a transaction. To reduce the heartbeat of the central clock while maintaining safety for deferred aborts, we introduced the concept of split-increment timestamps. We then argued that our algorithm, including deferred aborts, provides opacity—the gold standard of correctness for STMs. Finally, we demonstrated that µSTM meets or exceeds the performance of state-of-the-art single-versioned and multiversioned systems.

Acknowledgments This work was supported in part by the National Science Foundation grant CCF-2119352, and a gift from Jane Street. Some experiments presented in this paper were carried out using the Grid’5000 testbed, supported by a scientific interest group hosted by Inria and including CNRS, RENATER and several Universities as well as other organizations (see https://www.grid5000.fr).

µSTM: A Lightweight and Efficient STM

References [1] Daniel Anderson, Guy E. Blelloch, and Yuanhao Wei. 2021. Concurrent deferred reference counting with constant-time overhead. In ACM Conference on Programming Language Design and Implementation (PLDI). doi:10.1145/3453483.3454060 [2] Gal Assa, Andreia Correia, Pedro Ramalhete, Valerio Schiavoni, and Pascal Felber. 2023. TL4x: Buffered Durable Transactions on Disk as Fast as in Memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [3] Philip A. Bernstein and Nathan Goodman. 1983. Multiversion Concurrency Control - Theory and Algorithms. ACM Transactions on Database Systems (TODS) 8, 4 (Dec. 1983), 465–483. [4] Guy E. Blelloch, Zachary Kent, and Yuanhao Wei. 2025. TLF: Transactional Lock Fusion. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). doi:10.1145/3694906.3743341 [5] Guy E. Blelloch and Yuanhao Wei. 2024. VERLIB: Concurrent Vesioned Pointers. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [6] Hans-J. Boehm. 2012. Can seqlocks get along with programming language memory models?. In ACM SIGPLAN Workshop on Memory Systems Performance and Correctness. [7] Hans J. Boehm. 2020. Byte-wise atomic memcpy, P1478R5. Webpage. https: //www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1478r5.html [8] João Cachopo and António Rito-Silva. 2006. Versioned Boxes as the Basis for Memory Transactions. Science of Computer Programming 63, 2 (2006), 172–185. [9] Calin Cascaval, Colin Blundell, Maged Michael, Harold W. Cain, Peng Wu, Stefanie Chiras, and Siddhartha Chatterjee. 2008. Software Transactional Memory: Why Is It Only a Research Toy? The promise of STM may likely be undermined by its overheads and workload applicabilities. Queue 6, 5 (2008). [10] Gaetano Coccimiglio, Trevor Brown, and Srivatsan Ravi. 2026. Multiverse: Transactional Memory with Dynamic Multiversioning. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [11] Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proc. 1st ACM Symposium on Cloud Computing. doi:10.1145/1807128.1807152 [12] The Transaction Processing Council. 2010. TPC-C Benchmark (Revision 5.11.0). http://www.tpc.org/tpcc/ [13] Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Mike Zwilling. 2013. Hekaton: SQL Server’s Memory-optimized OLTP Engine. In ACM SIGMOD International Conference on Management of Data (SIGMOD). doi:10.1145/2463676.2463710 [14] Dave Dice, Alexander Matveev, and Nir Shavit. 2010. Implicit Privatization Using Private Transactions. In Proceedings of the 2nd ACM SIGPLAN Workshop on Transactional Computing (TRANSACT). [15] Dave Dice, Ori Shalev, and Nir Shavit. 2006. Transactional Locking II. In International Symposium on Distributed Computing (DISC). [16] Nuno Diegues and Paolo Romano. 2015. Time-Warp: Efficient Abort Reduction in Transactional Memory. ACM Transactions on Parallel Computing (TOPC) 2, 2, Article 12 (June 2015), 44 pages. [17] Pascal Felber, Christof Fetzer, and Torvald Riegel. 2008. Dynamic performance tuning of word-based software transactional memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). 10 pages. doi:10.1145/ 1345206.1345241 [18] Sérgio Miguel Fernandes and João Cachopo. 2011. Lock-Free and Scalable MultiVersion Software Transactional Memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [19] Keir Fraser. 2004. Practical lock-freedom. Technical Report. University of Cambridge, Computer Laboratory. [20] Rachid Guerraoui and Michal Kapalka. 2008. On the correctness of transactional memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). doi:10.1145/1345206.1345233 [21] Cordelia Hall, Simon L. Peyton Jones, and Patrick M. Sansom. 1995. Unboxing using Specialisation. In Functional Programming, Glasgow 1994, Kevin Hammond, David N. Turner, and Patrick M. Sansom (Eds.). Springer London. [22] Tim Harris, James Larus, and Ravi Rajwar. 2010. Transactional Memory, 2nd Edition. Morgan and Claypool Publishers. [23] Stephen Hemminger. 2012. Fast reader/writer lock for gettimeofday 2.5.30. Linux kernel mailing list. https://lwn.net/Articles/7388/. [24] Fritz Henglein and Jesper Jørgensen. 1994. Formally Optimal Boxing. In ACM Symposium on Principles of Programming Languages (POPL). ACM, 213–226. doi:10. 1145/174675.177874 [25] Sanidhya Kashyap, Changwoo Min, Kangnyeon Kim, and Taesoo Kim. 2018. A scalable ordering primitive for multicore machines. In Proceedings of the Thirteenth EuroSys Conference (Porto, Portugal) (EuroSys ’18). Association for Computing Machinery, New York, NY, USA, Article 34, 15 pages. doi:10.1145/3190508. 3190510 [26] Zachary Kent, Guy Blelloch, and André Costa. 2026. µSTM: A Lightweight and Efficient STM Supporting General Types and Deferred Aborts. The full paper version will be made available on arXiv..

SPAA ’26, July 06–10, 2026, London, United Kingdom

[27] B. W. Kernighan and D. M. Ritchie. 1988. The C Programming Language (2nd ed.), Chapter 8 (Appendix B). Prentice Hall. [28] Artem Khyzha, Hagit Attiya, Alexey Gotsman, and Noam Rinetzky. 2018. Safe privatization in transactional memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). ACM, Vienna Austria, 233–245. doi:10. 1145/3178487.3178505 [29] Priyanka Kumar, Sathya Peri, and K. Vidyasankar. 2014. A TimeStamp Based Multi-version STM Algorithm. In IEEE International Conference on Distributed Computing and Networking (ICDCN). 212–226. [30] H. T. Kung and Philip L. Lehman. 1980. Concurrent Manipulation of Binary Search Trees. ACM Transactions on Database Systems (TODS) 5, 3 (1980). [31] H. T. Kung and John T. Robinson. 1981. On Optimistic Methods for Concurrency Control. ACM Transactions on Database Systems (TODS) 6, 2 (1981). [32] C. Lameter. 2005. Effective synchronization on Linux/NUMA systems. In Proc. of the Gelato Federation Meeting. http://lameter.com/gelato2005.pdf [33] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. In IEEE International Conference on Data Engineering (ICDE). [34] Hyeontaek Lim, Michael Kaminsky, and David G. Andersen. 2017. Cicada: Dependably Fast Multi-Core In-Memory Transactions. In ACM SIGMOD International Conference on Management of Data (SIGMOD). 21–35. Linux Kernel Source Code, File [35] Linux Kernel Developers. [n. d.]. arch/arm64/include/asm/arch_timer.h, Lines 200–210. https://github. com/torvalds/linux/blob/8e65320d91cdc3b241d4b94855c88459b91abf66/arch/ arm64/include/asm/arch_timer.h#L200-L210. [36] lisdair Meredith, Mungo Gill, Joshua Berne, Corentin Jabot, Pablo Halpern, and Lori Hughes. 2025. Trivial Relocatability For C++26: Proposal to safely relocate objects in memory. https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2025/ p2786r13.html. [37] Li Lu and Michael L Scott. 2013. Generic multiversion STM. In International Symposium on Distributed Computing (DISC). Springer. [38] Thomas Neumann, Tobias Mühlbauer, and Alfons Kemper. 2015. Fast Serializable Multi-version Concurrency Control for Main-Memory Database Systems. In ACM SIGMOD International Conference on Management of Data (SIGMOD). [39] Arthur O’Dwyer. 2024. P1144R10: std::is_trivially_relocatable. https://www.openstd.org/jtc1/sc22/wg21/docs/papers/2024/p1144r10.html. [40] Mikael Olsson. 2022. Boxing and Unboxing. Apress, Berkeley, CA, 111–112. [41] Christos H Papadimitriou and Paris C Kanellakis. 1984. On Concurrency Control by Multiple Versions. ACM Transactions on Database Systems (TODS) 9, 1 (1984), 89–99. [42] Dmitri Perelman, Anton Byshevsky, Oleg Litmanovich, and Idit Keidar. 2011. SMV: Selective Multi-Versioning STM. In International Symposium on Distributed Computing (DISC). 125–140. [43] Dmitri Perelman, Rui Fan, and Idit Keidar. 2010. On Maintaining Multiple Versions in STM. In ACM Symposium on Principles of Distributed Computing (PODC). 16– 25. [44] Dan R. K. Ports and Kevin Grittner. 2012. Serializable Snapshot Isolation in PostgreSQL. Proceedings of the VLDB Endowment (PVLDB) 5, 12 (Aug. 2012). doi:10.14778/2367502.2367523 [45] Pedro Ramalhete and Andreia Correia. 2024. Scaling Up Transactions with Slower Clocks. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). ACM. doi:10.1145/3627535.3638472 [46] Pedro Ramalhete, Andreia Correia, and Pascal Felber. 2023. 2PLSF: Two-Phase Locking with Starvation-Freedom. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [47] Pedro Ramalhete, Andreia Correia, Pascal Felber, and Nachshon Cohen. 2019. OneFile: A wait-free persistent transactional memory. In IEEE/IFIP International Conference on Dependable Systems and Networks. [48] D. Reed. 1978. Naming and synchronization in a decentralized computer system. Technical Report LCS/TR-205. EECS Dept., MIT. [49] Torvald Riegel, Pascal Felber, and Christof Fetzer. 2006. A Lazy Snapshot Algorithm with Eager Validation. In International Symposium on Distributed Computing (DISC). Springer, 284–298. [50] Younghun Roh, Yuanhao Wei, Eric Ruppert, Panagiota Fatourou, Siddhartha Jayanti, and Julian Shun. 2025. Aggregating Funnels for Faster Fetch&Add and Queues. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP) (Las Vegas, NV, USA) (PPoPP ’25). Association for Computing Machinery, New York, NY, USA, 99–114. doi:10.1145/3710848.3710873 [51] Wenjia Ruan, Yujie Liu, and Michael Spear. 2013. Boosting Timestamp-Based Transactional Memory by Exploiting Hardware Cycle Counters. ACM Trans. Archit. Code Optim. 10, 4 (dec 2013), 21 pages. [52] Michael F. Spear, Luke Dalessandro, Virendra J. Marathe, and Michael L. Scott. 2009. A comprehensive strategy for contention management in software transactional memory. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). doi:10.1145/1594835.1504199 [53] Michael F. Spear, Virendra J. Marathe, Luke Dalessandro, and Michael L. Scott. 2007. Privatization techniques for software transactional memory. In ACM Symposium on Principles of Distributed Computing (PODC).

SPAA ’26, July 06–10, 2026, London, United Kingdom

[54] Bjarne Stroustrup. 1994. The Design and Evolution of C++. Addison-Wesley Professional, Reading, Massachusetts. [55] Michael J. Sullivan. 2017. Low-level Concurrent Programming Using the Relaxed Memory Calculus. Ph. D. Dissertation. Carnegie Mellon University. CMU-CS-17126. [56] Yuanhao Wei, Guy E. Blelloch, Panagiota Fatourou, and Eric Ruppert. 2023. Practically and Theoretically Efficient Garbage Collection for Multiversioning. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP). [57] Yingjun Wu, Joy Arulraj, Jiexi Lin, Ran Xian, and Andrew Pavlo. 2017. An Empirical Evaluation of In-Memory Multi-Version Concurrency Control. Proceedings of the VLDB Endowment (PVLDB) 10 (2017). Issue 7. [58] Xiangyao Yu, Andrew Pavlo, Daniel Sanchez, and Srinivas Devadas. 2016. TicToc: Time Traveling Optimistic Concurrency Control. In ACM SIGMOD International Conference on Management of Data (SIGMOD).

Appendices A

Privatization Safety

An issue not commonly addressed by other STM systems is the interoperability of transactional and non-transactional code. In particular, user programs might require that variables previously accessed inside a transaction be used outside of the STM context (privatization) or vice versa (publication). The question is how can an STM provide privatization (and publication) safety. Figure 13 illustrates what can go wrong if an STM system does not ensure privatization safety. The is_private variable represents whether x can be accessed transactionally (false), or nontransactionally (true). Thread 1 executes a transaction that sets is_private (lines 4-6), supposedly enabling a safe raw access to x (line 7). The issue is that, without correct privatization, the assertion on line 8 can fail. The pattern, known as delayed commit, happens because Thread 2 buffered its write to x (very common amongst STMs) and later overwrote Thread 1’s write (line 8). Thread 1 //is_private == false

1 2 3

transaction([&] { is_private.store(true); }); x = 7;

4 5 6 7 8

assert(x == 7); //Fails

Thread 2 transaction([&] { if (!is_private.load()) x.store(5); //buffered //Validate

9

//Write to x and Commit });

Figure 13: Unsafe interleaving mixing transactional and nontransactional data accesses. The question is how do we know when it is safe for nontransactional accesses to occur. One possibility would be to only access variables that may be accessed transactionally through stm::load and stm::store operations, be it inside or outside transactions. This can be done explicitly or automatically through compiler instrumentation. The downside to this approach is the loss of performance accompanied by requiring STM routines to run on all accesses to data that may be used transactionally. Another option is to provide an additional fence instruction that allows for privatization (and another for publication), as described in [28]. By requiring that users explicitly fence on privatization, we allow raw accesses to data previously accessed transactionally. In the example

Zachary Kent, Guy E. Blelloch, and André Costa

1 2

template <typename T> inline void fence(T& d) { transaction([=] {d.store(d.load());}); } Figure 14: fence(x) implementation. depicted in Figure 13, a fence performed by Thread 1 after line 6 would suffice. Note that most STMs do not address privatization safety, which forces applications to either only access data inside of transactions or write their own quiescence mechanism to wait for all active transactions to finish. The fence instruction resembles a fence in the C/C++ memory model. This is because the raw access in Thread 1 can be seen as analogous to a relaxed access that is not synchronized with Thread 2. Hence, a fence before the write to x on line 7 can be thought of as preventing reordering of the following raw accesses. Data-race free semantics are required for correct usage of a fencing solution (see [28] for more detail). To implement the described fence instruction, we would require a barrier that waits for all currently running transactions to finish, similar to RCU patterns. The issue then becomes that such an instruction may be too coarse-grained for some use cases. For example, in Figure 13, one can imagine that if other threads were running and operating on a disjoint set of data, Thread 1 would not need to wait for those threads to finish. Thus, we propose a fence(x) instruction that only fences on a given object x. The fence(x) instruction can be implemented much more efficiently, as can be seen in Figure 14. By performing a no-side-effects write on x, we ensure that after successfully fencing, currently running transactions will either: have finished performing their write-back phase; or will have aborted, in which case they must be ordered after the fence (e.g., in our example Thread 2 must read false when it reads is_private).

µSTM: A Lightweight and Efficient STM

B

µSTM Code

SPAA ’26, July 06–10, 2026, London, United Kingdom

79 80

1 2 3 4 5 6 7 8 9 10 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 32 33 34 35 36 38 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 56 57 58 59 60 61 62 64 65 66 67 68 69 70 72 73 74 75 76 77 78

// Supports transactions with the following interface: // r = ustm::transaction(func) // runs a func in transaction // r = ustm::transaction(func, true) // read only mode // r = ustm::load(x) // loads value from x // ustm::store(x, v) // stores v into x // r = ustm::New<T>(args ...) // new object of type T // ustm::Delete(x) // deletes x // ustm::fence(x) // for privatization // ustm::fence() // for privatization // The types for load and store can be any relocatable type. #ifndef USTM_H_ #define USTM_H_ #include <array> #include <atomic> #include <bitset> #include <cmath> #include <functional> #include <iostream> #include <thread> #include <tuple> #include <unordered_map> #include <vector> // Uses epoch-based SMR from uepoch.h. Needed interface: // r = uepoch::protect(func) : runs func under protection // uepoch::delay(func) : delays until protected are done // uepoch::add_before_epoch_hook(func) // uepoch::thread_id() // uepoch::quiesce() : waits for all protected regions #include "uepoch.h" namespace ustm { // some constants constexpr int MaxThreads = 4096; // can be increased constexpr int logLocks = 22; // log_2 of number of locks static constexpr int filterBits = 10; // for hash filter

81 82 83 84 85 86 87 88 90 91 93 94 95 96 97 99 100 101 102 103 104 105 106 107 108 109 110 111 113 114 115

std::atomic<version*> verlist = nullptr; // version list version* getVersionList() const { return verlist.load();} // add to version list void addLink(version* l, TS prevStamp) { l->next = verlist.load(); l->stamp = prevStamp; verlist.store(l, std::memory_order_release); } // Returns whether succeeded or not, and if succeeded a // 0 stamp. If was self locked, and the swapped out // timestamp otherwise std::pair<bool,TS> tryLock(int tid, const TS startStamp) { Status s = getStatus(); if (isLocked(s)) if (getTID(s) == tid) return std::pair(true, 0); else return std::pair(false, 0); if (s < startStamp && v.compare_exchange_strong(s, setLock(tid))) { return std::pair(true, getStamp(s)); } else return std::pair(false, 0); } // unlocks by setting status to timestamp void unlock(const TS ts) { v.store(ts, std::memory_order_release); }

124

// checks that either self locked or timestamp before // startStamp bool validateRead(const TS startStamp, int tid) const { Status s = getStatus(); return ((isLocked(s) && getTID(s) == tid) || s < startStamp); } };

126

struct STMState;

117

using TS = size_t; // type for timestamps

118

struct timeStamp { std::atomic<TS> ts = 1ul; // returns current stamp TS getStamp() const { return ts.load(); } // returns incremented stamp TS nextStamp(TS prevStamp=0) { if (prevStamp == 0) prevStamp = getStamp(); TS stamp = ts.load(); if (stamp >prevStamp) return stamp; for (volatile int i = 0; i <200; i++); stamp = ts.load(); if (stamp >prevStamp) return stamp; return ++ts; } };

120

// generic version link struct version { version* next = nullptr; TS stamp = 0; void* addr; version(void* addr) : addr(addr) {} };

136

// link including a type specific value template <typename T> struct link : version { T value; T scratch; link(T* addr, T value) : version{addr}, value(value) {} };

144

// The lock structure. Contains the status of the lock // and if using versioning a version list. struct alignas(16) lock { using Status = size_t; // If locked (high bit set) keeps tid of owner, // otherwise keeps timestamp std::atomic<Status> v = 1; // time starts at 1

lock() {} static int getTID(Status s) { return ~(1ul <<63) & s;} static TS getStamp(Status s) { return s;} static bool isLocked(Status s) { return (s >>63) & 1ul;} static Status setLock(int tid) { return Status((1ul <<63) | tid);} Status getStatus() const { return v.load(std::memory_order_acquire);} void setStamp(TS stamp) { v.store(stamp, std::memory_order_release); }

119 121 122 123

128 129 130 131 132 133 134 135 137 138 140 141 142 143 145 146 147 148 149 150 151 153 154 155 156 158 159

// Transaction descriptor, includes the logs, stats, and // other state struct alignas(128) Descriptor { bool inTransaction {false}; bool readOnly {false}; bool lateRead {false}; int inConstructor {0}; size_t tid; // thread identifier size_t numRetries {0}; TS startStamp; STMState* stmState; // Entry for the write log. Contains the location, an // oldStamp used when locked, a pointer to the link // containing the value, a pointer to the data within // the link and the size in bytes of the value. struct logEntry { void* loc; TS oldStamp; version* link; void* data; void* scratch; int size; }; // The following four members are the logs. std::vector<logEntry> writeLog; // The read log contains pointers to read locations. std::vector<const void*> readLog; // Alloc and delete logs keep pointers to functions that // do deletes

SPAA ’26, July 06–10, 2026, London, United Kingdom

160 161 163 164 165 167 168 169 170 171 172 173 174 175 177 178 179 180 181 182 184 185 186 187 188 189 191 192 193 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239

std::vector<std::function<void()>> allocLog; std::vector<std::function<void()>> deleteLog;

Zachary Kent, Guy E. Blelloch, and André Costa

241

// A hash map and filter to let reads find prior writes std::unordered_map<void*, int> writeMap; std::bitset<filterBits> writeFilter;

242

// used to reset between each attempt void reset() { if (writeLog.size() >0) { writeFilter = 0; writeLog.clear(); writeMap.clear(); } readLog.clear(); deleteLog.clear(); allocLog.clear(); inConstructor = false; lateRead = false; } };

246

template <int bits> size_t hash(const void* addr) { size_t x = ((reinterpret_cast<size_t>(addr)>>6) * UINT64_C(0xbf58476d1ce4e5b9)); return x >>(64 - bits); } struct STMState { // state consists of locks, descriptors, and timestamp static constexpr size_t numLocks = 1ul <<logLocks; std::array<Descriptor,MaxThreads> descriptors; std::array<lock,numLocks> writeLocks; timeStamp ts;

244 245 247 248 249 250 251 252 253 254 255 257 258 259 260 261 262 263 264 265 266 268 269

// Returns a lock corresponding to a hash of the address inline lock& getLock(const void* addr) { return writeLocks[hash<logLocks>(addr)];}

270

// returns true if successful inline bool commitTransaction(Descriptor* myd) { TS endStamp; bool hasWrite = myd->writeLog.size() >0; if (hasWrite) { if (myd->lateRead) return false; // Take locks (abort if any fail) for (auto& e : myd->writeLog) { auto [r,s] = getLock(e.loc).tryLock(myd->tid, myd->startStamp); if (!r) return false; e.oldStamp = s; } // get stamp -- this is the serialization point endStamp = ts.getStamp(); // Validate the reads (abort if any fail) for (auto& e : myd->readLog) if (!getLock(e).validateRead(myd->startStamp, myd->tid)) return false; // If here (i.e. locks and validates succeeded), // transaction succeeded. Apply the writes and then // unlock them. for (auto& e : myd->writeLog) {

274

auto *tmp = e.scratch; // swap destination and data (from the link) std::memcpy(tmp, e.loc, e.size); std::memcpy(e.loc, e.data, e.size); std::memcpy(e.data, tmp, e.size); // add link to version list TS writeStamp = ((e.oldStamp == 0) ? endStamp : e.oldStamp); getLock(e.loc).addLink(e.link, writeStamp);

} std::atomic_thread_fence(std::memory_order_release); for (auto& e : myd->writeLog) // unlock writes if (e.oldStamp != 0) getLock(e.loc).unlock(endStamp);

} // Since successful, apply the deletes. for (auto& e : myd->deleteLog) uepoch::delay(std::move(e)); myd->reset(); if (hasWrite) ts.nextStamp(endStamp);

myd->inTransaction = false; return true;

240

271 273 275 276 277 279 280 281 282 283 285 286 287 288 289 290 291 292 293 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319

} inline void abortTransaction(Descriptor* myd) { // Release locks and apply deletes to allocated objects. for (auto& e : myd->writeLog) if (e.oldStamp != 0) getLock(e.loc).unlock(e.oldStamp); for (auto& e : myd->allocLog) uepoch::delay(std::move(e)); if (++myd->numRetries % 4000000 == 0) { std::cout <<"ustm: too many retries: " << std::endl; abort();} myd->reset(); ts.nextStamp(myd->startStamp); } STMState() { for (int i=0; i <MaxThreads; i++) { descriptors[i].tid = i; descriptors[i].stmState = this; } // ensures stamp is incremented whenever epoch is uepoch::add_before_epoch_hook([&] { ts.nextStamp(); }); } ~STMState() {} }; extern inline Descriptor* initDescriptor() { static STMState stm; return &stm.descriptors[uepoch::thread_id()]; } // thread local copy of descriptor. extern inline Descriptor* getDescriptor() { static thread_local Descriptor* d = initDescriptor(); return d; } template <typename T> inline T load(T& v, bool unprotected=false) { Descriptor* myd = getDescriptor(); lock& lck = myd->stmState->getLock(&v); auto status = lck.getStatus(); // check if value is in the write buffer if (myd->writeLog.size() >0 && myd->writeFilter[hash<filterBits>(&v)]) { auto a = myd->writeMap.find((void*) &v); if (a != myd->writeMap.end()) { version* ptr = (myd->writeLog[(*a).second]).link; return (reinterpret_cast<link<T>*>(ptr))->value; } } version* nxt; bool regular = (myd->inTransaction && !myd->readOnly && !unprotected); if (regular) myd->readLog.push_back(&v); char tmp[sizeof(T)]; T* location = reinterpret_cast<T*>(tmp); while (true) { auto prevStatus = status; std::memcpy(tmp, &v, sizeof(T)); nxt = lck.getVersionList(); std::atomic_thread_fence(std::memory_order_acquire); status = lck.getStatus(); if (prevStatus == status) { if (status <myd->startStamp) return *location; if (!lock::isLocked(status)) { if (!myd->inTransaction) return *location; break; } } } if (regular) myd->lateRead = true; TS stamp = lck.getStamp(status); // Chase down the version list to the right one while (stamp >= myd->startStamp && nxt != nullptr) { if (nxt->addr == &v)

µSTM: A Lightweight and Efficient STM

location = &(reinterpret_cast<link<T>*>(nxt)->value); stamp = nxt->stamp; nxt = nxt->next;

320 321 322 323 324 325 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 349 350 351 352 353 354 355 356 357 358 359 360 361 363 364 365 366 367 368 369 370 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 396 397 398

}

} return *location;

// runs func in an transaction // func takes no argument and must return a value template<typename F> inline auto transaction(F&& func, bool readOnly = false) { Descriptor* myd = getDescriptor(); STMState* stm = myd->stmState; // if nested then just run if (myd->inTransaction) return func(); myd->inTransaction = true; myd->numRetries = 0; myd->readOnly = readOnly; while (true) { auto returnValue = uepoch::protect([&] { myd->startStamp = stm->ts.getStamp(); return func(); }); if (stm->commitTransaction(myd)) return returnValue; else stm->abortTransaction(myd); } } // adds to log so can delete if aborted template <typename T, typename... Args> inline T* New(Args&&... args) { Descriptor* myd = getDescriptor(); if (myd->inTransaction) { myd->inConstructor++; T* ptr = new T(args...); myd->allocLog.push_back([=] {delete ptr;}); myd->inConstructor--; return ptr; } else return new T(args...); } // adds to log and only applies deletes on success template<typename T> inline void Delete(T* obj) { if (obj == nullptr) return; Descriptor* myd = getDescriptor(); if (!myd->inTransaction) delete obj; else myd->deleteLog.push_back([=] { delete obj;}); } template <typename T> inline void store(T& loc, const T& v) { Descriptor* myd = getDescriptor(); if (myd->inConstructor >0) loc = v; else if (!myd->inTransaction) transaction([&] {ustm::store(loc, v); return true;}); else { // insert into hash filter and map so reads can find it myd->writeFilter[hash<filterBits>(&loc)] = 1; myd->writeMap[&loc] = myd->writeLog.size(); // temporarily store value in new link auto* hp = ustm::New<link<T>>(&loc, v); ustm::Delete(hp); // delete is delayed myd->writeLog.push_back({ .loc = &loc, .oldStamp = 0, .link = hp, .data = &hp->value, .scratch = &hp->scratch, .size = sizeof(T) }); } } template <typename T> inline void fence(T& loc) { ustm::transaction([=] {

SPAA ’26, July 06–10, 2026, London, United Kingdom

399

ustm::store(loc, ustm::load(loc));}); }

402

inline void fence() { uepoch::quiesce();} } // End namespace ustm

404

#endif // USTM_H_

401