City Research Online

Skip Hash: A Fast Ordered Map Via Software Transactional Memory

Rodriguez, M., Aksenov, V. ORCID: 0000-0001-9134-5490 & Spear, M. (2025). Skip Hash: A Fast Ordered Map Via Software Transactional Memory. Paper presented at the IEEE ICDCS 2025 45th IEEE International Conference on Distributed Computing Systems, 20-23 Jul 2025, Glasgow, London.

Abstract

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.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © 2025 IEEE.
Publisher Keywords: Synchronization, Concurrent Data Structures, Range Queries, Software Transactional Memory
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology
School of Science & Technology > Department of Computer Science
SWORD Depositor:
[thumbnail of ICDCS_2025_paper_508.pdf]
Preview
Text - Accepted Version
Available under License Creative Commons Attribution.

Download (369kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login