This work challenges the perceived tradeoff between strict semantics and scalable performance in priority schedulers. We break down and analyze the use of relaxation in existing priority queue designs, aiming to show that by tailoring the design to workload characteristics, priority queues can retain strong semantics while achieving competitive scalability. In fact, many widely used applications of priority queues exhibit workloads with common characteristics: the number of distinct priorities is few relative to the number of jobs, and insertions tend to be low-priority. We use these observations to design QPID, a strict, concurrent priority queue. Our experimental results show that QPID scales nearly as well as the best relaxed competitor and outperforms all other strict and relaxed competitors in most cases.

Scalable ordered maps must ensure that range queries, which operate over many consecutive keys, provide intuitive semantics (e.g., linearizability) without degrading the performance of concurrent insertions and removals. These goals are difficult to achieve simultaneously when concurrent data structures are built using only locks and compare-and-swap objects. However, recent innovations in software transactional memory (STM) allow programmers to assume that multi-word atomic operations can be fast and simple.This paper introduces the skip hash, which uses STM to combine a skip list and a hash map behind a single ordered map abstraction, resulting in O(1) overhead for most operations. The skip hash makes use of a novel range query manager—again leveraging STM—to achieve fast, linearizable range queries that do not inhibit scalability. In performance evaluation, we show that the skip hash outperforms the state of the art in almost all cases. This places the skip hash in the uncommon position of being both exceedingly fast and exceedingly simple, which demonstrates that designing novel STM-based data structures is a promising direction for future research.

We present the skip vector, a novel highperformance concurrent data structure based on the skip list. The key innovation in the skip vector is to flatten the index and data layers of the skip list into vectors. This increases spatial locality, reduces synchronization overhead, and avoids much of the costly pointer chasing that skip lists incur. We evaluate a skip vector implementation in C++. Our implementation coordinates interactions among threads by utilizing optimistic traversal with sequence locks. To ensure memory safety, it employs hazard pointers; this leads to tight bounds on wasted space, but due to the skip vector design, does not lead to high overhead. Performance of the skip vector for small data set sizes is higher than for a comparable skip list, and as the amount of data increases, the benefits of the skip vector over a skip list increase.

This paper presents the skip vector, a novel high-performance concurrent data structure based on the skip list. Traversal is sped up by flattening the layers of the skip list into vectors, avoiding much of the costly pointer chasing that skip lists incur. The skip vector utilizes optimistic traversal with sequence locks, and hazard pointers for fast, memory-safe, concurrent access. In microbenchmark evaluation, we show that the skip vector offers excellent performance across a range of key ranges, thread counts, and operation mixes.

We study the problem of ensuring the correctness of concurrent programs that perform mutating foreach and range operations over concurrent data structures. We introduce three algorithms which vary in the location and the granularity of concurrency control metadata. Our algorithms make the linearization of bulk operations visible to concurrent elemental operations, which enables them to scale well, keep overhead low, and operate within tight memory bounds. In our experimental evaluation, we demonstrate that our techniques do not hinder the performance of elemental operations in elemental-only workloads, and allow scalability among concurrent mutating bulk operations. Furthermore, in mixed workloads, our algorithms outperform the baseline, sometimes by an order of magnitude or more.

High-performance software transactional memory (STM) implementations rely on nuanced use of synchronization variables to coordinate speculative accesses to program data. We discuss some consequences of the C++ memory model on STM, identify an easy-to-fix implementation error, and describe an unavoidable formal race condition that occurs in an important class of STM algorithms.