Kelly, Robert and Pearlmutter, Barak A. and Maguire, Phil (2018) Concurrent Robin Hood Hashing. In: 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Schloss Dagstuhl, 10:1-10:16. ISBN 9783959770989

Preview

Download (741kB) | Preview

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.

Item Type:	Book Section
Additional Information:	© Robert Kelly, Barak A. Pearlmutter, and Phil Maguire; licensed under Creative Commons License CC-BY https://creativecommons.org/about/cclicenses/. Cite this version s: arXiv:1809.04339 [cs.DC]
Keywords:	concurrency; robin hood hashing; data-structures; hash-tables; lock-free;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	14238
Identification Number:	https://doi.org/10.4230/LIPIcs.OPODIS.2018.10
Depositing User:	Phil Maguire
Date Deposited:	23 Mar 2021 17:15
Publisher:	Schloss Dagstuhl
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads