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__ $$bAssoc Computing Machinery$$c2012$$aNew York
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$$g191413$$aProkopec, Aleksandar
000184476 700__ $$aBronson, Nathan G.
000184476 700__ $$aBagwell, Phil
000184476 700__ $$aOdersky, Martin$$g126003$$0241835
000184476 773__ $$j47$$tAcm Sigplan Notices$$k8$$q151-160
000184476 909C0 $$xU10409$$0252187$$pLAMP
000184476 909CO $$pIC$$particle$$ooai:infoscience.tind.io:184476
000184476 917Z8 $$x166927
000184476 937__ $$aEPFL-ARTICLE-184476
000184476 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000184476 980__ $$aARTICLE