Hash benchmarking

Inspired by Rusty's hashing comparison, I wrote a small benchmark program to compare different hashing methods with 32bit data stored. The program then was modified to test the methods with 128bit data stored. (The lookup3.c file with the Jenkins hash and the short types from CCAN are required.) Instead of the general case, the approaches were tailored to the problem when the data to be stored is small, so we cannot waste much memory on the container part of the hash elements.

The following methods were compared:

• Single linked list (single list): collisions are resolved by the truly single linked list of the elements, i.e. there is no "prev" pointer.
• Single linked list with resizing (resize list): the same as the previous one but when the length of a linked list exceeds 12, we double the hash and rehash the elements.
• Flat hash with rehashing (flat rehash): we store the elements in a huge array and collisions are resolved by hashing again with another init parameter of the hash function, at a maximum of 8 times. If we cannot find an empty slot, we double the hash and rehash the elements.
• Flat hash with linear search (flat linear): we store the elements in a huge array and collisions are resolved by searching linearly for an empty slot, at a maximum of 8 times. If we cannot find an empty slot, we double the hash and rehash the elements.
• Cache friendly hash (cache linear): the elements are stored in the hash in small arrays capable to store four elements. At a maximum three arrays are chained and if the fourth should be initialized, we double the hash and rehash the elements.

The methods were benchmarked when storing 32bit and 128bit data. With 32bit data, the initial hash size was 2²⁰ (1048576) and the number of elements were started from one million and then increased by another million at every round. With 128bit data, the initial hash size was 2¹⁷ (131072) and the number of elements were started from 100000 and then increased by the same number at every round. The program measured the time to insert the given number of elements; lookup all of them; lookup the same number of non-matching elements; delete the upper half part, add back, delete the lower half part and then add back; delete all elements; and how much memory is required to store the elements. The benchmark was run on a machine with two Intel Xeon 2.66GHz processors and 4GB of RAM. The program was stopped at the elem number of 40M which resulted this logfile. The graphs below were generated by a small Perl script and gnuplot. (I discarded the results from the last round because it produced abnormally large time values for the flat linear hash case, probably due to a large maintenance job started by cron.) With the 128bit data the resulted log file is here.

Single linked list

We can clearly see that simply using a linked list when the elements can (multiple times) exceed the hash size results longer and longer looking up time. Therefore I excluded the plain single list method from the comparisons below.

Insert

The graph shows how expensive is when we search for an empty slot by testing slots with hashing again and again. For small data the best is the flat array with linear searching, but for larger stored data the cache friendly hash performs the best. The cache friendly hash is always faster than the single linked list with resizing. So it seems cache friendlyness does indeed help. The same pattern can be seen in the delete-then-readd case too:

Lookups

The flat array methods are the winners but we can see that the cache friendly hash is again better than the resized single list approach. In the graph of the resized single list we can see when the hash were doubled.

Missed lookups

Here the flat array with rehashing again proves to be the slowest one. The resized linked list comes together with the other methods but is still a little bit slower than those.

Delete

The cache friendly hash is the slowest one when deleting the entries due to the required internal maintenance - it is much more simpler to delete an entry at the other methods. The missing "prev" pointer penalizes the linked list as well.

Memory

For small stored data the cache friendly hash is slightly better than the resized single list, but for larger stored data it wastes memory compared to the single list. The flat array methods waste a lot of memory and here we can see that the simple linear search is even worse than searching with rehashing with regard of the memory usage.

Summary

According to the graphs, if we have enough memory and want to optimalize just for speed, then huge arrays with linear search are the best. If we want to optimalize both for speed and memory, then the cache friendly hash can be a good choice.