Aleksandar Prokopec
ABSTRACT
Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O(log n) time.
In this paper, we show that the concurrent hash trie operations can run in expected constant time. We present a novel lock-free concurrent hash trie design that exerts less pressure on the memory allocator. This hash trie is augmented with a quiescently consistent cache, which permits the basic operations to run in expected O(1) time. We show a statistical analysis for the constant-time bound, which, to the best of our knowledge, is the first such proof for hash tries. We also prove the safety, lock-freedom and linearizability properties. On typical workloads, our implementation demonstrates up to 5X performance improvements with respect to the previous hash trie variants.
Supplemental Material
Available for Download
zip
reactors-topic-cachetrie.zip (5.6 MB)
Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O (log n) time. This artifact contains present a novel lock-free concurrent hash trie implementation that exerts less pressure on the memory allocator. This hash trie is augmented with a quiescently consistent cache, which permits the basic operations to run in expected O (1) time. On typical workloads, our implementation demonstrates up to 5× performance improvements with respect to the previous hash trie variants.
- Miguel Areias and Ricardo Rocha. 2014. On the Correctness and Efficiency of Lock-Free Expandable Tries for Tabled Logic Programs. In Proceedings of the 16th International Symposium on Practical Aspects of Declarative Languages - Volume 8324 (PADL 2014). Springer-Verlag New York, Inc., New York, NY, USA, 168--183. Google Scholar
Digital Library
- Miguel Areias and Ricardo Rocha. 2016. A Lock-Free Hash Trie Design for Concurrent Tabled Logic Programs. Int. J. Parallel Program. 44, 3 (June 2016), 386--406. Google ScholarDigital Library
- Phil Bagwell. 2000. Fast And Space Efficient Trie Searches. Technical Report.Google Scholar
- Phil Bagwell. 2001. Ideal Hash Trees. (2001).Google Scholar
- Dmitry Basin, Edward Bortnikov, Anastasia Braginsky, Guy Golan-Gueta, Eshcar Hillel, Idit Keidar, and Moshe Sulamy. 2017. KiWi: A Key-Value Map for Scalable Real-Time Analytics. In Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '17). ACM, New York, NY, USA, 357--369. Google ScholarDigital Library
- Douglas Baskins. 2000. The Judy Array Implementation. http://judy.sourceforge.net/. (2000).Google Scholar
- Anastasia Braginsky and Erez Petrank. 2011. Locality-conscious Lock-free Linked Lists. In Proceedings of the 12th International Conference on Distributed Computing and Networking (ICDCN'11). Springer-Verlag, Berlin, Heidelberg, 107--118. http://dl.acm.org/citation.cfm?id= 1946143.1946153 Google ScholarDigital Library
- Anastasia Braginsky and Erez Petrank. 2012. A Lock-free B+Tree. In Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '12). ACM, New York, NY, USA, 58--67. Google ScholarDigital Library
- Nathan G. Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. 2010. A Practical Concurrent Binary Search Tree. SIGPLAN Not. 45, 5 (Jan. 2010), 257--268. Google ScholarDigital Library
- Cliff Click. 2007. Towards a Scalable Non-Blocking Coding Style. (2007). http://www.azulsystems.com/events/javaone_2007/2007_LockFreeHash.pdfGoogle Scholar
- Rene De La Briandais. 1959. File Searching Using Variable Length Keys. In Papers Presented at the the March 3--5, 1959, Western Joint Computer Conference (IRE-AIEE-ACM '59 (Western)). ACM, New York, NY, USA, 295--298. Google ScholarDigital Library
- Faith Ellen, Panagiota Fatourou, Eric Ruppert, and Franck van Breugel. 2010. Non-blocking Binary Search Trees. In Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC '10). ACM, New York, NY, USA, 131--140. Google ScholarDigital Library
- Edward Fredkin. 1960. Trie Memory. Commun. ACM 3, 9 (Sept. 1960), 490--499. Google ScholarDigital Library
- Andy Georges, Dries Buytaert, and Lieven Eeckhout. 2007. Statistically Rigorous Java Performance Evaluation. SIGPLAN Not. 42, 10 (Oct. 2007), 57--76. Google ScholarDigital Library
- Timothy L. Harris, Keir Fraser, and Ian A. Pratt. 2002. A Practical Multi-word Compare-and-Swap Operation. In Proceedings of the 16th International Conference on Distributed Computing (DISC '02). Springer-Verlag, London, UK, UK, 265--279. http://dl.acm.org/citation.cfm7id=645959.676137 Google ScholarDigital Library
- Maurice Herlihy, Yossi Lev, Victor Luchangco, and Nir Shavit. 2006. A Provably Correct Scalable Concurrent Skip List. (2006).Google Scholar
- Maurice Herlihy and Nir Shavit. 2008. The Art of Multiprocessor Programming. Morgan Kaufmann Inc., San Francisco, CA, USA. Google ScholarDigital Library
- P.G. Jensen, K.G. Larsen, and J. Srba. 2017. PTrie: Data Structure for Compressing and Storing Sets via Prefix Sharing. In Proceedings of the 14th International Colloquium on Theoretical Aspects of Computing (ICTAC'17) (LNCS). Springer, 1--18. To appear.Google Scholar
- Pramod G. Joisha. 2014. Sticky Tries: Fast Insertions, Fast Lookups, No Deletions for Large Key Universes. In Proceedings of the 2014 International Symposium on Memory Management (ISMM '14). ACM, New York, NY, USA, 35--46. Google ScholarDigital Library
- Charles Knessl and Wojciech Szpankowski. 2000. A Note on the Asymptotic Behavior of the Heights in b-Tries for b Large. Electr. J. Comb. 7 (2000). http://www.combinatorics.org/Volume_7/Abstracts/v7i1r39.htmlGoogle Scholar
- H. T. Kung and Philip L. Lehman. 1980. Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5, 3 (Sept. 1980), 354--382. Google ScholarDigital Library
- Doug Lea. 2014. Doug Lea's Workstation. (2014). http://g.oswego.edu/Google Scholar
- Franklin Mark Liang. 1983. Word Hy-phen-a-tion by Com-pu-ter. Ph.D. Dissertation. Stanford University, Stanford, CA 94305. Also available as Stanford University, Department of Computer Science Report No. STAN-CS-83-977.Google Scholar
- Ralph C. Merkle. 1988. A Digital Signature Based on a Conventional Encryption Function. In A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology (CRYPTO '87). Springer-Verlag, London, UK, UK, 369--378. http://dl.acm.org/citation.cfm?id=646752.704751 Google ScholarDigital Library
- Maged M. Michael. 2002. High Performance Dynamic Lock-free Hash Tables and List-based Sets. In Proceedings of the Fourteenth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '02). ACM, New York, NY, USA, 73--82. Google ScholarDigital Library
- Rotem Oshman and Nir Shavit. 2013. The SkipTrie: Low-depth Concurrent Search Without Rebalancing. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing (PODC '13). ACM, New York, NY, USA, 23--32. Google ScholarDigital Library
- Aleksandar Prokopec. 2014. Data Structures and Algorithms for Data-Parallel Computing in a Managed Runtime. Ph.D. Dissertation. IC, Lausanne.Google Scholar
- Aleksandar Prokopec. 2014. ScalaMeter Website. (2014). http://scalameter.github.ioGoogle Scholar
- Aleksandar Prokopec. 2015. SnapQueue: Lock-free Queue with Constant Time Snapshots. In Proceedings of the 6th ACM SIGPLAN Symposium on Scala (SCALA 2015). ACM, New York, NY, USA, 1--12. Google ScholarDigital Library
- Aleksandar Prokopec. 2016. Pluggable Scheduling for the Reactor Programming Model. In Proceedings of the 6th International Workshop on Programming Based on Actors, Agents, and Decentralized Control (AGERE 2016). ACM, New York, NY, USA, 41--50. Google ScholarDigital Library
- Aleksandar Prokopec. 2017. Analysis of Concurrent Lock-Free Hash Tries with Constant-Time Operations. ArXiv e-prints (Dec. 2017). arXiv:cs.DS/1712.09636Google Scholar
- Aleksandar Prokopec. 2017. Encoding the Building Blocks of Communication. In Proceedings of the 2017 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward! 2017). ACM, New York, NY, USA, 104--118. Google ScholarDigital Library
- Aleksandar Prokopec, Phil Bagwell, and Martin Odersky. 2011. Cache-Aware Lock-Free Concurrent Hash Tries. Technical Report.Google Scholar
- Aleksandar Prokopec, Phil Bagwell, and Martin Odersky. 2011. Lock-Free Resizeable Concurrent Tries. Springer Berlin Heidelberg, Berlin, Heidelberg, 156--170.Google Scholar
- Aleksandar Prokopec, Phil Bagwell, Tiark Rompf, and Martin Odersky. 2011. A Generic Parallel Collection Framework. In Proceedings of the 17th international conference on Parallel processing - Volume Part II (Euro-Par'11). Springer-Verlag, Berlin, Heidelberg, 136--147. http://dl.acm.org/citation.cfm?id=2033408.2033425 Google ScholarDigital Library
- Aleksandar Prokopec, Nathan Grasso Bronson, Phil Bagwell, and Martin Odersky. 2012. Concurrent Tries with Efficient Non-blocking Snapshots. (2012), 151--160. Google ScholarDigital Library
- Aleksandar Prokopec, Heather Miller, Philipp Haller, Tobias Schlatter, and Martin Odersky. 2012. FlowPools: A Lock-Free Deterministic Concurrent Dataflow Abstraction, Proofs. Technical Report.Google Scholar
- Aleksandar Prokopec, Heather Miller, Tobias Schlatter, Philipp Haller, and Martin Odersky. 2012. FlowPools: A Lock-Free Deterministic Concurrent Dataflow Abstraction. In LCPC. 158--173.Google Scholar
- Aleksandar Prokopec and Martin Odersky. 2015. Isolates, Channels, and Event Streams for Composable Distributed Programming. In 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software (Onward!) (Onward! 2015). ACM, New York, NY, USA, 171--182. Google ScholarDigital Library
- Aleksandar Prokopec and Martin Odersky. 2016. Conc-Trees for Functional and Parallel Programming. Springer International Publishing, Cham, 254--268. Google ScholarDigital Library
- A. Prokopec, D. Petrashko, and M. Odersky. 2015. Efficient Lock-Free Work-Stealing Iterators for Data-Parallel Collections. In 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing. 248--252. Google ScholarDigital Library
- William Pugh. 1990. Concurrent Maintenance of Skip Lists. Technical Report. College Park, MD, USA. Google ScholarDigital Library
- N. Shafiei. 2013. Non-blocking Patricia Tries with Replace Operations. In 2013 IEEE 33rd International Conference on Distributed Computing Systems. 216--225. Google ScholarDigital Library
- Michael J. Steindorfer and Jurgen J. Vinju. 2015. Optimizing Hash-array Mapped Tries for Fast and Lean Immutable JVM Collections. SIGPLAN Not. 50, 10 (Oct. 2015), 783--800. Google ScholarDigital Library
- Michael J. Steindorfer and Jurgen J. Vinju. 2016. Towards a Software Product Line of Trie-based Collections. In Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2016). ACM, New York, NY, USA, 168--172. Google ScholarDigital Library
Index Terms
- Cache-tries: concurrent lock-free hash tries with constant-time operations
Recommendations
Cache-tries: concurrent lock-free hash tries with constant-time operations
PPoPP '18Concurrent non-blocking hash tries have good cache locality, and horizontally scalable operations. However, operations on most existing concurrent hash tries run in O(log n) time.
In this paper, we show that the concurrent hash trie operations can run ...
LOFT: lock-free transactional data structures
PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel ProgrammingConcurrent data structures are widely used in modern multicore architectures, providing atomicity (linearizability) for each concurrent operation. However, it is often desirable to execute several operations on multiple data structures atomically. We ...
Transactional Lock Elision Meets Combining
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed ComputingFlat combining (FC) and transactional lock elision (TLE) are two techniques that facilitate efficient multi-thread access to a sequentially implemented data structure protected by a lock. FC allows threads to delegate their operations to another (...
Comments