A scalable lock-free hash table with open addressing

Jesper Puge Nielsen, Sven Karlsson

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Abstract

Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.
Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16% and 15% fewer L1 and L2 cache misses respectively, leading to 21% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19%
Original languageEnglish
Title of host publicationProceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
Number of pages2
PublisherAssociation for Computing Machinery
Publication date2016
Pages1-2
Article number33
ISBN (Print)978-1-4503-4092-2
DOIs
Publication statusPublished - 2016
EventACM SIGPLAN Symposium on Principles and Practice of Parallel Programming - Barcelona, Spain
Duration: 12 Mar 201616 Mar 2016

Conference

ConferenceACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
CountrySpain
CityBarcelona
Period12/03/201616/03/2016
SeriesACM SIGPLAN Notices
ISSN0362-1340

Cite this

Nielsen, J. P., & Karlsson, S. (2016). A scalable lock-free hash table with open addressing. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (pp. 1-2). [33] Association for Computing Machinery. ACM SIGPLAN Notices https://doi.org/10.1145/3016078.2851196
Nielsen, Jesper Puge ; Karlsson, Sven . / A scalable lock-free hash table with open addressing. Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, 2016. pp. 1-2 (ACM SIGPLAN Notices).
@inproceedings{c168c107d01d4c98ab0a905c87b26ea9,
title = "A scalable lock-free hash table with open addressing",
abstract = "Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33{\%} and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16{\%} and 15{\%} fewer L1 and L2 cache misses respectively, leading to 21{\%} fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19{\%}",
author = "Nielsen, {Jesper Puge} and Sven Karlsson",
year = "2016",
doi = "10.1145/3016078.2851196",
language = "English",
isbn = "978-1-4503-4092-2",
pages = "1--2",
booktitle = "Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming",
publisher = "Association for Computing Machinery",
address = "United States",

}

Nielsen, JP & Karlsson, S 2016, A scalable lock-free hash table with open addressing. in Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming., 33, Association for Computing Machinery, ACM SIGPLAN Notices, pp. 1-2, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Barcelona, Spain, 12/03/2016. https://doi.org/10.1145/3016078.2851196

A scalable lock-free hash table with open addressing. / Nielsen, Jesper Puge; Karlsson, Sven .

Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery, 2016. p. 1-2 33 (ACM SIGPLAN Notices).

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - A scalable lock-free hash table with open addressing

AU - Nielsen, Jesper Puge

AU - Karlsson, Sven

PY - 2016

Y1 - 2016

N2 - Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16% and 15% fewer L1 and L2 cache misses respectively, leading to 21% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19%

AB - Concurrent data structures synchronized with locks do not scale well with the number of threads. As more scalable alternatives, concurrent data structures and algorithms based on widely available, however advanced, atomic operations have been proposed. These data structures allow for correct and concurrent operations without any locks. In this paper, we present a new fully lock-free open addressed hash table with a simpler design than prior published work. We split hash table insertions into two atomic phases: first inserting a value ignoring other concurrent operations, then in the second phase resolve any duplicate or conflicting values.Our hash table has a constant and low memory usage that is less than existing lock-free hash tables at a fill level of 33% and above. The hash table exhibits good cache locality. Compared to prior art, our hash table results in 16% and 15% fewer L1 and L2 cache misses respectively, leading to 21% fewer memory stall cycles. Our experiments show that our hash table scales close to linearly with the number of threads and outperforms, in throughput, other lock-free hash tables by 19%

U2 - 10.1145/3016078.2851196

DO - 10.1145/3016078.2851196

M3 - Article in proceedings

SN - 978-1-4503-4092-2

SP - 1

EP - 2

BT - Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

PB - Association for Computing Machinery

ER -

Nielsen JP, Karlsson S. A scalable lock-free hash table with open addressing. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. Association for Computing Machinery. 2016. p. 1-2. 33. (ACM SIGPLAN Notices). https://doi.org/10.1145/3016078.2851196