Our '1 in 3 billion' hash collision showed up on seed 6

We wrote a comment in our code saying the chance of a hash collision was about 3 × 10⁻¹⁰ per run. The hash was 64 bits, there were 100,000 names, and the birthday arithmetic was correct.

Then a teammate generated a dataset with a new seed, and two names collided in all 64 bits:

"Dacom Mina" -> 0x916714a150607c41 "Dacom Maca" -> 0x916714a150607c41 

That was the most useful thing we learned in Speed Demon 2026, a 72-hour performance hackathon run by Hackathon Raptors. Four tasks, each with a slow Python reference, and you are scored on time, peak memory and code size on a fixed machine: an i5-13500 with 6 cores and 12 threads, turbo off.

Three of us entered as Deez-attacher: me, dannyamah and realist. We wrote Rust with zero dependencies and used Claude Code heavily. Some of the mistakes below are ones it made and I accepted. The code and every measurement are in the repo.

Here is where we ended on the public board at code freeze. Final scores, on a seed nobody has seen, aren't out yet.

Solidly mid-table. The leaders ran A and C in 0.014 s. So read this as a list of what cost us time, not a recipe for winning.

The collision: odds that were never real

To count distinct names per country in track C, we identified each name by a hash and never compared bytes. That change took the track from 0.069 s to 0.060 s. The hash was an FxHash-style step over 8-byte words, followed by the MurmurHash3 finaliser:

fn mix(h: u64, w: u64) -> u64 { (h.rotate_left(5) ^ w).wrapping_mul(0x517c_c1b7_2722_0a95) } 

Here is how two names defeat it:

1. Dacom Mi and Dacom Ma differ only in their last byte. i ^ a is 0x08, so the two words differ only at bit 59.
2. Multiplying can only carry a difference upward, so after the multiply the two states differ only in their top five bits.
3. rotate_left(5) moves those five bits to the bottom of the word, exactly where the next word's first byte gets XORed in.
4. If n ^ c happens to equal that difference, it cancels, and the two states are now identical.

The finaliser can't help, because it is a bijection: equal inputs stay equal.

I reproduced this in Python. Take two 10-byte names that share their first seven bytes, set the eighth to i and a, and try every lowercase letter for the ninth: about 1 pair in 35 collides (15,034 of 520,000). In 200,000 pairs of random names, none did.

The 3 × 10⁻¹⁰ figure assumed the hash behaved randomly, on input that was anything but random. Names in this dataset are built from a shared vocabulary, so near-duplicates are common.

Every check we had passed: the board's seed, plus our seeds 2 and 3. realist found it by adding seeds 4 to 7, and C undercounted distinct names on seed 6 only. Final scoring runs on an unseen seed and every run must be correct, so this could have zeroed the track. The fix was a folded multiply (a 64×64→128-bit multiply with the halves XORed together), tested with zero collisions on 2.9 million deliberately near-duplicate names.

What I'd do differently: a collision probability is a claim about your hash, so test it on the nastiest input you can build before you believe the number.

Three benchmarks, each blind to something different

We ended up with three ways of measuring, and every one of them misled us.

Each blind spot cost us something real.

The Mac hid a third of track B's corpus pass. A counting sort cost about 5 ns per posting locally and about 48 ns on the box. It scattered writes across 53,000 per-term cursors, which fits in the Mac's L2 and misses constantly in 1.25 MB shared by two hyperthreads.

The board made us throw away real wins. I rejected an AVX2 endpoint scan because a single board run showed about 2%. Later, the A/B runner measured a similar scan at 1.055x (95% CI 1.049 to 1.059). dannyamah reverted a D change after two noisy samples, then restored it when A/B measured 1.073x.

The runner couldn't see contention. Some of its wins vanished on the box and were reverted. The reverse also happened, as the next section shows.

The A/B tool (dev/tools/ab.py) arrived on the last full day, and I wish we'd had it on the first. It alternates two binaries in ABBA order so that drift hits both equally, and reports a bootstrap interval. Our rule became: compute changes go through A/B, and anything about threads or memory goes to the board.

The lock we tested for and wrongly ruled out

Removing the endpoint lookup from track A's parser saved about 9 ms, which works out to around 100 cycles per lookup on a 64 KB thread-local table. That is far too slow for a table in cache.

