Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Kelly, Robert; Pearlmutter, Barak A.; Maguire, Phil http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-100701
URL:

; ;

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


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