Performance analysis of multi-threaded locking in bucket hash tables

Abstract. Data structures, such as hash tables, are often accessed from within critical sections in multi-threaded environments in order to preserve data integrity. The extent of mutual exclusion greatly affects the performance by limiting the level of achievable parallelism. Increasing the resolution of locking allows higher throughput at the cost of increased memory use with all its side effects. Highly concurrent bucket hash tables use fine-grained locking where each lock protects one or a few buckets. In this paper we analyze the behavior or large hash tables with respect to their performance when the granularity of locking changes. We offer a simplified queuing model for estimating the number of locks that the hash table should use for maximum efficiency. The model and its suggestions are evaluated under real-life circumstances by testing a concurrent custom bucket hash table.