Name
Abstract | ||
|---|---|---|
We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure space-efficiency, removal operations compress the trie when necessary. We show how to implement an efficient lock-free snapshot operation for concurrent hash tries. The snapshot operation uses a single-word compare-and-swap and avoids copying the data structure eagerly. Snapshots are used to implement consistent iterators and a linearizable size retrieval. We compare concurrent hash trie performance with other concurrent data structures and evaluate the performance of the snapshot operation. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2145816.2145836 | PPOPP |
Keywords | Field | DocType |
standard mutable lock-free operation,concurrent try,hash trie,concurrent hash,concurrent data structure,efficient lock-free snapshot operation,non-blocking concurrent hash trie,concurrent hash trie performance,snapshot operation,removal operation,efficient non-blocking snapshot,data structure,snapshot,algorithms,shared memory,concurrent data structures,compare and swap | Hash array mapped trie,Hash tree,Double hashing,Extendible hashing,Computer science,Parallel computing,HAT-trie,Theoretical computer science,Hash function,Concurrent data structure,Hash trie,Distributed computing | Conference |
Volume | Issue | ISSN |
47 | 8 | 0362-1340 |
Citations | PageRank | References |
49 | 1.85 | 12 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandar Prokopec | 1 | 163 | 13.56 |
| Nathan Grasso Bronson | 2 | 49 | 1.85 |
| Phil Bagwell | 3 | 81 | 4.64 |
| Martin Odersky | 4 | 2261 | 170.39 |