Cited time in webofscience Cited time in scopus

Performance analysis of cache-conscious hashing techniques for multi-core CPUs

Performance analysis of cache-conscious hashing techniques for multi-core CPUs
Kim, EuihyeokKim, Min-Soo
DGIST Authors
Kim, EuihyeokKim, Min-Soo
Issued Date
Article Type
Associative ProcessingBioinformaticsCache FriendlyChained HashingCompare-and-SwapCompare-and-SwapsComputer ArchitectureData StructuresHash TableHopscotch HashingIntel MicroarchitectureLinear HashingLock-Free Hash TablesMicro ArchitecturesMicroprocessor ChipsMulti-CoresMulticoresParallel ProgrammingProgram ProcessorsRefinable Hash TablesSystems Analysis
A hash table is a fundamental data structure implementing an associative memory that maps a key to its associative value. Due to its very fast mapping operation of O(1), it has been widely used in various areas such as databases, bioinformatics, and distributed computing. Besides, the paradigm of micro-architecture design of CPUs is shifting away from faster uniprocessors toward slower chip multiprocessors. In order to fully exploit the performance of such modern computer architectures, the data structures and algorithms considering parallelism become more important than ever. This paper implements three cache-conscious hashing methods, linear hashing and chained hashing, and also, a modern hashing method, hopscotch hashing, and analyzes their performance under Intel 32-core CPU of Nehalem microarchitecture. We implement each hashing method using state-of-the-art techniques such as lock-free data structures, especially based on compare-and-swap (CAS) operations, and refinable data structures. To the best of our knowledge, the work done by this paper is the first work analyzing the performance of three all hashing methods under the same implementation framework. Experimental results using data of 223 (i.e., about eight millions) key-value pairs shows that lock-free linear hashing is the best for insert operation among three hashing methods, and lock-free chained hashing is the best for lookup operation. Hopscotch hashing shows the second best performance of lookup operation. However, hopscotch hash table size is much bigger than other hash table size. Through experiments, we have found that the hopscotch hashing is relatively not efficient than other hash methods.
Security Engineering Research Support Center
Files in This Item:

There are no files associated with this item.

Appears in Collections:
Department of Electrical Engineering and Computer Science InfoLab 1. Journal Articles


  • twitter
  • facebook
  • mendeley

Items in Repository are protected by copyright, with all rights reserved, unless otherwise indicated.