000184476 001__ 184476
000184476 005__ 20181203023018.0
000184476 0247_ $$2doi$$a10.1145/2370036.2145836
000184476 022__ $$a0362-1340
000184476 02470 $$2ISI$$a000309350200015
000184476 037__ $$aARTICLE
000184476 245__ $$aConcurrent Tries with Efficient Non-Blocking Snapshots
000184476 260__ $$aNew York$$bAssoc Computing Machinery$$c2012
000184476 269__ $$a2012
000184476 300__ $$a10
000184476 336__ $$aJournal Articles
000184476 520__ $$aWe 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.
000184476 6531_ $$aAlgorithms
000184476 6531_ $$ahash trie
000184476 6531_ $$aconcurrent data structure
000184476 6531_ $$asnapshot
000184476 6531_ $$anon-blocking
000184476 700__ $$0244134$$aProkopec, Aleksandar$$g191413
000184476 700__ $$aBronson, Nathan G.
000184476 700__ $$aBagwell, Phil
000184476 700__ $$0241835$$aOdersky, Martin$$g126003
000184476 773__ $$j47$$k8$$q151-160$$tAcm Sigplan Notices
000184476 909C0 $$0252187$$pLAMP$$xU10409
000184476 909CO $$ooai:infoscience.tind.io:184476$$pIC$$particle
000184476 917Z8 $$x166927
000184476 937__ $$aEPFL-ARTICLE-184476
000184476 973__ $$aEPFL$$rREVIEWED$$sPUBLISHED
000184476 980__ $$aARTICLE