Strongly universal string hashing is fast
Owen Kaser, Daniel Lemire
cs.DB, cs.DS
2012-02-23
Multilinear hashing computed with plain 64-bit multiply-add and a right shift is strongly universal, runs at 0.2-0.5 cycles per byte on desktop CPUs, and beats Rabin-Karp by 1.7x or more.
Hash tables, Bloom filters, cardinality estimators and set-intersection algorithms all get their performance guarantees from hashing that is random enough. The textbook answer is to draw a function at random from a strongly universal family, where the hash values of any two distinct inputs are independent. Production code instead runs functions like Rabin-Karp or SAX that carry no guarantees at all, on the assumption that guarantees cost speed. Measurements across 12 processors here say the opposite: on 64-bit desktop and server CPUs, the strongly universal families are faster by 1.7x to 3.3x.
Two other pieces of conventional wisdom get tested and fail: "fewer multiplications run faster", and "hardware carry-less multiplication should make binary finite fields competitive".
Multilinear hashing is defined over a finite field: h(s) = m1 + Σ m(i+1)·si with random coefficients. Over a field it is strongly universal, but software finite-field multiplication is expensive.
The key construction generalizes a 1996 trick of Dietzfelbinger from single integers to strings: compute the same inner product in plain unsigned 64-bit arithmetic with no reduction, then shift right by 32 bits and keep the top half. Theorem 3.1 proves the family stays strongly universal. The proof rests on a fact that can be stated plainly: multiplying by an odd number is a bijection modulo 2^K, and when the multiplier carries τ trailing binary zeros, Proposition 3.1 shows the equation (ax+c mod 2^K) ÷ 2^(L-1) = b has exactly 2^(L-1) solutions. The count is exact, so pairwise independence survives.
In C the whole hash is a three-line loop, sum += m p, ending with return sum >> 32. One multiplication and one addition per 32-bit character, 2n+1 operations in total, at most twice a counting lower bound.
Multilinear-HM halves the multiplications by folding two adjacent scalar products into one: (m2i+s2i-1)·(m2i+1+s2i). Variable-length strings append a character value of one so no string ends in zero, or prepend the length.
The bill comes in random bits: 64 per 32-bit input character. Stinson's bound says strong universality itself needs about 32(n+1) bits, so this memory price cannot be engineered away.
Cycles per byte, 64-bit processors, 32-bit hash values (from Tables 2 and 3):
| Processor | best Multilinear | Rabin-Karp | SAX |
| Intel i7-2677M | 0.20 | 0.64 | 0.82 |
| Intel Core 2 Duo | 0.52 | 1.3 | 1.3 |
| AMD FX8150 | 0.51 | 0.86 | 1.3 |
Across eight desktop and server processors, the family with the strongest guarantee leads on every chip.
Multilinear-HM, with half the multiplications, wins only on AMD (about 33% faster) and VIA (45%); on Intel it ties the double-multiplication version, which the authors attribute to Intel's multiplication pipelining. ARM is the counter-intuitive case: on the Apple A4 and Tegra 2, both equipped with a multiply-accumulate instruction, the 2-by-2 unrolled variant with the most multiplications is the fastest.
The carry-less multiplication route loses across the board. The best GF variant on an i7-2600 runs at 1.1 cycles per byte, four times slower than Multilinear-HM at 0.27, capped by that Intel generation's throughput of one carry-less product every 8 cycles. The mpFb software finite-field library is an order of magnitude slower: 7.69 µs versus 0.78 µs for a 4 kB string. GMP with 512-bit words is 12x slower; the GCC uint128 extension is 38% slower.
The one peer is NH, the almost-universal family from the UMAC authors: roughly tied on five of eight processors, clearly faster on the i7-2600, i7-2677M and FX8150 (0.16 vs 0.27, 0.12 vs 0.20, 0.17 vs 0.51). NH needs about half the random bits, but its output has to be 64 bits wide to reach the same 1/2^32 collision probability, and it fails uniformity. Trading away guarantees bought speed on three chips out of eight.
32-bit embedded chips flip the picture: an Atom N270 needs 3.6 cycles per byte for the best Multilinear against 1.1 for Rabin-Karp. The recommendation is explicitly limited to 64-bit desktop and server CPUs.
Randomized hashing is the standard defense against hash-flooding denial of service, where an attacker feeds a hash table keys chosen to land in one bucket and drags operations toward quadratic time; Ruby 1.9 and Perl 5.8.1 adopted it for exactly this reason. This paper removes the speed excuse: on 64-bit server hardware the theoretically strongest option is also the fastest, using ordinary integer multiplication, no SIMD, no special instruction set.
The methodological lesson outlives the hardware. Counting operations on a superscalar CPU produces wrong conclusions: once multiplications pipeline, they are nearly free, and algebraic tricks that shrink their count can be worthless or harmful. Any optimization sold as "fewer multiplications" needs a benchmark before it needs a proof.
For sketches, cuckoo hashing and set intersection, anything that assumes pairwise independence, there is a three-line implementation to copy.
The random buffer is a real cost: hashing 4 kB consumes 8 kB of random material, and the authors call generating and storing it "the main difficulty". Stinson's bound means no strongly universal family does much better.
Timings are lab-best: one randomly generated 4 kB string hashed repeatedly, compiler flags tuned by trial and error. The authors note that real applications should expect degradation from bandwidth and caching.
The hardware is from 2011-2012: Core 2 through i7-2600, ARM A4, Tegra 2, GCC 4.x. The one-carry-less-multiply-per-8-cycles ceiling belongs to that Intel generation; modern CPUs execute carry-less multiplication far faster, so the CLMUL verdict deserves a rerun on current silicon. Deeper multiplication pipelines only strengthen the finding that fewer multiplications do not help.
The paper also leaves a small conjecture open: for every L there exists an irreducible polynomial with degree(p(x) − x^L) ≤ L/2, the property the fast Barrett reduction relies on. No proof given.