Rust anagram indexing driven from 173 to 11 nanoseconds per word with tuned primes

A blog post by David G. Andersen, published October 27, 2026 on his site Wiredream under the title "11 Nanoseconds per Word: Ridiculously Over-Optimizing Anagrams," reached Hacker News's front page in early November 2026. It walks through a Rust optimization exercise that most developers would have abandoned halfway — and its centerpiece is a method for giving every word in a Scrabble dictionary a collision-free 64-bit identifier built from prime numbers.

The puzzle that started it

According to the post, a friend introduced Andersen to a Word Ladder variant in which each step can change one letter, delete or add one letter, or rearrange all the letters of the current word. Because the anagram steps are difficult to spot by eye, he wrote a solver, and when it took over a second to run he turned to optimization. The post covers only the first stage: grouping the entire dictionary into anagram families. A follow-up post on solving the full ladder is promised.

Four optimizations, each measured

The classic way to group anagrams is to sort each word's letters into a canonical key — "spot" becomes "opst" — and use that key in a hash table. Andersen's baseline Rust version, run over the 178,690-entry Scrabble dictionary, took 31 milliseconds, or 173 nanoseconds per word. He points out that at that speed a modern laptop executes thousands of instructions per word, which he treats as an outrage worth correcting.

The first fix targeted allocations. With roughly 161,000 keys for 178,690 words, most hash table entries are singletons, so he stopped allocating a dynamic vector per key. Instead he emulates an append-only linked list using flat u32 arrays — a heads table plus next and word arrays — and overloads the high bit of each entry to distinguish a lone word from a list head. That cut the run to 20 milliseconds, or 112 nanoseconds per word.

The second fix changed the key itself: instead of sorting characters into a newly allocated string, he packs a letter-count vector into a u128 at 4 bits per letter (26 letters times 4 bits equals 104 bits). This removes the sort and the string allocation, bringing the time down to 5.6 milliseconds, 31 nanoseconds per word.

Third, he replaced Rust's default hash table with the FxHashMap from the rustc_hash crate, which is faster precisely because it omits defenses against adversarial hash-flooding inputs — a reasonable trade when the input is a trusted dictionary. Result: 4.1 milliseconds, 23 nanoseconds per word.

Fitting a Gödel number into 64 bits

The u128 key carries a hidden cost: it spans two registers, so additions carry between them and equality checks do twice the work. Compressing letter counts to 64 bits would allow only 2 bits per letter, too few for a word like MISSISSIPPI with its four S's.

Andersen's solution is Gödel numbering: assign each letter a distinct prime and identify a word by the product of its letters' primes, which is unique by unique factorization. The obvious assignment (a=2, b=3, c=5, and so on) overflows 64 bits at the 365th word in the dictionary, "ABORTIVENESSES" — and the dictionary contains 3,157 fifteen-letter words.

So he tuned the assignment against the corpus rather than general English letter frequency, working from the letter patterns in those long words. E keeps the prime 2, I gets 3, and the common T gets 29, while J can safely take the large prime 101 because the longest word containing two J's, JEJUNENESSES, is only 12 letters. With that tuning, every word's prime product fits in 64 bits with no collisions, so the hash table needs no equality-check fallback machinery. The post's title puts the final figure at 11 nanoseconds per word, and Andersen writes that he had not encountered the technique before, while suspecting Knuth probably noticed it around 1965.

Why it matters

The post is a compact lesson in the order of optimization: kill allocations first, then fix the data representation, then question general-purpose defaults — with every step measured and justified. The prime-product key is the standout idea, showing how a piece of classic number theory plus corpus-specific tuning can replace hash-collision handling entirely with single-register integer comparisons. Andersen is also candid about scope: if you only need the anagrams of one specific word, a simple hash table is fine, and the whole exercise exists because a full-dictionary anagram index feeds the word-ladder solver. That honesty, plus concrete numbers at every stage, is why a post about a word game ended up on Hacker News as a genuine engineering lesson.