License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10070/
Go to the corresponding LIPIcs Volume Portal

Kelly, Robert ; Pearlmutter, Barak A. ; Maguire, Phil

Concurrent Robin Hood Hashing

pdf-format:
LIPIcs-OPODIS-2018-10.pdf (0.7 MB)

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
Collection: 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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI