Performance Analysis of Lock-Free Linear Hashing 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 0(1), it has been widely used in various areas such as databases, bioinformatics, and embedded systems. 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 a linear hashing method and analyzes its performance under Intel 32-core CPU microarchitecture. We implement the method in a lock-free manner, especially by using the compare-and-swap(CAS) operation, which is the state-of-the-art technique for parallelism. To the best of our knowledge, the work done by this paper is the first work analyzing the performance of a lock-free linear hash table under the Intel microarchitecture of a large number of cores. Experimental results using data of 2 23 (i.e., about eight millions) key-value pairs shows the performance of both insert and lookup operations is improved by up to more than 20 times compared with that of a single-threaded method. Through experiments, we also uncover the potential performance problem of the CAS-based parallelism of the Intel microarchitecture.