arXiv preprint ·
A Simple Optimistic B-Skiplist Algorithm
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC). OLC replaces the multi-cache-line RW lock with a compact, single-cache-line lock: readers validate a version number without writing to shared memory, avoiding cache invalidations and retrying only on a detected conflict. Although OLC was thought poorly suited to skiplists, where a single per-element lock may span structurally unrelated levels, the B-skiplist's blocked layout places each level (and associated lock) in its own node. We exploit the B-skiplist's upfront knowledge of promotion height with a hybrid top-down scheme that traverses upper levels optimistically and locks only from the promotion level down, so most inserts never dirty a cache line. On 128 threads, the proposed optimistic B-skiplist achieves $1.2-10\times$ higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves $0.8-4.3\times$ the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to $13\times$ lower latency than concurrent skiplists and tree-based indices, and is within $1.6\times$ of the latency of the OLC-based B+-tree.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
An Unconditional Space-Approximation Lower Bound for Semi-Streaming Matching
Output-Sensitive Enumeration of Maximal Closed Substrings in Linear Space
Uniformity Testing for the Monomer-Dimer Model
On Worst-Case Guarantees for Graph-Based Nearest-Neighbor Search
Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.