A shared registry sat behind that table, behind a mutex, taken only the first time each thread met a name. All 12 threads start on the same part of the file and meet the same names at once. So I suspected the lock, and tested thread-local ids with no registry. It came back slower twice, at 0.0432 and 0.0435 s against 0.0396. I crossed the lock off.

That was the wrong conclusion, for two reasons. Unchanged code later measured 0.0432 on the same board, so my evidence was inside the noise. And my replacement added a rank lookup per record, so I hadn't tested "no lock". I had tested "no lock, plus new work".

realist later replaced the registry with one lock-free table shared by all threads. Parsing went from 28.5 ms to 19.9 ms. That is contention the 2-vCPU runner can't see at all.

Track D had a lock bug of its own, and this one is worth checking for in your own Rust:

// Holds the lock for the whole loop body: temporaries in a // `while let` scrutinee live until the end of the body. while let Some((b, rows)) = work.lock().unwrap().next() { fill_bucket(b, rows, /* ... */); } // Holds it only to pick the next bucket. loop { let Some((b, rows)) = work.lock().unwrap().next() else { break }; fill_bucket(b, rows, /* ... */); } 

Our "parallel" build was running one bucket at a time. Together with a smaller distance-map entry in the same commit, the fix took D from 0.246 s to 0.193 s.

Timing probes: wrong answers on purpose

The board has no profiler, but it reports time and memory even when your output is wrong. So we committed versions that write an empty file and exit after a given phase:

std::fs::write(out.join("summary.txt"), b"").unwrap(); // TIMING PROBE std::process::exit(0); 

Every push ran all four tracks, so one board slot could carry a probe on one track and an experiment on another. We logged 42 probe runs over the event. Subtracting probes against each other told us where B's time went, on the real hardware:

No local profile had made that 84 ms sort look like a problem. My fix, scattering one term range at a time, recovered only about 22 ms of it, but we'd never have looked there otherwise.

The two-line change

This is a realist find in track C. Every record checked for a byte order mark:

// before if c[p..].starts_with(BOM) { // after: every byte but a BOM's is ASCII (spec 2.2), so 0xEF at a record start is one if c[p] == BOM[0] { 

Three bytes, a memcmp call, 3.3 million times. 1.080x on the A/B runner, the largest single compute win on that track. It works because the spec guarantees everything else is ASCII, so the first byte is enough. Reading the spec closely found more speed than most of our SIMD did.

The optimisation that failed, then won

On day two I tried summarising query results in bulk, with a popcount per bitmap word and six masked popcounts for the sum of bit positions, and only the first ten ids handled one by one. The board said 0.319 s against 0.314 s, so I reverted it.

The next day, dannyamah tried the same idea and measured 1.074x (CI 1.071 to 1.077). In between, the threshold for turning a term into a bitmap had moved from 1/16 of a chunk to 1/64. Far more result data was in bitmaps now, so the code path I'd tested on barely-used data had become the hot one.

A reverted experiment only tells you about the code as it was that day. We kept every failure in PERF.md, 37 labelled in the run log, and that record is how an old idea got a second look.

Freeing memory is a multi-core event

Track A freed about 860 record blocks one at a time. Each munmap is a TLB shootdown that interrupts every core. Reserving one mapping per hour and returning it with a single munmap took the run from 0.033 s to 0.028 s, without changing any of the actual work.

What we never figured out

• About 24 MB on B and D. The box charged us that much more than our arrays explain. It wasn't thread stacks, and one malloc arena saved only 3.7 MB.
• Returning memory on D. Giving back the build's edge arrays with madvise raised the peak from 160 MB to 233 MB, even at 2 MB granularity. I suspect transparent huge pages, but we never proved it. Smaller rows are what finally brought it down to 125 MB.
• How the leaders did it. The top team ran D in 0.061 s against our 0.194 s. A profile puts 22% of our run in distance-map probes. We never tried goal-directed search, which is my best guess, and it is only a guess.

If you only keep three things

1. Test your hash on adversarial near-duplicates. The birthday bound assumes randomness you may not have.
2. Know what your benchmark can't see. A 2-vCPU runner can't see contention, a laptop can't see the target's cache, and one noisy sample can't see 5%.
3. Log your failures with their numbers, and retest them when the code around them changes.

Everything is public: the repo, with a PERF.md per track listing every board run, probe and reverted experiment. Thanks to Hackathon Raptors for running it. Final results come out November 13, and I'll find out then whether our hash survives a seed it has never seen.