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.
@InProceedings{kelly_et_al:LIPIcs.OPODIS.2018.10, author = {Kelly, Robert and Pearlmutter, Barak A. and Maguire, Phil}, title = {{Concurrent Robin Hood Hashing}}, booktitle = {22nd International Conference on Principles of Distributed Systems (OPODIS 2018)}, pages = {10:1--10:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-098-9}, ISSN = {1868-8969}, year = {2019}, volume = {125}, editor = {Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.10}, URN = {urn:nbn:de:0030-drops-100701}, doi = {10.4230/LIPIcs.OPODIS.2018.10}, annote = {Keywords: concurrency, Robin Hood Hashing, data-structures, hash tables, non-blocking} }
Feedback for Dagstuhl Publishing