11 Nanoseconds per Word: Over-Optimizing Anagrams

A solver for a word-ladder variant - where each move can change, add, or delete a letter, or rearrange a word - needs to identify every group of dictionary anagrams. The author uses that task to explore how far a Rust implementation can be optimized. The baseline sorts each word’s letters to form a hash-table key and takes 31 ms to process 178,690 Scrabble words, or 173 nanoseconds per word. Replacing per-group vectors with a compact linked-list-like structure cuts the time to 20 ms; packing letter counts into a u128 and switching to a faster hash map brings it to 4.1 ms.

The largest improvement comes from encoding each letter as a distinct prime and identifying a word by the product of its letters’ primes. Since ordinary prime assignments overflow 64 bits for dictionary entries, the author tunes which prime belongs to each letter against the actual word patterns, producing unique, non-overflowing keys for this Scrabble dictionary. That reduces runtime to 2.6 ms. Further gains come from storing words as packed five-bit characters, using two independent multiplication accumulators, and processing a fixed number of character slots to reduce branches and enable compiler vectorization. The final measured time is 1.96 ms, or 10.9 nanoseconds per word - about 15 times faster than the original. The optimization is tailored to this dictionary; it is not presented as a universal anagram-key scheme.