|
Title:
|
MODELLING PERFORMANCE IMPACT OF CACHES ON HASH TABLE PERFORMANCE |
|
Author(s):
|
Sándor Kolumbán , Sándor Juhász , Ákos Dudás |
|
ISBN:
|
978-972-8924-86-7 |
|
Editors:
|
Hans Weghorn, Jörg Roth and Pedro Isaías |
|
Year:
|
2009 |
|
Edition:
|
Single |
|
Keywords:
|
Linear probing, double hashing, quadratic quotient, uniform hashing, probe length, cache friendliness. |
|
Type:
|
Full Paper |
|
First Page:
|
34 |
|
Last Page:
|
42 |
|
Language:
|
English |
|
Cover:
|
|
|
Full Contents:
|
click to dowload 
|
|
Paper Abstract:
|
Several recent papers have analysed the connection between the major characteristics of hashing algorithms (like probe
length) and their performance. Their results indicate that, depending on the parameters of the experimental setup, the
cache friendly behaviour of algorithms can have significant effect on the performance ranking of these algorithms. In this
paper, we examine this effect through the comparison of hashing with simple linear probing and more complex collision
avoidance mechanisms. A multi-parametric model will be presented, which links these previously mentioned
experimental results. Among sophisticated collision avoidance algorithms, we will consider the linear double hashing and
the quadratic quotient methods. A mathematical model will be presented for estimating probe lengths and number of
cache misses of the different approaches. We will show how cache friendliness is related to probe lengths of the
considered hashing algorithms and how it affects their performance. Our results will be supported by experiments, and
previous results of other authors will be interpreted through our model. |
|
|
|
|
|
|
