← All articles

Hash functions part 3 – performance

In part 1 we introduced hash functions, and in part 2 we took a look at what security means for hash functions. In this part, we will take a look at the performance characteristics of hash functions.

One of the most important aspects of hash functions is the performance. We want to map arbitrary data to an integer representation, and we want it to be fast since we are going to use it as an integral part of high-performance data structures. However, hash functions are notoriously hard to measure, as a fast hash function on one system, might be the slowest hash on another system. We will clarify that in just a minute.

Algorithmic Complexity#

Most hash functions can be grouped into a handful of different algorithmic complexity categories, as we started out doing in part 1. The relationship between the complexity and performance is tight, and we will always be in a situation where the simple hash functions will be able to outperform the more complex algorithms. This is simply due to the fact they need to do less work for each byte, compared to more complex algorithms.

Some algorithms might have a simple main loop made up of add, subtract, xor and shift operations, which are all fast on modern CPUs, but then finish up with a heavy mixer function for avalanching. Suffice to say, that simpler hash functions that don't do avalanching are always going to be a tiny bit faster, but also have worse security characteristics.

Code Speed vs. Instructions#

One of the most misunderstood concepts in computer science is code speed. Usually we observe that 10 lines of code are faster than 100 lines of code, but actually, nothing is further from the truth. Programming languages give us a way to build an abstraction to represent what we need, which is almost always easier to work with than machine language at the instruction level. Compilers nowadays are really clever, and they can actually optimize 100 lines of code to fewer instructions than those 10 lines of code.

Instruction Speed#

Some instructions are faster than others, and it is directly tied to the inner workings of the CPU and because of that, the speed varies a lot between different architectures. In this blog post, we work in orders of magnitude instead of specific timings. If you need specific timings, Agner Fog has an amazing list of timings for each CPU architecture on his website. If we group the speeds into 3 groups, ordered by descending speeds:

  1. Bitwise / addition / subtraction / shifts
  2. Multiplication
  3. Division

For simplicity, let's assume that a multiplication is 10x slower than additions, and divisions are 10x slower than multiplications. It is not quite correct, but close enough for our purposes.

Compiler Optimization: Modulus#

The modulus operator, often denoted as % in programming languages, is very common in hash functions. It returns the remainder of a division, which is usually used to trim a value to be within a range. Let's have a look at an example:

C#
int a = 10 % 3; // 1
int b = 11 % 3; // 2
int c = 12 % 3; // 0
int d = 13 % 3; // 1

For nonnegative values on the left, the results are within [0..2].

The modulus operator is actually quite slow. It's equivalent to:

Text
c = a – b * (a / b)

As you can see, it is a subtraction, a multiplication and a division operation, where the division is the really expensive operation. For this reason, compilers often try to optimize it. One really neat trick compilers do is to look for modulus that are powers of 2, and replace them with an and (&) operation instead. When n is unsigned and m is a nonzero power of 2, the following holds true:

Text
n % m == (n & (m - 1))

When the mask is known at compile time, this can reduce the calculation to a single AND instruction.

Putting It All Together#

In the phone directory, Bob and Dan both hash to 275. With eight buckets, 275 % 8 and 275 & 7 both select bucket 3. The bit mask can make bucket selection cheaper, but the table still has to compare names to return the right number, just as it did in part 1.

If anyone can submit names, a crowded bucket can make even a lookup for a missing name expensive. A suitable keyed hash makes bucket placement harder to predict, and request limits help bound the work a caller can trigger. Both matter for the networked directory in part 2.

When we benchmark the directory, we should measure the whole lookup: hashing the name, selecting the bucket, and searching it. Try names that are present and names that are missing, using key lengths and table sizes typical of the application. A cheaper hash or bucket calculation only helps if that saving survives the rest of the lookup.

More in Algorithms

All 25 Algorithms articles →