Shared Memory Synchronization (2nd edition)

This second edition, published roughly a decade after the original, has numerous small improvements throughout-clarifications, bug fixes, and references to newer work. It also incorporates two major updates. First, we have re-worked and clarified the memory model and notation (Secs. 2.2 and 2.3)...

Simple, Fast and Widely Applicable Concurrent Memory Reclamation via Neutralization

Reclaiming memory in non-blocking dynamic data structures in unmanaged languages like C/C++ presents a unique challenge due to the risk of use-after-free errors caused by concurrent accesses. Existing safe memory reclamation (SMR) algorithms fall short of satisfying five key properties: high...

PHyTM: persistent hybrid transactional memory

Processors with hardware support for transactional memory (HTM) are rapidly becoming commonplace, and processor manufacturers are currently working on implementing support for upcoming non-volatile memory (NVM) technologies. The combination of HTM and NVM promises to be a natural choice for...

Practical Hardware Transactional vEB Trees

van Emde Boas (vEB) trees are sequential data structures optimized for extremely fast predecessor and successor queries. Such queries are an important incentive to use ordered sets or maps such as vEB trees. All operations in a vEB tree are doubly logarithmic in the universe size. Attempts to...

Are Your Epochs Too Epic? Batch Free Can Be Harmful

Epoch based memory reclamation (EBR) is one of the most popular techniques for reclaiming memory in lock-free and optimistic locking data structures, due to its ease of use and good performance in practice. However, EBR is known to be sensitive to thread delays, which can result in performance...

The fence complexity of persistent sets

We study the psync complexity of concurrent sets in the non-volatile shared memory model. Flush instructions are used in non-volatile memory to force shared state to be written back to non-volatile memory and must typically be accompanied by the use of expensive fence instructions to enforce...

Efficient hardware primitives for immediate memory reclamation in optimistic data structures

Safe memory reclamation (SMR) algorithms are crucial for preventing use-after-free errors in optimistic data structures. SMR algorithms typically delay reclamation for safety and reclaim objects in batches for efficiency. It is difficult to strike a balance between performance and space efficiency....

Performance anomalies in concurrent data structure microbenchmarks

Recent decades have witnessed a surge in the development of concurrent data structures with an increasing interest in data structures implementing concurrent sets (CSets). Microbenchmarking tools are frequently utilized to evaluate and compare the performance differences across concurrent data...

PREP-UC: A practical replicated persistent universal construction

The process of designing and implementing correct concurrent data structures is non-trivial and often error prone. The recent commercial availability of non-volatile memory has prompted many researchers to also consider designing concurrent data structures that persist shared state allowing the data...

PathCAS: An efficient middle ground for concurrent search data structures

To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as...

Elimination (a,b)-trees with fast, durable updates

Many concurrent dictionary implementations are designed and optimized for read-mostly workloads with uniformly distributed keys, and often perform poorly on update-heavy workloads. In this work, we first present a concurrent (a,b)-tree, the OCC-ABtree, which outperforms its fastest competitor by up...

NBR: Neutralization based reclamation

Safe memory reclamation (SMR) algorithms suffer from a trade-off between bounding unreclaimed memory and the speed of reclamation. Hazard pointer (HP) based algorithms bound unreclaimed memory at all times, but tend to be slower than other approaches. Epoch based reclamation (EBR) algorithms are...

Memory Tagging: Minimalist Synchronization for Scalable Concurrent Data Structures

There has been a significant amount of research on hardware and software support for efficient concurrent data structures; yet, the question of how to build correct, simple, and scalable data structures has not yet been definitively settled. In this paper, we revisit this question from a minimalist...

Non-blocking interpolation search trees with doubly-logarithmic running time

Balanced search trees typically use key comparisons to guide their operations, and achieve logarithmic running time. By relying on numerical properties of the keys, interpolation search achieves lower search complexity and better performance. Although interpolation-based data structures were...

Snapshot-based synchronization: a fast replacement for hand-over-hand locking

Concurrent accesses to shared data structures must be synchronized to avoid data races. Coarse-grained synchronization, which locks the entire data structure, is easy to implement but does not scale. Fine-grained synchronization can scale well, but can be hard to reason about. Hand-over-hand...

Relaxed schedulers efficiently parallelize sequential algorithms

There has been significant progress in understanding the parallelism inherent to iterative sequential algorithms: for many classic algorithms, the depth of the dependence structure is now well understood, and scheduling techniques have been developed to exploit this shallow dependence structure for...

Distributionally linearizable data structures

Relaxed concurrent data structures have become increasingly popular, due to their scalability in graph processing and machine learning applications (\citeNguyen13, gonzalez2012powergraph ). Despite considerable interest, there exist families of natural, high performing randomized relaxed concurrent...

Getting to the root of concurrent search tree performance

Many systems rely on optimistic concurrent search trees for multi-core scalability. In principle, optimistic trees have a simple performance story: searches are read-only and so run in parallel, with writes to shared memory occurring only when modifying the data structure. However, this paper shows...

Harnessing epoch-based reclamation for efficient range queries

Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous...

Reuse, don't recycle: transforming lock-free algorithms that throw away descriptors

In many lock-free algorithms, threads help one another, and each operation creates a descriptor that describes how other threads should help it. Allocating and reclaiming descriptors introduces significant space and time overhead. We introduce the first descriptor abstract data type (ADT), which...

