Concurrent Tries with Efficient Non-Blocking Snapshots

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.


Published in:
Acm Sigplan Notices, 47, 8, 151-160
Year:
2012
Publisher:
New York, Assoc Computing Machinery
ISSN:
0362-1340
Keywords:
Laboratories:




 Record created 2013-02-27, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)