Perfect Hashing

The beauty of perfect hashing is that you never have to deal with any collisions during item lookup. I recently created libphashtable, a perfect hashing hash table library for C/C++ which focuses on minimizing item lookup latency jitter. This article presents benchmarking results that show how its lookup times compare to those of a traditional hash table.

Overview

The libphashtable README contains some details on the libphashtable design and on hashing background. This diagram provides a short summary on how libphashtable works:

libphashtable lookup scheme

Results

Perfect Hashing Boxenplot

This graph is a boxenplot (a boxplot variant, a.k.a. letter-value plot) that describes all measured item lookup access times. It's a comparison of a standard hash-table, i.e. std::unordered_map (umap), against libphashtable (ptable), using different item hash functions on a high-end CPU (Intel Xeon Gold 6246) vs. a low-end CPU (Intel Atom C3768). Again, the libphashtable README's Measurements Section contains further details on the benchmark setup.

The median is marked by a dark grey line that is part (or on top) of the biggest box. The biggest box contains 50 % of the values. The next smaller boxes contain the next 25 %, 12.5 % etc. of the measured values. Outliers are drawn in a diamond shape, where, of course, multiple outliers may be drawn on top of each other.

Thus, the lower the median the better, less boxes are better than more, flat boxes are better than higher ones, less outliers are better than more, etc.

As expected, using a traditional hash table leads to much latency jitter. It's not just outliers, e.g. on Xeon 50 % of the lookups are distributed over a 5 to 10 ns wide range or so. While e.g. on the Atom CPU, 50 % of the lookups are distributed over a 20 ns range or so. The very simple and old SDBM item hash function over the board yields very good results. Also, using a more expensive item hash function doesn't really have a good trade off here, such as less collisions due to a better distribution of its range, i.e. the boxes and outliers basically are just shifted without being compressed.

The graph shows that libphashtable indeed yields a 'perfect' item lookup latency distribution. That means the boxes are so flat that the median line covers them all and there aren't any outliers, in most configurations. In general, using the SDBM hash function as item hash function is a safe choice, especially when targeting a low-end CPU.