|author:||Tom van Dijk|
|title:||Analysing and Improving Hash Table Performance|
|keywords:||analysis, performance, hash table, dictionary, cache, state search|
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.