Algorithmic improvements for fast concurrent cuckoo hashing

Xiaozhou Li, David G. Andersen, Michael Kaminsky, Michael J. Freedman

Research output: Contribution to conferencePaperpeer-review

122 Scopus citations


Fast concurrent hash tables are an increasingly important building block as we scale systems to greater numbers of cores and threads. This paper presents the design, implementation, and evaluation of a high-throughput and memory-efficient concurrent hash table that supports multiple readers and writers. The design arises from careful attention to systems-level optimizations such as minimizing critical section length and reducing interprocessor coherence traffic through algorithm re-engineering. As part of the architectural basis for this engineering, we include a discussion of our experience and results adopting Intel's recent hardware transactional memory (HTM) support to this critical building block. We find that naively allowing concurrent access using a coarse-grained lock on existing data structures reduces overall performance with more threads. While HTM mitigates this slowdown somewhat, it does not eliminate it. Algorithmic optimizations that benefit both HTM and designs for fine-grained locking are needed to achieve high performance. Our performance results demonstrate that our new hash table design-based around optimistic cuckoo hashing- outperforms other optimized concurrent hash tables by up to 2.5x for write-heavy workloads, even while using substantially less memory for small key-value items. On a 16-core machine, our hash table executes almost 40 million insert and more than 70 million lookup operations per second.

Original languageEnglish (US)
StatePublished - 2014
Event9th ACM European Conference on Computer Systems, EuroSys 2014 - Amsterdam, Netherlands
Duration: Apr 14 2014Apr 16 2014


Other9th ACM European Conference on Computer Systems, EuroSys 2014

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Control and Systems Engineering


Dive into the research topics of 'Algorithmic improvements for fast concurrent cuckoo hashing'. Together they form a unique fingerprint.

Cite this