Aleksandar Prokopec
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.
- O. Agesen, D. L. Detlefs, C. H. Flood, A. Garthwaite, P. A. Martin , N. Shavit , G. L. Steele Jr.: DCAS-Based Concurrent Deques. SPAA, 2000. Google Scholar
Digital Library
- P. Bagwell: Ideal Hash Trees. EPFL Technical Report, 2001.Google Scholar
- R. Brandais: File searching using variable length keys. Proceedings of Western Joint Computer Conference, 1959. Google ScholarDigital Library
- N. G. Bronson, J. Casper, H. Chafi, K. Olukotun: A Practical Concurrent Binary Search Tree. Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 2009. Google ScholarDigital Library
- C. Click: Towards a Scalable Non-Blocking Coding Style. http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdfGoogle Scholar
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 2nd Edition. The MIT Press, 2001. Google ScholarDigital Library
- F. Ellen, P. Fatourou, E. Ruppert, F. van Breugel: Non-blocking binary search trees. PODC, 2010. Google ScholarDigital Library
- E. Fredkin: Trie memory. Communications of the ACM, 1960. Google ScholarDigital Library
- A. Georges, D. Buytaert, L. Eeckhout: Statistically Rigorous Java Performance Evaluation. OOPSLA, 2007. Google ScholarDigital Library
- T. L. Harris, K. Fraser, I. A. Pratt: A Practical Multi-word Compareand-Swap Operation. DISC, 2002. Google ScholarDigital Library
- M. Herlihy: A Methodology for Implementing Highly Concurrent Data Structures. PPOPP, 1990. Google ScholarDigital Library
- M. Herlihy, Y. Lev, V. Luchangco, N. Shavit: A Provably Correct Scalable Concurrent Skip List. OPODIS, 2006.Google Scholar
- H. Kung, P. Lehman: Concurrent manipulation of binary search trees. ACM Transactions on Database Systems (TODS), vol. 5, issue 3, 1980. Google ScholarDigital Library
- Doug Lea's Home Page: http://gee.cs.oswego.edu/Google Scholar
- W. Litwin: Trie Hashing. Proceedings of the 1981 ACM SIGMOD international conference on Management of data, 1981. Google ScholarDigital Library
- W. Litwin, Y. Sagiv, K. Vidyasankar: Concurrency and Trie Hashing. Acta Informatica archive, vol. 26, issue 7, 1989. Google ScholarDigital Library
- Maged M. Michael: High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. SPAA, 2002. Google ScholarDigital Library
- M. Moir, N. Shavit: Concurrent data structures. Handbook of Data Structures and Applications, Chapman and Hall, 2004.Google Scholar
- C. Okasaki: Purely Functional Data Structures. Cambridge University Press, 1999. Google ScholarDigital Library
- A. Prokopec, P. Bagwell, M. Odersky: Cache-Aware Lock-Free Concurrent Hash Tries. EPFL Technical Report, 2011.Google Scholar
- A. Prokopec, P. Bagwell, T. Rompf, M. Odersky, A Generic Parallel Collection Framework. Euro-Par 2011 Parallel Processing, 2011. Google ScholarDigital Library
- William Pugh: Concurrent Maintenance of Skip Lists. UM Technical Report, 1990. Google ScholarDigital Library
- William Pugh: Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications ACM, volume 33, 1990. Google ScholarDigital Library
- The Scala Programming Language Homepage. http://www.scalalang.org/Google Scholar
- O. Shalev, N. Shavit: Split-Ordered Lists: Lock-Free Extensible Hash Tables. Journal of the ACM, vol. 53., no. 3., 2006. Google ScholarDigital Library
Index Terms
- Concurrent tries with efficient non-blocking snapshots
Recommendations
Fast concurrent lock-free binary search trees
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programmingWe present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. In addition to read and write instructions, our algorithm uses (single-...
Constant-time snapshots with applications to concurrent data structures
PPoPP '21: Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingGiven a concurrent data structure, we present an approach for efficiently taking snapshots of its constituent CAS objects. More specifically, we support a constant-time operation that returns a snapshot handle. This snapshot handle can later be used to ...
Concurrent tries with efficient non-blocking snapshots
PPoPP '12: Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel ProgrammingWe 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 ...
Comments