Benchmark Hash Functions in Go for Speed and Spread

"Which hash should I use?" has several different questions inside it. For a hash table or a bucket choice you want speed and even spread. For a checksum you want to detect corruption cheaply. For a cache key or a deduplication fingerprint you want collisions to be rare. For a password or a signature you want something no one can reverse or forge, and speed is the enemy. This article times nine hash functions that Go programs commonly use at three input sizes, then measures how evenly the non cryptographic ones spread a million realistic keys, and states which question each answers. The answers surprised us twice: SHA-256 beat MD5, and the textbook FNV loses badly on large inputs.

It uses the method in benchmarking a Go function properly. For the map that these hashes feed, see maps against slices, and for hashing with a secret key see HMAC in Go. The cornerstone is the Go performance guide.

The contenders

• FNV-1a 64 (hash/fnv): a byte at a time, one multiply per byte. Tiny and simple. Two versions here: the standard library's and a hand written loop.
• hash/maphash: the standard library's seeded hash, the one Go's own maps use (through the runtime). Randomly seeded per process, so output is not stable across runs.
• xxhash 64 (github.com/cespare/xxhash/v2): a widely used fast non cryptographic hash with a stable, specified output.
• CRC32 (IEEE and Castagnoli): a checksum designed to catch transmission errors, accelerated by CPU instructions on most processors.
• MD5, SHA-1, SHA-256: cryptographic hashes from crypto/*.

The cryptographic ones return a byte array, and the lab takes one byte of it so that all nine return a number. The inputs are 16 bytes (a short key), 1 KB (a record) and 64 KB (a block).

package main

import (
	"crypto/md5"
	"crypto/sha1"
	"crypto/sha256"
	"flag"
	"fmt"
	"hash/crc32"
	"hash/fnv"
	"hash/maphash"
	"math"
	"sort"
	"strconv"
	"testing"

	"github.com/cespare/xxhash/v2"
)

func init() {
	testing.Init()
	flag.Set("test.benchtime", "150ms")
}

var sinkU uint64
var sinkB []byte

func fnv64a(b []byte) uint64 {
	h := fnv.New64a()
	h.Write(b)
	return h.Sum64()
}

func fnvInline(b []byte) uint64 {
	h := uint64(14695981039346656037)
	for _, c := range b {
		h = (h ^ uint64(c)) * 1099511628211
	}
	return h
}

var seed = maphash.MakeSeed()
var castagnoli = crc32.MakeTable(crc32.Castagnoli)

type hasher struct {
	name string
	f    func([]byte) uint64
}

func median(f func(b *testing.B)) float64 {
	const runs = 5
	xs := make([]float64, 0, runs)
	for i := 0; i < runs; i++ {
		r := testing.Benchmark(f)
		xs = append(xs, float64(r.T.Nanoseconds())/float64(r.N))
	}
	sort.Float64s(xs)
	return xs[runs/2]
}

func main() {
	hs := []hasher{
		{"fnv-1a 64 (hash/fnv)", fnv64a},
		{"fnv-1a 64 (inline loop)", fnvInline},
		{"maphash", func(b []byte) uint64 { return maphash.Bytes(seed, b) }},
		{"xxhash 64 (cespare)", xxhash.Sum64},
		{"crc32 IEEE", func(b []byte) uint64 { return uint64(crc32.ChecksumIEEE(b)) }},
		{"crc32 Castagnoli", func(b []byte) uint64 { return uint64(crc32.Checksum(b, castagnoli)) }},
		{"md5", func(b []byte) uint64 { s := md5.Sum(b); return uint64(s[0]) }},
		{"sha1", func(b []byte) uint64 { s := sha1.Sum(b); return uint64(s[0]) }},
		{"sha256", func(b []byte) uint64 { s := sha256.Sum256(b); return uint64(s[0]) }},
	}
	sizes := []int{16, 1024, 65536}
	data := map[int][]byte{}
	for _, n := range sizes {
		b := make([]byte, n)
		for i := range b {
			b[i] = byte(i*31 + 7)
		}
		data[n] = b
	}
	fmt.Printf("%-26s", "ns per hash")
	for _, n := range sizes {
		fmt.Printf(" %10s %9s", strconv.Itoa(n)+" B", "MB/s")
	}
	fmt.Println()
	for _, h := range hs {
		fmt.Printf("%-26s", h.name)
		for _, n := range sizes {
			b := data[n]
			ns := median(func(tb *testing.B) {
				for tb.Loop() {
					sinkU = h.f(b)
				}
			})
			fmt.Printf(" %10.1f %9.0f", ns, float64(n)/ns*1000)
		}
		fmt.Println()
	}

	fmt.Println()
	const keys = 1 << 20
	const buckets = 1 << 14 // 64 keys per bucket on average
	fmt.Printf("spread of %d sequential keys \"user:N\" over %d buckets (expected load %d, ideal std dev %.1f)\n", keys, buckets, keys/buckets, math.Sqrt(float64(keys/buckets)))
	for _, h := range []hasher{hs[0], hs[1], hs[2], hs[3], hs[4]} {
		counts := make([]int, buckets)
		for i := 0; i < keys; i++ {
			counts[h.f([]byte("user:"+strconv.Itoa(i)))%buckets]++
		}
		max, min := 0, keys
		var sum2 float64
		for _, c := range counts {
			if c > max {
				max = c
			}
			if c < min {
				min = c
			}
			d := float64(c) - float64(keys/buckets)
			sum2 += d * d
		}
		fmt.Printf("  %-26s min %3d  max %3d  std dev %5.1f\n", h.name, min, max, math.Sqrt(sum2/buckets))
	}
}

ns per hash                      16 B      MB/s     1024 B      MB/s    65536 B      MB/s
fnv-1a 64 (hash/fnv)              7.7      2079     1246.1       822    82074.8       798
fnv-1a 64 (inline loop)           7.6      2099     1296.7       790    82386.6       795
maphash                           3.3      4899       83.7     12230     5785.7     11327
xxhash 64 (cespare)              12.4      1294       69.9     14653     4526.6     14478
crc32 IEEE                        6.3      2537      104.4      9805     7722.4      8487
crc32 Castagnoli                  5.3      3007      101.2     10119     7704.4      8506
md5                             107.2       149     1675.3       611    99461.6       659
sha1                             59.8       268      478.1      2142    27053.6      2422
sha256                           54.1       296      471.4      2172    27112.6      2417

spread of 1048576 sequential keys "user:N" over 16384 buckets (expected load 64, ideal std dev 8.0)
  fnv-1a 64 (hash/fnv)       min  35  max  99  std dev   9.2
  fnv-1a 64 (inline loop)    min  35  max  99  std dev   9.2
  maphash                    min  36  max  96  std dev   8.0
  xxhash 64 (cespare)        min  34  max 100  std dev   8.1
  crc32 IEEE                 min  47  max  80  std dev   5.8

Speed

Short keys and long inputs have different winners

For a 16 byte key maphash took 3.3 ns, CRC32 about 5 to 6 ns, FNV 7.7 ns and xxhash 12.4 ns. xxhash is built to process large blocks with several lanes in parallel, and a 16 byte input does not give it enough to chew on, so its fixed setup shows. At 1 KB and above the order inverts: xxhash 69.9 ns, maphash 83.7 ns, CRC32 about 100 ns, FNV 1,246 ns. At 64 KB FNV ran at 798 MB/s and xxhash at 14,478 MB/s, 18 times faster.

If your keys are short identifiers, the difference between the fastest and the slowest non cryptographic hash is about 9 ns. If you hash blocks, files or messages, FNV is the wrong choice by an order of magnitude, and the reason is structural: each FNV step depends on the previous result, so the processor cannot overlap them.

The library version of FNV costs nothing extra

The hand written loop (7.6, 1,297 and 82,387 ns) matched hash/fnv (7.7, 1,246 and 82,075 ns). The compiler devirtualised the interface calls, so a cost you would expect to see (allocating a hasher, calling Write) did not show up on this input. On a hot path with tiny keys a stack allocated hasher is worth confirming with -benchmem.

SHA-256 beat MD5

SHA-256 ran at 2,417 MB/s and MD5 at 659 MB/s, 3.7 times slower. The reason is hardware: this Apple M1 Max, like most current ARM and many x86 processors, has instructions for SHA-1 and SHA-2, and Go uses them. No processor has an MD5 instruction, so MD5 runs as software. MD5 is broken for security and now is not even the fast legacy option on this hardware. Choosing it for speed is a mistake, and for integrity against an attacker it is a worse one. On an older x86 processor without SHA extensions the ranking may differ, so measure on the hardware that runs your code.

CRC32 is fast and specialised

CRC32 reached 8.5 GB/s, because it uses carry less multiplication instructions, and Castagnoli (used by iSCSI, Kafka and many storage formats) matched IEEE. A CRC detects accidental corruption, and it is trivial for an attacker to forge. It is also a 32 bit result: among a million items, collisions are likely, as the next section shows.

Spread

Speed is half of what a hash table wants. The other half is that keys land evenly. The lab hashes 1,048,576 sequential keys of the form user:N into 16,384 buckets (64 per bucket on average) and reports the lightest and heaviest bucket and the standard deviation of the bucket sizes. A perfectly random hash gives a standard deviation of about 8.0, the square root of the mean.

maphash and xxhash behaved like random functions: a deviation of 8.0 and 8.1 and a heaviest bucket of about 100, which is 1.6 times the average. FNV was a little worse, at 9.2. CRC32 was better than random (5.8), because sequential keys that differ in a few characters map to different values by construction, which is a property of the CRC and does not hold for all inputs.

For a bucketing job all four are acceptable on this input. The practical differences are elsewhere: FNV's weakness with similar keys shows on other patterns, and a 32 bit CRC cannot address more than 4 billion buckets or tell a billion keys apart.

Choosing

Never use a non cryptographic hash for security, and never use a fast hash for passwords. The speed that makes maphash good for tables is what makes it useless against a guesser.

Cautions

Stable output matters. maphash is seeded randomly per process, so it cannot be persisted or used for sharding across servers. Use xxhash or another specified function.

HashDoS. A table keyed by user input with a predictable hash can be attacked with colliding keys. Go's built in map is seeded for this reason, and a hand rolled table should use a seeded hash.

64 bits is not unique. With 64 bit hashes, collisions among a billion items are real (the birthday bound is about 4 billion). A cache key that must never collide should be compared in full after the hash matches.

The machine matters. CPU instructions for CRC and SHA change the ranking. The table above is for an M1 Max; an x86 server with AVX or SHA extensions is a different table.

Checklist

• Short keys: maphash or CRC32; large inputs: xxhash.
• FNV-1a is fine for tiny keys and 18 times slower than xxhash on 64 KB.
• SHA-256 was 3.7 times faster than MD5 on this CPU; avoid MD5.
• Spread was near ideal for maphash and xxhash on sequential keys.
• Use a seeded hash for tables keyed by untrusted input, and a slow one for passwords.
• Measure on your hardware.

The packages are documented at hash/maphash, crypto/sha256 and the xxhash repository.