Tom van Dijk - Analysing and Improving Hash Table Performance

author:Tom van Dijk
title:Analysing and Improving Hash Table Performance
keywords:analysis, performance, hash table, dictionary, cache, state search
graduation date:January 2009



In this paper we describe three methods for analysing how different algorithms use a dictionary. With these methods, the implementation of the dictionary can be fine-tuned, in order to increase performance. The methods aim at discovering patterns that can be used to achieve more optimal use of hierarchical memory, especially L2 cache. Our research mainly focuses on improving the performance of hash tables used by state search algorithms. We also present some pitfalls that may appear when trying to improve performance.