Hotrace

The program reads standard input in two phases. Before a blank line, lines come in pairs: a key, then its value. After the blank line, each line is a key to look up: we print its value, or a message if it does not exist. Ranking is based on execution time, on huge files.

All slots live in a single contiguous array (open addressing). A key is hashed with FNV-1a, and its starting position is hash & mask: since the capacity is always a power of two, the modulo becomes a single bitwise AND. If the slot is taken, we move one slot forward (linear probing), which stays in the same cache line.

Each slot also stores its key’s hash: strings are only compared when the hashes match. When the table goes over 75 % full, it doubles in size. The threshold is computed with integers to avoid floating point.

strcmp is rewritten with SSE2: pcmpeqb compares 16 bytes at once, then pmovmskb sums the result up as a 16-bit mask. A guard avoids reading 16 bytes across the end of a memory page, which could crash.

strlen uses the SWAR trick (8 bytes per register) to find the null byte, and bsf / bsr find the first set bit, for instance to compute the next power of two.