Hashing and SwissTable

5.4 Finding by key: the hash map and the dense array

When an update for instrument 42 reaches the strategy thread on core 3, the strategy first needs its position in BTC-USDT-PERP: given a key, find the value. Most programs answer with a hash map, which works for any key. A trading loop can usually answer with an array, which works only for small integer keys and costs a twentieth to a fiftieth as much.

What a hash map is

If the keys were the integers 0 to N − 1, a key could be an array index and no map would be needed. Usually they are not: a symbol is a string, and a venue’s id can be any of four billion numbers. A hash function bridges the gap: a function from a key to a number, 64 bits in Rust, that always gives the same number for the same key and spreads different keys evenly over its range, so that the number, cut down to the size of an array, picks a slot. The slots are buckets, and in Rust’s map each holds at most one entry, a key and its value side by side. Two keys whose numbers pick the same bucket collide, and one must go elsewhere. Rust’s map uses open addressing: the second key goes into another bucket of the same array, chosen by a fixed rule, and the sequence of buckets the rule visits is the probe. A lookup hashes the key, goes to the bucket it picks, compares the key there, and probes on until it finds its key or an empty bucket, which means the key is absent. The alternative, chaining, hangs a linked list from each bucket instead.

The hash function: SipHash, and hash flooding

Rust’s HashMap hashes with SipHash-1-3 by default, from the SipHash family Jean-Philippe Aumasson and Daniel J. Bernstein published in 2012; the digits count its rounds, one of mixing per 8 bytes of input and three to finish. SipHash is keyed: it mixes in a secret random key, which the map’s RandomState hasher takes from the operating system’s random source, so that nobody without the key can predict which bucket a given key lands in.

That is the defence against hash flooding. An attacker who chooses the keys a program inserts, such as the headers of a web request, and knows the hash function, can choose thousands that share one probe sequence; each insert then probes past every earlier one, n inserts cost about n²/2 probes, and the server spends its time probing instead of serving. Without the key the attacker cannot tell which keys collide. The protection costs 15–25 ns on a u32, 60–100 cycles, most of a lookup; the standard library’s documentation itself says other algorithms outperform it for small keys such as integers.

FxHash and ahash are the fast alternatives, at 1–3 ns. FxHash, from the rustc-hash crate, is the Rust compiler’s own hasher, named after the Firefox function it began as; for an integer it is an add, a multiply and a rotate, with no key, so anyone who knows the formula can make keys collide. ahash uses the processor’s AES instructions and is keyed, though its authors do not claim cryptographic strength. With either, a hit costs 5–15 ns. They are safe when nobody hostile chooses the keys: ids the program assigned, venue ids from the venue’s published list of instruments, order ids it generated. Keys from the outside world keep SipHash.

SwissTable: buckets, control bytes and groups

Since Rust 1.36 the standard HashMap has been the hashbrown crate’s port of Google’s SwissTable, which keeps two arrays: the buckets and, beside them, one control byte per bucket. A control byte records what its bucket holds: 0xFF for empty, 0x80 for an entry since deleted, or, when full, a byte whose top bit is clear and whose other 7 bits are the top 7 bits of the entry’s hash. The hash is used twice: its lowest bits pick the starting bucket (the bucket count is always a power of two, so keeping the low bits is the same as taking the remainder), and its top 7 bits are the tag the search looks for.

The control bytes are read 16 at a time, a group as wide as one SSE2 register, the 16 bytes that x86-64’s SIMD instructions work on together; without SIMD a group is 8 bytes, one 64-bit word. A lookup loads the group at its starting position, compares all 16 bytes with 16 copies of the tag in one instruction, pcmpeqb, and turns the result with pmovmskb into a 16-bit mask with a bit set for each bucket whose tag matched. Only those buckets have their keys compared, usually just the right one, since another key’s tag matches by chance one time in 128. If nothing matches and the group holds an empty byte, the key is absent; only a group full of other keys sends the probe on, to the next group, then two further, then three, a triangular sequence that visits every group once. Most lookups end in the first group, so a hit costs the hash plus one group line and one entry line: 5–15 ns of probing on top of the hash’s 15–25, 20–50 ns with the table in L1 or L2, and 50–100 ns cold in L3, where both lines miss.