Performance Analysis of Hashing Techniques for Multi-core CPUs

Abstract

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 four cache-conscious hashing methods, linear hashing and chained hashing, and also, a modern hashing methods, cuckoo hashing and 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 four 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 four hashing methods, and lock-free chained hashing is the best for lookup operation. Hopscotch hashing shows the second best per-formance of lookup operation. However, cuckoo hashing and hopscotch hash size is much bigger than other hash table size. Through experiments, we have found that the cuckoo hashing and hopscotch hashing are relatively not efficient than other hash methods. ⓒ 2013 DGIST