An improved cuckoo hash table for multi-core CPUs

作者：Yuan Tong^*; Liu Zhijing; Wang Zi; Liu Hui

来源：Journal of Computational Information Systems, 2014, 10(21): 9379-9386.

DOI：10.12733/jcis12645

• Better performance
• Cuckoo hashing
• Data-level parallelism
• Hash table
• Key-value stores
• Multi-core processor
• Thought experiments
• Thread level parallelism

Concurrent hash tables play an more important role in various areas as modern CPUs have greater numbers of cores and threads. In this paper, we propose an improved cuckoo hash table for multi-core CPUs with exploiting thread-level parallelism and data-level parallelism. We firstly introduce the structure of our proposed cuckoo hash table, which is a combination of the standard cuckoo hash table and the chained hash table, and supports multiple reader/multiple writer access. Then we propose two optimizations for lookup operation; one is the use of SIMD instructions for tag-based lookup operation, the other is the transfer operation when deleting one pair from the cuckoo hash table. Thought experiments on 8-core platform, we have finally shown that our improved cuckoo hash table has better performance of insert operation and lookup operation, especially in the lookup operation, and that our proposed hash table is suitable for various hardware platforms.

• 出版日期2014
• 单位西安电子科技大学