Cost of concurrency in hybrid transactional memory

State-of-the-art \emph{software transactional memory (STM)} implementations achieve good performance by carefully avoiding the overhead of \emph{incremental validation} (i.e., re-reading previously read data items to avoid inconsistency) while still providing \emph{progressiveness} (allowing...

A template for implementing fast lock-free trees using HTM

Algorithms that use hardware transactional memory (HTM) must provide a software-only fallback path to guarantee progress. The design of the fallback path can have a profound impact on performance. If the fallback path is allowed to run concurrently with hardware transactions, then hardware...

Investigating the performance of hardware transactions on a multi-socket machine

The introduction of hardware transactional memory (HTM) into commercial processors opens a door for designing and implementing scalable synchronization mechanisms. One example for such a mechanism is transactional lock elision (TLE), where lock-based critical sections are executed concurrently using...

Reclaiming memory for lock-free data structures: there has to be a better way

Memory reclamation for sequential or lock-based data structures is typically easy. However, memory reclamation for lock-free data structures is a significant challenge. Automatic techniques such as garbage collection are inefficient or use locks, and non-automatic techniques either have high...

B-slack trees: space efficient B-trees

B-slack trees, a subclass of B-trees that have substantially better worst-case space complexity, are introduced. They store n keys in height O(logbn), where b is the maximum node degree. Updates can be performed in O(logb2n) amortized time. A relaxed balance version, which is well suited for...

A general technique for non-blocking trees

We describe a general technique for obtaining provably correct, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the tree atomically. Our non-blocking algorithms make...

Pragmatic primitives for non-blocking data structures

We define a new set of primitive operations that greatly simplify the implementation of non-blocking data structures in asynchronous shared-memory systems. The new operations operate on a set of Data-records, each of which contains multiple fields. The operations are generalizations of the...

Range queries in non-blocking k-ary search trees

We present a linearizable, non-blocking k-ary search tree (k-ST) that supports fast searches and range queries. Our algorithm uses single-word compare-and-swap (CAS) operations, and tolerates any number of crash failures. Performance experiments show that, for workloads containing small range...

Non-blocking k-ary search trees

This paper presents the first concurrent non-blocking k-ary search tree. Our data structure generalizes the recent non-blocking binary search tree of Ellen et al. [5] to trees in which each internal node has k children. Larger values of k decrease the depth of the tree, but lead to higher contention...

Cost of concurrency in hybrid transactional memory

Persistent hybrid transactional memory

Investigating the performance of hardware transactions on a multi-socket machine

Unexpected scaling in path copying trees

Brief Announcement: Performance anomalies in concurrent data structure microbenchmarks

Recent decades have witnessed a surge in the development of concurrent data structures with an increasing interest in data structures implementing concurrent sets (CSets). Microbenchmarking tools are frequently utilized to evaluate and compare performance differences across concurrent data...

Reuse, don't recycle: transforming lock-free algorithms that throw away descriptors

Concurrent data structures

Faster data structures in transactional memory using three paths

A general technique for non-blocking trees

Are Your Epochs Too Epic? Batch Free Can Be Harmful

Epoch based memory reclamation (EBR) is one of the most popular techniques for reclaiming memory in lock-free and optimistic locking data structures, due to its ease of use and good performance in practice. However, EBR is known to be sensitive to thread delays, which can result in performance...

PathCAS: An efficient middle ground for concurrent search data structures

To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient and elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as...

Performance anomalies in concurrent data structure microbenchmarks

Recent decades have witnessed a surge in the development of concurrent data structures with an increasing interest in data structures implementing concurrent sets (CSets). Microbenchmarking tools are frequently utilized to evaluate and compare the performance differences across concurrent data...

Elimination (a,b)-trees with fast, durable updates

Many concurrent dictionary implementations are designed and optimized for read-mostly workloads with uniformly distributed keys, and often perform poorly on update-heavy workloads. In this work, we first present a concurrent (a,b)-tree, the OCC-ABtree, which outperforms its fastest competitor by up...

NBR: Neutralization based reclamation

Safe memory reclamation (SMR) algorithms suffer from a trade-off between bounding unreclaimed memory and the speed of reclamation. Hazard pointer (HP) based algorithms bound unreclaimed memory at all times, but tend to be slower than other approaches. Epoch based reclamation (EBR) algorithms are...

Analysis and Evaluation of Non-Blocking Interpolation Search Trees

We start by summarizing the recently proposed implementation of the first non-blocking concurrent interpolation search tree (C-IST) data structure. We then analyze the individual operations of the C-IST, and show that they are correct and linearizable. We furthermore show that lookup (and several...

Relaxed schedulers efficiently parallelize sequential algorithms

Distributionally linearizable data structures

A general technique for non-blocking trees

Pragmatic primitives for non-blocking data structures

Range queries in non-blocking k-ary search trees

B-slack trees: space efficient B-trees

Reclaiming memory for lock-free data structures: there has to be a better way

A template for implementing fast lock-free trees using HTM

Reuse, don't recycle: transforming lock-free algorithms that throw away descriptors

Non-blocking k-ary search trees

Adaptive techniques for improving performance of hardware transactions on multi-socket machines

Socket scheduling modes may prevent non-uniform memory access effects from negatively affecting performance of synchronization mechanisms utilizing hardware transactional memory. Each mode may indicate whether a thread may execute a critical section on a particular socket. For example, under...