Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2018.10
URN: urn:nbn:de:0030-drops-100701
URL: https://drops.dagstuhl.de/opus/volltexte/2018/10070/
Kelly, Robert ; Pearlmutter, Barak A. ; Maguire, Phil
Concurrent Robin Hood Hashing
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{kelly_et_al:LIPIcs:2018:10070,
author = {Robert Kelly and Barak A. Pearlmutter and Phil Maguire},
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 = {2018},
volume = {125},
editor = {Jiannong Cao and Faith Ellen and Luis Rodrigues and Bernardo Ferreira},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10070},
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}
}
| Keywords: | concurrency, Robin Hood Hashing, data-structures, hash tables, non-blocking | |
| Seminar: | 22nd International Conference on Principles of Distributed Systems (OPODIS 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 15.01.2019 | |
| Supplementary Material: | https://github.com/DaKellyFella/concurrent-robin-hood-hashing |
