000166908 001__ 166908
000166908 005__ 20190316235144.0
000166908 037__ $$aREP_WORK
000166908 245__ $$aCache-Aware Lock-Free Concurrent Hash Tries
000166908 269__ $$a2011
000166908 260__ $$c2011
000166908 300__ $$a14
000166908 336__ $$aReports
000166908 520__ $$aThis report describes an implementation of a non-blocking concurrent shared-memory hash trie based on single-word compare-and-swap instructions. Insert, lookup and remove operations modifying different parts of the hash trie can be run independent of each other and do not contend. Remove operations ensure that the unneeded memory is freed and that the trie is kept compact. A pseudocode for these operations is presented and a proof of correctness is given -- we show that the implementation is linearizable and lock-free. Finally, benchmarks are presented which compare concurrent hash trie operations against the corresponding operations on other concurrent data structures, showing their performance and scalability.
000166908 6531_ $$aconcurrent tries
000166908 6531_ $$alock-free data structures
000166908 6531_ $$ahash tries
000166908 700__ $$0244134$$g191413$$aProkopec, Aleksandar
000166908 700__ $$aBagwell, Phil
000166908 700__ $$0241835$$g126003$$aOdersky, Martin
000166908 8564_ $$uhttps://infoscience.epfl.ch/record/166908/files/ctries-techreport.pdf$$zn/a$$s368025$$yPreprint
000166908 909C0 $$xU10409$$0252187$$pLAMP
000166908 909CO $$qGLOBAL_SET$$pIC$$ooai:infoscience.tind.io:166908$$preport
000166908 917Z8 $$x191413
000166908 917Z8 $$x191413
000166908 917Z8 $$x191413
000166908 937__ $$aEPFL-REPORT-166908
000166908 973__ $$sPUBLISHED$$aEPFL
000166908 980__ $$aREPORT