Skip Hash: A Fast Ordered Map Via Software Transactional Memory
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916431517450240 |
|---|---|
| author | Rodriguez, Matthew Aksenov, Vitaly Spear, Michael |
| author_facet | Rodriguez, Matthew Aksenov, Vitaly Spear, Michael |
| contents | 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, a new ordered map designed around that assumption. It combines a skip list and a hash map behind a single abstraction, resulting in $O(1)$ overheads 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_07466 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Skip Hash: A Fast Ordered Map Via Software Transactional Memory Rodriguez, Matthew Aksenov, Vitaly Spear, Michael Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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, a new ordered map designed around that assumption. It combines a skip list and a hash map behind a single abstraction, resulting in $O(1)$ overheads 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. |
| title | Skip Hash: A Fast Ordered Map Via Software Transactional Memory |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.07466 |