Document Open Access Logo

Concurrent Robin Hood Hashing

Authors Robert Kelly , Barak A. Pearlmutter , Phil Maguire

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.10.pdf
  • Filesize: 0.7 MB
  • 16 pages

Document Identifiers

Author Details

Robert Kelly
  • Maynooth University Department of Computer Science, Maynooth, Ireland
Barak A. Pearlmutter
  • Maynooth University Department of Computer Science and Hamilton Institute, Maynooth, Ireland
Phil Maguire
  • Maynooth University Department of Computer Science, Maynooth, Ireland

Funding

Funded by the Government of Ireland Postgraduate Scholarship.

Cite AsGet BibTex

Robert Kelly, Barak A. Pearlmutter, and Phil Maguire. Concurrent Robin Hood Hashing. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.10

Abstract

In this paper we examine the issues involved in adding concurrency to the Robin Hood hash table algorithm. We present a non-blocking obstruction-free K-CAS Robin Hood algorithm which requires only a single word compare-and-swap primitive, thus making it highly portable. The implementation maintains the attractive properties of the original Robin Hood structure, such as a low expected probe length, capability to operate effectively under a high load factor and good cache locality, all of which are essential for high performance on modern computer architectures. We compare our data-structures to various other lock-free and concurrent algorithms, as well as a simple hardware transactional variant, and show that our implementation performs better across a number of contexts.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Concurrent algorithms
Keywords
  • concurrency
  • Robin Hood Hashing
  • data-structures
  • hash tables
  • non-blocking

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. D. Alistarh, W. Leiserson, A. Matveev, and N. Shavit. ThreadScan: Automatic and Scalable Memory Reclamation. In SPAA, 2015. Google Scholar
  2. D. Alistarh, W. Leiserson, A. Matveev, and N. Shavit. Forkscan: Conservative Memory Reclamation for Modern Operating Systems. In EuroSys, 2017. Google Scholar
  3. A. Amighi, S. Blom, and M. Huisman. VerCors: A Layered Approach to Practical Verification of Concurrent Software. In 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, PDP, 2016. Google Scholar
  4. M. Arbel-Raviv and T. Brown. Reuse, Don't Recycle: Transforming Lock-Free Algorithms That Throw Away Descriptors. In DISC, 2017. Google Scholar
  5. M. Batty. The C11 and C++11 Concurrency Model. http://www.cl.cam.ac.uk/~mjb220/thesis/thesis.pdf. Accessed: 2017-05-04.
  6. T. Brown. A Template for Implementing Fast Lock-free Trees Using HTM. In PODC, 2017. Google Scholar
  7. P. Celis. Robin Hood Hashing. PhD thesis, University of Waterloo, Waterloo, Ont., Canada, Canada, 1986. Google Scholar
  8. C. Click. Lock-Free/Wait-Free Hash Table. http://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf. Accessed: 2017-05-04.
  9. N. Cohen and E. Petrank. Efficient memory management for lock-free data structures with optimistic access. In Proceedings of the 27th ACM symposium on Parallelism in Algorithms and Architectures, pages 254-263. ACM, 2015. Google Scholar
  10. T. Cormen, C. Stein, R. Rivest, and C. Leiserson. Introduction to Algorithms. McGraw-Hill Higher Education, 2nd edition, 2001. Google Scholar
  11. U. Drepper. What Every Programmer Should Know About Memory, 2007. Google Scholar
  12. J. Evans. JEMalloc, Retrieved 2018-08-06. Available at https://github.com/jemalloc/jemalloc. Google Scholar
  13. S. Feldman, P. LaBorde, and D. Dechev. A Wait-Free Multi-Word Compare-and-Swap Operation. International Journal of Parallel Programming, 43(4):572-596, August 2015. Google Scholar
  14. K. Fraser. Practical lock-freedom. Technical report, University of Cambridge, Computer Laboratory, 2004. Google Scholar
  15. G. Gonnet and R. Baeza-Yates. Handbook of Algorithms and Data Structures: In Pascal and C (2Nd Ed.). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1991. Google Scholar
  16. T. Harris. A Pragmatic Implementation of Non-blocking Linked-Lists. In Proceedings of the 15th International Conference on Distributed Computing, DISC, 2001. Google Scholar
  17. T. Harris, K. Fraser, and I. Pratt. A Practical Multi-word Compare-and-Swap Operation. In Proceedings of the 16th International Conference on Distributed Computing, DISC '02, pages 265-279, London, UK, UK, 2002. Springer-Verlag. Google Scholar
  18. M. Herlihy, V. Luchangco, and M. Moir. Obstruction-Free Synchronization: Double-Ended Queues As an Example. In Proceedings of the 23rd International Conference on Distributed Computing Systems, ICDCS '03. IEEE Computer Society, 2003. Google Scholar
  19. M. Herlihy and J. Moss. Transactional Memory: Architectural Support for Lock-free Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, ISCA '93. ACM, 1993. Google Scholar
  20. M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 1 edition, March 2008. Google Scholar
  21. M. Herlihy, N. Shavit, and M. Tzafrir. Hopscotch Hashing. In DISC '08: Proceedings of the 22nd international symposium on Distributed Computing, pages 350-364, Berlin, Heidelberg, 2008. Springer-Verlag. URL: http://dx.doi.org/10.1007/978-3-540-87779-0_24.
  22. M. Herlihy and J. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst., 12(3):463-492, July 1990. Google Scholar
  23. R. Kelly. Source Code For Lock-Free Robin Hood Benchmark. https://github.com/DaKellyFella/concurrent-robin-hood-hashing. Accessed: 2018-11-14.
  24. K. Rustan M. Leino and Peter Müller. A Basis for Verifying Multi-threaded Programs, pages 378-393. Springer Berlin Heidelberg, Berlin, Heidelberg, 2009. Google Scholar
  25. M. Michael. 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. ACM, 2002. Google Scholar
  26. M. Michael. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects. IEEE Trans. Parallel Distrib. Syst., 15(6):491-504, June 2004. Google Scholar
  27. J. Nielsen and S. Karlsson. A Scalable Lock-free Hash Table with Open Addressing. SIGPLAN Not., 51(8):33:1-33:2, February 2016. Google Scholar
  28. D. Lea P. William, S. Adve. JSR 133: JavaTM Memory Model and Thread Specification Revision. https://www.jcp.org/en/jsr/detail?id=133. Accessed: 2017-05-04.
  29. A. Padegs. System/370 extended architecture: Design considerations. IBM Journal of Research and Development, 27(3):198-205, 1983. Google Scholar
  30. C. Purcell and T. Harris. Non-blocking Hashtables with Open Addressing, pages 108-121. Springer Berlin Heidelberg, Berlin, Heidelberg, 2005. Google Scholar
  31. R. Rajwar and J. Goodman. Speculative lock elision: Enabling highly concurrent multithreaded execution. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, pages 294-305. IEEE Computer Society, 2001. Google Scholar
  32. O. Shalev and N. Shavit. Split-Ordered Lists: Lock-Free Extensible Hash Tables. In Proceedings of the 22nd Annual ACM Symposium on Principles of Distributed Computing (PODC), 2003. Google Scholar
  33. D. Siakavaras, K. Nikas, G. Goumas, and N. Koziris. Massively Concurrent Red-Black Trees with Hardware Transactional Memory. In 2016 24th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP), 2016. Google Scholar
  34. H. Sutter. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software. Dr. Dobb’s Journal, 30(3), 2005. Google Scholar
  35. Rust Core Team. Rust Collections Hash Table. https://doc.rust-lang.org/std/collections/struct.HashMap.html. Accessed: 2017-05-07.
  36. D. Terpstra, H. Jagode, H. You, and J. Dongarra. Collecting Performance Data with PAPI-C. In Tools for High Performance Computing 2009, pages 157-173, Berlin, Heidelberg, 2010. Springer Berlin Heidelberg. Google Scholar
  37. R. Yoo, C. Hughes, K. Lai, and R. Rajwar. Performance Evaluation of Intel; Transactional Synchronization Extensions for High-performance Computing. In Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis, SC. ACM, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact