A fast concurrent and resizable Robin Hood hash table

Concurrent hash tables are among the most important primitives in concurrent programming and have been extensively studied in the literature. Robin Hood hashing is a variant of linear probing that moves around keys to reduce probe distances. It has been used to develop state of the art serial hash tables. However, there is only one existing previous work on a concurrent Robin Hood table. The difficulty in making Robin Hood concurrent lies in the potential for large memory reorganization by the different table operations. This thesis presents Bolt, a concurrent resizable Robin Hood hash table engineered for high performance. Bolt treads an intricate balance between an atomic fast path and a locking slow path to facilitate concurrency. It uses a novel scheme to interleave the two without compromising correctness in the concurrent setting. It maintains the low expected probe count and good cache locality of Robin Hood hashing. We compared Bolt to a wide range of existing concurrent hash tables in a comprehensive benchmark. We demonstrate that on a 36-core machine with hyper-threading, Bolt is between 1.57x - 1.73x faster than the fastest publicly available non-resizable concurrent hash table and 1.45 - 2x faster than the fastest publicly available concurrent resizable hash table. It also achieves speedups between 15x - 35x over a highly optimized serial implementation at 36-cores with hyper-threading.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2021

Author dc:creator

• Kahssay, Endrias(Endrias K.)

Advisor dc:contributor.advisor

• Julian Shun.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses may be protected by copyright. Please reuse MIT thesis content according to the MIT Libraries Permissions Policy, which is available through the URL provided.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/130693

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/130693