DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.10

Concurrent Robin Hood Hashing

Authors: Robert Kelly, Barak A. Pearlmutter, and Phil Maguire

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

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.

Cite as

Robert Kelly, Barak A. Pearlmutter, and Phil Maguire. Concurrent Robin Hood Hashing. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@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}
}

Search Results

Documents authored by Kelly, Robert

Concurrent Robin Hood Hashing

Abstract

Cite as

Thanks for your feedback!

Could not send message