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

Abstract

 

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.

 

Additional Resources

  1. The paper