{"article":{"slug":"11-nanoseconds-per-word-ridiculously-over-optimizing-anagrams","title":"11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams","subtitle":null,"summary":"David G. Andersen builds a solver for an anagram-enabled word ladder game and then over-optimizes its anagram indexing in Rust, using collision-free prime-product (Gödel numbering) identifiers, packed inputs and branchless loops to reach about 11 ns per word.","content_type":"blog_post","language":"en","canonical_url":"https://wiredream.com/anagram-fun/","author":{"name":"David G. Andersen","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Wiredream","url":null,"listing_slug":null,"listing":null},"topics":[{"name":"performance","slug":"performance","url":"https://listedarticles.com/topics/performance"},{"name":"rust","slug":"rust","url":"https://listedarticles.com/topics/rust"},{"name":"algorithms","slug":"algorithms","url":"https://listedarticles.com/topics/algorithms"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":2171,"reading_minutes":9,"published_at":"2026-10-27T00:00:00.000Z","added_at":"2026-11-05T05:09:31.629Z","updated_at":"2026-11-05T05:09:31.629Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/11-nanoseconds-per-word-ridiculously-over-optimizing-anagrams","markdown_url":"https://listedarticles.com/articles/11-nanoseconds-per-word-ridiculously-over-optimizing-anagrams.md","example":false,"citation":"David G. Andersen, Wiredream. \"11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams.\" 27 Oct 2026. https://wiredream.com/anagram-fun/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://wiredream.com/anagram-fun/"},"body_markdown":"# [11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams](https://wiredream.com/anagram-fun/)\n\n David G. Andersen  October 27, 2026 \n\nBLOG → BLOT → SLOT → SPOT ↝ POST\n\nA friend recently pointed out a new Word Ladder game variant:\nFind a path of mutations from a start word to an end word,\nwhere mutations can be single letter changes, single letter\ndeletions or additions, or anagramming the word. It annoyed me\n(the paths involving anagrams can be wickedly hard to spot),\nso, naturally, I wrote a solver for it. And when the solver\ntook over a second to run, I of course had to optimize it. Along the way, I\nfound a fun trick for anagram indexing—fitting a collision-free\nprime-product identifier for every word in the dictionary into a\nsingle 64-bit integer—that I hadn't seen before (though the history\nof computing is long and Knuth probably noticed it in 1965).\n\nFor completeness, I should note that what I was interested in\nwas finding all anagrams in a dictionary---if you just want\nto find anagrams of a specific word you can probably get away\nwith a much simpler hash table design! We'll use all of the\nanagrams in the next post talking about solving the whole word\nladder.\n\n## Finding anagrams\n\nThe two usual tricks for finding anagrams are to use\neither a letter-sorted permutation or a letter-count vector\nas a\nunique identifier for the letters in the word in an\norder-independent way:\n\n```\nletter_sort(\"spot\") -> \"opst\"\n```\n\nor\n\n```\nletter_count(\"spot\") -> \"[... o:1, p: 1, s: 1, t:1 ...]\"\n```\n\nand then run through the dictionary and insert items\ninto a hash table based upon their letter count. In python-ish pseudocode:\n\n```\nfor word in dictionary:\n  table[letter_sort(word)] += word\n```\n\nwhich creates a table with entries like:\n\n```\n\"opst\" : [\"spot\", \"post\", \"tops\", \"stop\"]\n```\n\n### Baseline: Sorting strings\n\nBecause I'd been feeling a little, uh, rusty in my coding lately, I\ndecided to implement this all myself in Rust instead of yelling at an LLM\nto do it (this is a leetcode-like problem so it would have done it trivially).\nThat code looked like:\n\n```\nfn anagram_dictionary(words: &[String]) -> HashMap<String, Vec<String>> {\n    let mut anagrams: HashMap<String, Vec<String>> = HashMap::new();\n    for word in words {\n        let key: Vec<u8> = word.bytes().sorted().collect();\n        let key = String::from_utf8(key).expect(\"dictionary words must be ASCII\");\n        anagrams.entry(key).or_default().push(word.clone());\n    }\n    anagrams\n}\n```\n\nUsing the Scrabble(tm) dictionary pre-read into memory, this function\nproduces the anagram dictionary in:\n\n**Result: 31ms (173ns / word)**\n\nThat seems fine. Oh wait, just kidding, that's INSANELY SLOW. The\ndictionary has 178,690 entries in it, which means we're spending 173\nnanoseconds per word to build up this dictionary. In 173 nanoseconds\nyou could execute roughly 4400 instructions on my Macbook Pro M1.\nWho has time to wait for that??\n\n### Eliminating `Vec` allocations\n\nWhen optimizing, one of the first places to be suspicious is\nallocations, and this one has them in droves. Every word results\nin either the allocation of a Vec or an append to a Vec, which\nsometimes needs an allocation. Practically, there are about\n161019 keys in the table, so that's 161k allocations (!!).\nLet's improve those by using a slightly more clever data structure,\nnoting two things:\n\n- With 161k entries in the hash table and only 178k dictionary\n  items, most of those hash table entries will be singletons.\n- We have the original word list stored in memory and it can be\n  indexed by a u32 given its size.\n\nSo we'll do two things: We'll find a way to store singleton\nitems without needing a dynamic-length data structure at all,\nand we'll implement the equivalent of a linked list for appending\nitems to the lists, since they're append-only and we only scan them\nonce at the end. To do this, we'll use a structure like this:\n\n```\n  heads: HashMap::<K, u32>,\n  next: Vec<u32>,\n  word: Vec<u32>\n```\n\nWhere heads is indexed by the anagram-identifying-key (e.g.,\nthe character-sorted string). We'll overload that u32 by\nusing the high bit (we only have 170k or so words) to let\nit represent\n*either* an actual data value (the index of\nan element in the list) OR an index into the next+word arrays.\nThe next array is our linked list - it stores pointers to\nanother entry in the next array. The word array stores the\nassociated data. It looks like this:\n\n![keygroups](https://wiredream.com/keygroups.svg)\n\n**Result: 31ms -> 20ms (112ns / word)**\n\n### Packing letter counts into a `u128`\n\nMuch better, but we can do better yet. The time to sort\nthat string and create a new string allocation is non-trivial\nand we're doing 178k of them. That's going to be another\nbig chunk of nanoseconds.\n\nLet's try a letter count vector instead, and pack it tightly into an integer.\nWith only 26 characters, if we assume that no word has more than 15\nrepetitions of the same character, we could use 4 bits per character\nfor 26 x 4=104 bits. That fits comfortably in a u128, and while\nthat's not tiny, it's at least a nice fixed size 16 byte thing\nwe can use as a fast hash table key.\n\n```\n/// Group words by a u128 holding a 4-bit count of each letter A-Z.\n/// Assumes uppercase A-Z words with no letter repeated more than 15 times.\nfn u128_lettercount(words: &[String]) -> KeyGroups {\n    let items = words.iter().enumerate().map(|(idx, word)| {\n        let mut lettercount = 0u128;\n        for letter in word.bytes() {\n            lettercount += 1u128 << ((letter - b'A') as u32 * 4);\n        }\n        (lettercount, idx as u32)\n    });\n    KeyGroups::new(words.len(), items)\n}\n```\n\n(Note that we've done something else here - we're only returning\nthe list of anagrams, not a full dictionary containing all of the\nwords that don't have anagrams.)\n\nAvoiding the string manipulation and sorting gives a big win:\n\n**Result: 20ms -> 5.6ms (31ns / word)**\n\n### A faster hash table\n\nAt this point, we might ask a question like \"how much does\nthe slow default Rust hash table cost us?\"\n\nSo we'll switch to the [`rustc_hash`](https://crates.io/crates/rustc-hash) `FxHashMap`, which is much faster\nif you don't have to worry about adversarial inputs to your hash table.\n\n**Result: 5.6ms -> 4.1ms (23ns / word)**\n\nThat seems much better. But are we done yet?\n\n### 64-bit Gödel numbering with tuned primes\n\nOf course we're not done!\n\nStoring the letter count as a u128 is also a little slower\nthan necessary, because it'll be split across two 64 bit\nregisters and requires the compiler to carry that addition\nacross them and do twice as much work for equality testing.\nBut if we tried lettercounting in 64 bits, we would only be\nable to store 2 bits, and many words have more than 3 of\nthe same letter (\"MISSISSIPPI\", for example, already has 4 S's).\n\nInstead, we'll use an approach based on\n[Gödel numbering](https://en.wikipedia.org/wiki/G%C3%B6del_numbering):\nwe'll create a small\ntable associating one distinct prime number with each letter, and identify\neach word by the product of the letter-primes. This guarantees a\nunique identifier for each mix of letters. Naively, one might\nassign \"a -> 2, b -> 3, c -> 5\" and so on. But this is a practical\nblog post, and we'd like to fit the result in 64 bits; if\nwe use the naive assignment, we overflow at the 365th word in our\ndictionary, \"ABORTIVENESSES\". And that's only 14 characters long,\nwe have 3157 15-character words as well!\nIf we let it wrap,\nwe'll have just implemented a hash function, and there's no guarantee\nthat two words won't accidentally collide, so then we'd need to add\nsome machinery to check that...\n\nSo here's the trick: Find an optimized assignment of primes to\nletters in the alphabet such that none of the words in our\nScrabble dictionary overflow a 64 bit number. I started out\nthinking about the standard English letter frequency\n(ETAOINSHRDLU, etc.), but that turns out to be a little\nwrong: We don't care much about words like \"the\", we care about\nwords like \"WRONGHEADEDNESS\". So instead, we need to go\nbased on the patterns found in the 3157 15-character words. In particular,\nwhile \"E\" remains assigned to 2, the common \"T\" is assigned 29,\nand we use 3 for \"I\". Our friend \"J\" is assigned 101, since\nthe longest word with two or more J's in it is only 12 characters\nlong: JEJUNENESSES. Looking at that, those E's and N's and S's better\nhave low values, and they do: 2, 19, 17. We could handle 15 N's in\na row in 64 bits still.\n\nTo solve this, I had a small program start with the letter-frequency\nordering (which does a lot better than alphabetical but isn't good enough),\nloop finding the first word that overflowed and switch out some of its primes\nfor lower valued primes. This would have also been fun to throw at a\nsolver.\n\n```\nconst LETTER_PRIMES: [u64; 26] = [\n    5,   // A\n    61,  // B\n    37,  // C\n    53,  // D\n    2,   // E\n    71,  // F\n    47,  // G\n    41,  // H\n    3,   // I\n    101, // J\n    73,  // K\n    23,  // L\n    59,  // M\n    19,  // N\n    7,   // O\n    43,  // P\n    97,  // Q\n    11,  // R\n    17,  // S\n    29,  // T\n    31,  // U\n    89,  // V\n    67,  // W\n    83,  // X\n    13,  // Y\n    79,  // Z\n];\n```\n\nwhich doesn't overflow for any word in the Scrabble dictionary.\nWe've found a collision-free canonical 64-bit identifier for the bag of letters in a\n(Scrabble) word, which looks like this in code:\n\n```\nfn prime_anagramdict(words: &[String]) -> KeyGroups {\n    let items = words.iter().enumerate().map(|(idx, word)| {\n        let mut product = 1u64;\n        for letter in word.bytes() {\n            product = product.wrapping_mul(LETTER_PRIMES[(letter - b'A') as usize]);\n        }\n        (product, idx as u32)\n    });\n    KeyGroups::new::<FxBuildHasher, _>(words.len(), items)\n}\n```\n\nIn this representation, the largest product word is\n\n```\nPSYCHOPATHOLOGY = 17763551150644031915\n```\n\nwhich in log2 is 63.945; it's about 96.2% of the way through the 64 bit\nnumber space. Close, but it fits.\n\n**Result: 4.1ms -> 2.6ms (14.7ns / word — 12x faster than baseline)**\n\n### Using a u128 packed word representation\n\nAnd then there's a final optimization you can do: Instead of reading\nthe dictionary into strings, read them into a packed u128 representation\nusing 5 bits per character, and then add some instruction-level parallelism\nfor our CPU (ILP) by doing the product accumulation using two independent\naccumulators. This u128 representation is useful for speeding up other\nparts of the word ladder solver later. That code looks like this:\n\n```\nfn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {\n    let items = packed_words.iter().enumerate().map(|(idx, &packed)| {\n        let mut even = 1u64;\n        let mut odd = 1u64;\n        let mut rest = packed;\n        while rest != 0 {\n            even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);\n            odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);\n            rest >>= 10;\n        }\n        (even.wrapping_mul(odd), idx as u32)\n    });\n    KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)\n}\n```\n\n**Result: 2.6ms -> 2.3ms (13 ns/word - 13x faster than baseline)**\n\n### Low-level optimizations: branches and auto-vectorization\n\nThis is looking pretty good. The only last optimization I have to add\nis to address some branch mispredictions in that rest != 0 loop. We\ncan instead just treat all words as if they're 16 characters long and\nignore the 0's at the end by mapping them to 1 in our primes table\n(i.e., they have no effect on the product). Using a fixed length of 16\nalso permits more auto-vectorization by our friendly compiler.\nTo support that, we also separate the computation of the prime product\nfrom the insertion into the hash table, allowing more ILP from our\nnow-vectorized multiplication loop.\n\nThat code ends up looking like this:\n\n```\nfn packed_prime_product(packed: u128) -> u64 {\n    debug_assert!(packed >> 80 == 0, \"word longer than 16 letters\");\n    let mut even = 1u64;\n    let mut odd = 1u64;\n    let mut rest = packed;\n    for _ in 0..8 {\n        even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);\n        odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);\n        rest >>= 10;\n    }\n    even.wrapping_mul(odd)\n}   \n\nfn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {\n    let products: Vec<u64> = packed_words.iter().map(|&p| packed_prime_product(p)).collect();\n    let items = products.iter().enumerate().map(|(idx, &product)| (product, idx as u32));\n    KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)\n}\n```\n\n**Result: 2.3 ms -> 1.96ms (10.9ns/word, 15x faster than baseline)**\n\nWe're finally pretty close to what I think a single core on my machine\ncan get without explicit vectorization. That 1.96ms is about 1.23ns per\nbyte, which could theoretically be about 3.2 x 8 x 1.23 = 31 instructions\n(but realistically fewer), which doesn't leave a *ton* of\nroom for optimization---though I could be wrong! There's some space\nin there for an even faster hash table implementation but I'd rather\nstick with common, off-the-shelf things there.\n\n### Summary of optimizations\n\n| Step | Optimization | Total Time | Time / Word | Speedup vs. Baseline |\n| --- | --- | --- | --- | --- |\n| 0 | Baseline (`HashMap<String, Vec<String>>`, sorted string keys) | 31.0 ms | 173 ns | 1.0x |\n| 1 | `KeyGroups` flat arrays & inline singletons | 20.0 ms | 112 ns | 1.6x |\n| 2 | 4-bit letter counts packed into `u128` | 5.6 ms | 31 ns | 5.5x |\n| 3 | Switch to `rustc_hash::FxHashMap` | 4.1 ms | 23 ns | 7.6x |\n| 4 | 64-bit Gödel numbering (corpus-tuned prime products) | 2.6 ms | 14.7 ns | 11.9x |\n| 5 | 5-bit packed `u128` input words + dual-accumulator ILP | 2.3 ms | 13.0 ns | 13.5x |\n| 6 | Branchless fixed-length loop + auto-vectorized product pass | **1.96 ms** | **10.9 ns** | **15.8x** |\n\nIn the next post I'll show how we solve the entire word ladder problem,\nusing the anagrams we've found as a part of it.\n","body_html":"<h1 id=\"11-nanoseconds-per-word-ridiculously-over-optimizing-anagrams\"><a href=\"https://wiredream.com/anagram-fun/\" rel=\"nofollow ugc noopener\">11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams</a></h1>\n<p> David G. Andersen  October 27, 2026 </p>\n<p>BLOG → BLOT → SLOT → SPOT ↝ POST</p>\n<p>A friend recently pointed out a new Word Ladder game variant:\nFind a path of mutations from a start word to an end word,\nwhere mutations can be single letter changes, single letter\ndeletions or additions, or anagramming the word. It annoyed me\n(the paths involving anagrams can be wickedly hard to spot),\nso, naturally, I wrote a solver for it. And when the solver\ntook over a second to run, I of course had to optimize it. Along the way, I\nfound a fun trick for anagram indexing—fitting a collision-free\nprime-product identifier for every word in the dictionary into a\nsingle 64-bit integer—that I hadn&#39;t seen before (though the history\nof computing is long and Knuth probably noticed it in 1965).</p>\n<p>For completeness, I should note that what I was interested in\nwas finding all anagrams in a dictionary---if you just want\nto find anagrams of a specific word you can probably get away\nwith a much simpler hash table design! We&#39;ll use all of the\nanagrams in the next post talking about solving the whole word\nladder.</p>\n<h2 id=\"finding-anagrams\">Finding anagrams</h2>\n<p>The two usual tricks for finding anagrams are to use\neither a letter-sorted permutation or a letter-count vector\nas a\nunique identifier for the letters in the word in an\norder-independent way:</p>\n<pre><code>letter_sort(&quot;spot&quot;) -&gt; &quot;opst&quot;</code></pre>\n<p>or</p>\n<pre><code>letter_count(&quot;spot&quot;) -&gt; &quot;[... o:1, p: 1, s: 1, t:1 ...]&quot;</code></pre>\n<p>and then run through the dictionary and insert items\ninto a hash table based upon their letter count. In python-ish pseudocode:</p>\n<pre><code>for word in dictionary:\n  table[letter_sort(word)] += word</code></pre>\n<p>which creates a table with entries like:</p>\n<pre><code>&quot;opst&quot; : [&quot;spot&quot;, &quot;post&quot;, &quot;tops&quot;, &quot;stop&quot;]</code></pre>\n<h3 id=\"baseline-sorting-strings\">Baseline: Sorting strings</h3>\n<p>Because I&#39;d been feeling a little, uh, rusty in my coding lately, I\ndecided to implement this all myself in Rust instead of yelling at an LLM\nto do it (this is a leetcode-like problem so it would have done it trivially).\nThat code looked like:</p>\n<pre><code>fn anagram_dictionary(words: &amp;[String]) -&gt; HashMap&lt;String, Vec&lt;String&gt;&gt; {\n    let mut anagrams: HashMap&lt;String, Vec&lt;String&gt;&gt; = HashMap::new();\n    for word in words {\n        let key: Vec&lt;u8&gt; = word.bytes().sorted().collect();\n        let key = String::from_utf8(key).expect(&quot;dictionary words must be ASCII&quot;);\n        anagrams.entry(key).or_default().push(word.clone());\n    }\n    anagrams\n}</code></pre>\n<p>Using the Scrabble(tm) dictionary pre-read into memory, this function\nproduces the anagram dictionary in:</p>\n<p><strong>Result: 31ms (173ns / word)</strong></p>\n<p>That seems fine. Oh wait, just kidding, that&#39;s INSANELY SLOW. The\ndictionary has 178,690 entries in it, which means we&#39;re spending 173\nnanoseconds per word to build up this dictionary. In 173 nanoseconds\nyou could execute roughly 4400 instructions on my Macbook Pro M1.\nWho has time to wait for that??</p>\n<h3 id=\"eliminating-vec-allocations\">Eliminating <code>Vec</code> allocations</h3>\n<p>When optimizing, one of the first places to be suspicious is\nallocations, and this one has them in droves. Every word results\nin either the allocation of a Vec or an append to a Vec, which\nsometimes needs an allocation. Practically, there are about\n161019 keys in the table, so that&#39;s 161k allocations (!!).\nLet&#39;s improve those by using a slightly more clever data structure,\nnoting two things:</p>\n<ul><li><p>With 161k entries in the hash table and only 178k dictionary</p><p>items, most of those hash table entries will be singletons.</p></li><li><p>We have the original word list stored in memory and it can be</p><p>indexed by a u32 given its size.</p></li></ul>\n<p>So we&#39;ll do two things: We&#39;ll find a way to store singleton\nitems without needing a dynamic-length data structure at all,\nand we&#39;ll implement the equivalent of a linked list for appending\nitems to the lists, since they&#39;re append-only and we only scan them\nonce at the end. To do this, we&#39;ll use a structure like this:</p>\n<pre><code>  heads: HashMap::&lt;K, u32&gt;,\n  next: Vec&lt;u32&gt;,\n  word: Vec&lt;u32&gt;</code></pre>\n<p>Where heads is indexed by the anagram-identifying-key (e.g.,\nthe character-sorted string). We&#39;ll overload that u32 by\nusing the high bit (we only have 170k or so words) to let\nit represent\n<em>either</em> an actual data value (the index of\nan element in the list) OR an index into the next+word arrays.\nThe next array is our linked list - it stores pointers to\nanother entry in the next array. The word array stores the\nassociated data. It looks like this:</p>\n<figure><img src=\"https://wiredream.com/keygroups.svg\" alt=\"keygroups\" loading=\"lazy\" decoding=\"async\" referrerpolicy=\"no-referrer\" /></figure>\n<p><strong>Result: 31ms -&gt; 20ms (112ns / word)</strong></p>\n<h3 id=\"packing-letter-counts-into-a-u128\">Packing letter counts into a <code>u128</code></h3>\n<p>Much better, but we can do better yet. The time to sort\nthat string and create a new string allocation is non-trivial\nand we&#39;re doing 178k of them. That&#39;s going to be another\nbig chunk of nanoseconds.</p>\n<p>Let&#39;s try a letter count vector instead, and pack it tightly into an integer.\nWith only 26 characters, if we assume that no word has more than 15\nrepetitions of the same character, we could use 4 bits per character\nfor 26 x 4=104 bits. That fits comfortably in a u128, and while\nthat&#39;s not tiny, it&#39;s at least a nice fixed size 16 byte thing\nwe can use as a fast hash table key.</p>\n<pre><code>/// Group words by a u128 holding a 4-bit count of each letter A-Z.\n/// Assumes uppercase A-Z words with no letter repeated more than 15 times.\nfn u128_lettercount(words: &amp;[String]) -&gt; KeyGroups {\n    let items = words.iter().enumerate().map(|(idx, word)| {\n        let mut lettercount = 0u128;\n        for letter in word.bytes() {\n            lettercount += 1u128 &lt;&lt; ((letter - b&#39;A&#39;) as u32 * 4);\n        }\n        (lettercount, idx as u32)\n    });\n    KeyGroups::new(words.len(), items)\n}</code></pre>\n<p>(Note that we&#39;ve done something else here - we&#39;re only returning\nthe list of anagrams, not a full dictionary containing all of the\nwords that don&#39;t have anagrams.)</p>\n<p>Avoiding the string manipulation and sorting gives a big win:</p>\n<p><strong>Result: 20ms -&gt; 5.6ms (31ns / word)</strong></p>\n<h3 id=\"a-faster-hash-table\">A faster hash table</h3>\n<p>At this point, we might ask a question like &quot;how much does\nthe slow default Rust hash table cost us?&quot;</p>\n<p>So we&#39;ll switch to the <a href=\"https://crates.io/crates/rustc-hash\" rel=\"nofollow ugc noopener\"><code>rustc_hash</code></a> <code>FxHashMap</code>, which is much faster\nif you don&#39;t have to worry about adversarial inputs to your hash table.</p>\n<p><strong>Result: 5.6ms -&gt; 4.1ms (23ns / word)</strong></p>\n<p>That seems much better. But are we done yet?</p>\n<h3 id=\"64-bit-godel-numbering-with-tuned-primes\">64-bit Gödel numbering with tuned primes</h3>\n<p>Of course we&#39;re not done!</p>\n<p>Storing the letter count as a u128 is also a little slower\nthan necessary, because it&#39;ll be split across two 64 bit\nregisters and requires the compiler to carry that addition\nacross them and do twice as much work for equality testing.\nBut if we tried lettercounting in 64 bits, we would only be\nable to store 2 bits, and many words have more than 3 of\nthe same letter (&quot;MISSISSIPPI&quot;, for example, already has 4 S&#39;s).</p>\n<p>Instead, we&#39;ll use an approach based on\n<a href=\"https://en.wikipedia.org/wiki/G%C3%B6del_numbering\" rel=\"nofollow ugc noopener\">Gödel numbering</a>:\nwe&#39;ll create a small\ntable associating one distinct prime number with each letter, and identify\neach word by the product of the letter-primes. This guarantees a\nunique identifier for each mix of letters. Naively, one might\nassign &quot;a -&gt; 2, b -&gt; 3, c -&gt; 5&quot; and so on. But this is a practical\nblog post, and we&#39;d like to fit the result in 64 bits; if\nwe use the naive assignment, we overflow at the 365th word in our\ndictionary, &quot;ABORTIVENESSES&quot;. And that&#39;s only 14 characters long,\nwe have 3157 15-character words as well!\nIf we let it wrap,\nwe&#39;ll have just implemented a hash function, and there&#39;s no guarantee\nthat two words won&#39;t accidentally collide, so then we&#39;d need to add\nsome machinery to check that...</p>\n<p>So here&#39;s the trick: Find an optimized assignment of primes to\nletters in the alphabet such that none of the words in our\nScrabble dictionary overflow a 64 bit number. I started out\nthinking about the standard English letter frequency\n(ETAOINSHRDLU, etc.), but that turns out to be a little\nwrong: We don&#39;t care much about words like &quot;the&quot;, we care about\nwords like &quot;WRONGHEADEDNESS&quot;. So instead, we need to go\nbased on the patterns found in the 3157 15-character words. In particular,\nwhile &quot;E&quot; remains assigned to 2, the common &quot;T&quot; is assigned 29,\nand we use 3 for &quot;I&quot;. Our friend &quot;J&quot; is assigned 101, since\nthe longest word with two or more J&#39;s in it is only 12 characters\nlong: JEJUNENESSES. Looking at that, those E&#39;s and N&#39;s and S&#39;s better\nhave low values, and they do: 2, 19, 17. We could handle 15 N&#39;s in\na row in 64 bits still.</p>\n<p>To solve this, I had a small program start with the letter-frequency\nordering (which does a lot better than alphabetical but isn&#39;t good enough),\nloop finding the first word that overflowed and switch out some of its primes\nfor lower valued primes. This would have also been fun to throw at a\nsolver.</p>\n<pre><code>const LETTER_PRIMES: [u64; 26] = [\n    5,   // A\n    61,  // B\n    37,  // C\n    53,  // D\n    2,   // E\n    71,  // F\n    47,  // G\n    41,  // H\n    3,   // I\n    101, // J\n    73,  // K\n    23,  // L\n    59,  // M\n    19,  // N\n    7,   // O\n    43,  // P\n    97,  // Q\n    11,  // R\n    17,  // S\n    29,  // T\n    31,  // U\n    89,  // V\n    67,  // W\n    83,  // X\n    13,  // Y\n    79,  // Z\n];</code></pre>\n<p>which doesn&#39;t overflow for any word in the Scrabble dictionary.\nWe&#39;ve found a collision-free canonical 64-bit identifier for the bag of letters in a\n(Scrabble) word, which looks like this in code:</p>\n<pre><code>fn prime_anagramdict(words: &amp;[String]) -&gt; KeyGroups {\n    let items = words.iter().enumerate().map(|(idx, word)| {\n        let mut product = 1u64;\n        for letter in word.bytes() {\n            product = product.wrapping_mul(LETTER_PRIMES[(letter - b&#39;A&#39;) as usize]);\n        }\n        (product, idx as u32)\n    });\n    KeyGroups::new::&lt;FxBuildHasher, _&gt;(words.len(), items)\n}</code></pre>\n<p>In this representation, the largest product word is</p>\n<pre><code>PSYCHOPATHOLOGY = 17763551150644031915</code></pre>\n<p>which in log2 is 63.945; it&#39;s about 96.2% of the way through the 64 bit\nnumber space. Close, but it fits.</p>\n<p><strong>Result: 4.1ms -&gt; 2.6ms (14.7ns / word — 12x faster than baseline)</strong></p>\n<h3 id=\"using-a-u128-packed-word-representation\">Using a u128 packed word representation</h3>\n<p>And then there&#39;s a final optimization you can do: Instead of reading\nthe dictionary into strings, read them into a packed u128 representation\nusing 5 bits per character, and then add some instruction-level parallelism\nfor our CPU (ILP) by doing the product accumulation using two independent\naccumulators. This u128 representation is useful for speeding up other\nparts of the word ladder solver later. That code looks like this:</p>\n<pre><code>fn prime_anagramdict_packed(packed_words: &amp;[u128]) -&gt; KeyGroups {\n    let items = packed_words.iter().enumerate().map(|(idx, &amp;packed)| {\n        let mut even = 1u64;\n        let mut odd = 1u64;\n        let mut rest = packed;\n        while rest != 0 {\n            even = even.wrapping_mul(PACKED_PRIMES[(rest &amp; 0x1f) as usize]);\n            odd = odd.wrapping_mul(PACKED_PRIMES[((rest &gt;&gt; 5) &amp; 0x1f) as usize]);\n            rest &gt;&gt;= 10;\n        }\n        (even.wrapping_mul(odd), idx as u32)\n    });\n    KeyGroups::new::&lt;FxBuildHasher, _&gt;(packed_words.len(), items)\n}</code></pre>\n<p><strong>Result: 2.6ms -&gt; 2.3ms (13 ns/word - 13x faster than baseline)</strong></p>\n<h3 id=\"low-level-optimizations-branches-and-auto-vectorization\">Low-level optimizations: branches and auto-vectorization</h3>\n<p>This is looking pretty good. The only last optimization I have to add\nis to address some branch mispredictions in that rest != 0 loop. We\ncan instead just treat all words as if they&#39;re 16 characters long and\nignore the 0&#39;s at the end by mapping them to 1 in our primes table\n(i.e., they have no effect on the product). Using a fixed length of 16\nalso permits more auto-vectorization by our friendly compiler.\nTo support that, we also separate the computation of the prime product\nfrom the insertion into the hash table, allowing more ILP from our\nnow-vectorized multiplication loop.</p>\n<p>That code ends up looking like this:</p>\n<pre><code>fn packed_prime_product(packed: u128) -&gt; u64 {\n    debug_assert!(packed &gt;&gt; 80 == 0, &quot;word longer than 16 letters&quot;);\n    let mut even = 1u64;\n    let mut odd = 1u64;\n    let mut rest = packed;\n    for _ in 0..8 {\n        even = even.wrapping_mul(PACKED_PRIMES[(rest &amp; 0x1f) as usize]);\n        odd = odd.wrapping_mul(PACKED_PRIMES[((rest &gt;&gt; 5) &amp; 0x1f) as usize]);\n        rest &gt;&gt;= 10;\n    }\n    even.wrapping_mul(odd)\n}   \n\nfn prime_anagramdict_packed(packed_words: &amp;[u128]) -&gt; KeyGroups {\n    let products: Vec&lt;u64&gt; = packed_words.iter().map(|&amp;p| packed_prime_product(p)).collect();\n    let items = products.iter().enumerate().map(|(idx, &amp;product)| (product, idx as u32));\n    KeyGroups::new::&lt;FxBuildHasher, _&gt;(packed_words.len(), items)\n}</code></pre>\n<p><strong>Result: 2.3 ms -&gt; 1.96ms (10.9ns/word, 15x faster than baseline)</strong></p>\n<p>We&#39;re finally pretty close to what I think a single core on my machine\ncan get without explicit vectorization. That 1.96ms is about 1.23ns per\nbyte, which could theoretically be about 3.2 x 8 x 1.23 = 31 instructions\n(but realistically fewer), which doesn&#39;t leave a <em>ton</em> of\nroom for optimization---though I could be wrong! There&#39;s some space\nin there for an even faster hash table implementation but I&#39;d rather\nstick with common, off-the-shelf things there.</p>\n<h3 id=\"summary-of-optimizations\">Summary of optimizations</h3>\n<div class=\"table-wrap\"><table><thead><tr><th>Step</th><th>Optimization</th><th>Total Time</th><th>Time / Word</th><th>Speedup vs. Baseline</th></tr></thead><tbody><tr><td>0</td><td>Baseline (<code>HashMap&lt;String, Vec&lt;String&gt;&gt;</code>, sorted string keys)</td><td>31.0 ms</td><td>173 ns</td><td>1.0x</td></tr><tr><td>1</td><td><code>KeyGroups</code> flat arrays &amp; inline singletons</td><td>20.0 ms</td><td>112 ns</td><td>1.6x</td></tr><tr><td>2</td><td>4-bit letter counts packed into <code>u128</code></td><td>5.6 ms</td><td>31 ns</td><td>5.5x</td></tr><tr><td>3</td><td>Switch to <code>rustc_hash::FxHashMap</code></td><td>4.1 ms</td><td>23 ns</td><td>7.6x</td></tr><tr><td>4</td><td>64-bit Gödel numbering (corpus-tuned prime products)</td><td>2.6 ms</td><td>14.7 ns</td><td>11.9x</td></tr><tr><td>5</td><td>5-bit packed <code>u128</code> input words + dual-accumulator ILP</td><td>2.3 ms</td><td>13.0 ns</td><td>13.5x</td></tr><tr><td>6</td><td>Branchless fixed-length loop + auto-vectorized product pass</td><td><strong>1.96 ms</strong></td><td><strong>10.9 ns</strong></td><td><strong>15.8x</strong></td></tr></tbody></table></div>\n<p>In the next post I&#39;ll show how we solve the entire word ladder problem,\nusing the anagrams we&#39;ve found as a part of it.</p>","headings":[{"level":1,"text":"11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams","id":"11-nanoseconds-per-word-ridiculously-over-optimizing-anagrams"},{"level":2,"text":"Finding anagrams","id":"finding-anagrams"},{"level":3,"text":"Baseline: Sorting strings","id":"baseline-sorting-strings"},{"level":3,"text":"Eliminating Vec allocations","id":"eliminating-vec-allocations"},{"level":3,"text":"Packing letter counts into a u128","id":"packing-letter-counts-into-a-u128"},{"level":3,"text":"A faster hash table","id":"a-faster-hash-table"},{"level":3,"text":"64-bit Gödel numbering with tuned primes","id":"64-bit-godel-numbering-with-tuned-primes"},{"level":3,"text":"Using a u128 packed word representation","id":"using-a-u128-packed-word-representation"},{"level":3,"text":"Low-level optimizations: branches and auto-vectorization","id":"low-level-optimizations-branches-and-auto-vectorization"},{"level":3,"text":"Summary of optimizations","id":"summary-of-optimizations"}]}}