A Compression-Based Design for Higher Throughput in a Lock-Free Hash Map
Pedro Moreno, Miguel Areias and Ricardo Rocha
August 2020
Abstract
Lock-free implementation techniques are known to improve the overall
throughput of concurrent data structures. A hash map is an important
data structure used to organize information that must be accessed
frequently. A key role of a hash map is the ability to balance
workloads by dynamically adjusting its internal data structures in
order to provide the fastest possible access to the information. This
work extends a previous lock-free hash map design to also support
lock-free compression. The main goal is to significantly reduce the
depth of the internal hash levels within the hash map, in order to
minimize cache misses and increase the overall throughput. To
materialize our design, we redesigned the existent search, insert,
remove and expand operations in order to maintain the lock-freedom
property of the whole design. Experimental results show that lock-free
compression effectively improves the search operation and, in doing
so, it outperforms the previous design, which was already quite
competitive when compared against the concurrent hash map design
supported by Intel.
Bibtex
@InProceedings{moreno-europar20,
author = {P. Moreno and M. Areias and R. Rocha},
title = {{A Compression-Based Design for Higher Throughput in a Lock-Free Hash Map}},
booktitle = {Proceedings of the 26th International European Conference on Parallel and
Distributed Computing (Euro-Par 2020)},
pages = {458--473},
number = {12247},
series = {LNCS},
publisher = {Springer},
editor = {K. Rzadca and M. Malawski},
month = {August},
year = {2020},
address = {Warsaw, Poland (online event)},
}
Download Paper
PDF file
Springer (Paper)
Springer (Artifact)