11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams

本文为原文前 6,000 字符的节选翻译，完整内容请查看原文。

11 nanoseconds per word: Ridiculously Over-Optimizing Anagrams David G. Andersen October 27, 2026 BLOG → BLOT → SLOT → SPOT ↝ POST A friend recently pointed out a new Word Ladder game variant: Find a path of mutations from a start word to an end word, where mutations can be single letter changes, single letter deletions or additions, or anagramming the word. It annoyed me (the paths involving anagrams can be wickedly hard to spot), so, naturally, I wrote a solver for it. And when the solver took over a second to run, I of course had to optimize it. Along the way, I found a fun trick for anagram indexing—fitting a collision-free prime-product identifier for every word in the dictionary into a single 64-bit integer—that I hadn’t seen before (though the history of computing is long and Knuth probably noticed it in 1965). For completeness, I should note that what I was interested in was finding all anagrams in a dictionary---if you just want to find anagrams of a specific word you can probably get away with a much simpler hash table design! We’ll use all of the anagrams in the next post talking about solving the whole word ladder.

每词 11 纳秒：对变位词进行荒谬的过度优化。David G. Andersen，2026 年 10 月 27 日。BLOG → BLOT → SLOT → SPOT ↝ POST。一位朋友最近指出了一种新的“词梯”游戏变体：找到一条从起始单词到结束单词的变异路径，其中变异可以是单个字母的更改、单个字母的删除或添加，或者是单词的变位。这让我很恼火（涉及变位词的路径可能非常难以发现），所以，自然地，我为它写了一个求解器。当求解器的运行时间超过一秒时，我当然必须对其进行优化。在此过程中，我发现了一个有趣的变位词索引技巧——将字典中每个单词的无碰撞素数乘积标识符放入单个 64 位整数中——这是我以前没见过的（尽管计算历史悠久，Knuth 可能在 1965 年就注意到了这一点）。为了完整起见，我应该指出，我感兴趣的是找到字典中的所有变位词——如果你只是想找到特定单词的变位词，你可能可以使用更简单的哈希表设计！我们将在下一篇文章中讨论解决整个词梯问题时使用所有这些变位词。

Finding anagrams The two usual tricks for finding anagrams are to use either a letter-sorted permutation or a letter-count vector as a unique identifier for the letters in the word in an order-independent way: letter_sort(“spot”) -> “opst” or letter_count(“spot”) -> ”[… o:1, p: 1, s: 1, t:1 …]” and then run through the dictionary and insert items into a hash table based upon their letter count. In python-ish pseudocode: for word in dictionary: table[letter_sort(word)] += word which creates a table with entries like: “opst” : [“spot”, “post”, “tops”, “stop”]

寻找变位词。寻找变位词的两种常用技巧是使用字母排序后的排列或字母计数向量，作为单词中字母的唯一标识符，以一种与顺序无关的方式：letter_sort(“spot”) -> “opst” 或 letter_count(“spot”) -> ”[… o:1, p: 1, s: 1, t:1 …]”，然后遍历字典并根据它们的字母计数将项目插入哈希表。用类似 Python 的伪代码表示：for word in dictionary: table[letter_sort(word)] += word，这将创建一个包含如下条目的表：“opst” : [“spot”, “post”, “tops”, “stop”]。

Baseline: Sorting strings Because I’d been feeling a little, uh, rusty in my coding lately, I decided to implement this all myself in Rust instead of yelling at an LLM to do it (this is a leetcode-like problem so it would have done it trivially). That code looked like: fn anagram_dictionary(words: &[String]) -> HashMap<String, Vec> { let mut anagrams: HashMap<String, Vec> = HashMap::new(); for word in words { let key: Vec = word.bytes().sorted().collect(); let key = String::from_utf8(key).expect(“dictionary words must be ASCII”); anagrams.entry(key).or_default().push(word.clone()); } anagrams } Using the Scrabble(tm) dictionary pre-read into memory, this function produces the anagram dictionary in: Result: 31ms (173ns / word) That seems fine. Oh wait, just kidding, that’s INSANELY SLOW. The dictionary has 178,690 entries in it, which means we’re spending 173 nanoseconds per word to build up this dictionary. In 173 nanoseconds you could execute roughly 4400 instructions on my Macbook Pro M1. Who has time to wait for that??

基准：排序字符串。因为我最近感觉自己的编码有点生疏，所以我决定用 Rust 自己实现这一切，而不是让 LLM 来做（这是一个类似 LeetCode 的问题，所以它会轻而易举地完成）。代码如下：fn anagram_dictionary(words: &[String]) -> HashMap<String, Vec> { let mut anagrams: HashMap<String, Vec> = HashMap::new(); for word in words { let key: Vec = word.bytes().sorted().collect(); let key = String::from_utf8(key).expect(“dictionary words must be ASCII”); anagrams.entry(key).or_default().push(word.clone()); } anagrams }。使用预读入内存的 Scrabble(tm) 字典，此函数生成变位词字典的时间为：结果：31ms（每词 173ns）。这看起来不错。等等，开个玩笑，这慢得离谱。字典中有 178,690 个条目，这意味着我们花费了每词 173 纳秒来构建这个字典。在 173 纳秒内，你可以在我的 Macbook Pro M1 上执行大约 4400 条指令。谁有时间等这个？？

Eliminating Vec allocations When optimizing, one of the first places to be suspicious is allocations, and this one has them in droves. Every word results in either the allocation of a Vec or an append to a Vec, which sometimes needs an allocation. Practically, there are about 161019 keys in the table, so that’s 161k allocations (!!). Let’s improve those by using a slightly more clever data structure, noting two things: With 161k entries in the hash table and only 178k dictionary items, most of those hash table entries will be singletons. We have the original word list stored in memory and it can be indexed by a u32 given its size. So we’ll do two things: We’ll find a way to store singleton items without needing a dynamic-length data structure at all, and we’ll implement the equivalent of a linked list for appending items to the lists, since they’re append-only and we only scan them once at the end. To do this, we’ll use a structure like this: heads: HashMap::<K, u32>, next: Vec, word: Vec Where heads is indexed by the anagram-identifying-key (e.g., the character-sorted string). We’ll overload that u32 by using the high bit (we only have 170k or so words) to let it represent either an actual data value (the index of an element in the list) OR an index into the next+word arrays. The next array is our linked list - it stores pointers to another entry in the next array. The word array stores the associated data. It looks like this: Result: 31ms -> 20ms (112ns / word)

消除 Vec 分配。在进行优化时，首先要怀疑的地方之一就是内存分配，而这个程序中充斥着分配。每个单词都会导致 Vec 的分配或对 Vec 的追加（有时需要分配）。实际上，表中大约有 161,019 个键，所以那是 16.1 万次分配（！！）。让我们通过使用稍微聪明一点的数据结构来改进它们，注意两点：哈希表中有 16.1 万个条目，而字典项只有 17.8 万个，大多数哈希表条目将是单例。我们将原始单词列表存储在内存中，并且鉴于其大小，它可以通过 u32 进行索引。所以我们将做两件事：我们将找到一种存储单例项的方法，而根本不需要动态长度的数据结构，并且我们将实现相当于链表的功能来将项目追加到列表中，因为它们是只追加的，而且我们只在最后扫描它们一次。为此，我们将使用如下结构：heads: HashMap::<K, u32>, next: Vec, word: Vec，其中 heads 由变位词识别键（例如，字符排序后的字符串）索引。我们将通过使用高位（我们只有 17 万左右的单词）来重载该 u32，使其既可以表示实际数据值（列表中元素的索引），也可以表示指向 next+word 数组的索引。next 数组是我们的链表——它存储指向 next 数组中另一个条目的指针。word 数组存储相关数据。它看起来像这样：结果：31ms -> 20ms（每词 112ns）。

Packing letter counts into a u128 Much better, but we can do better yet. The time to sort that string and create a new string allocation is non-trivial and we’re doing 178k of them. That’s going to be another big chunk of nanoseconds. Let’s try a letter count vector instead, and pack it tightly into an integer. With only 26 characters, if we assume that no word has more than 15 repetitions of the same character, we could use 4 bits per character for 26 x 4=104 bits. That fits comfortably in a u128, and while that’s not tiny, it’s at least a nice fixed size 16 byte thing we can use as a fast hash table key. /// Group words by a u128 holding a 4-bit count of each letter A-Z. /// Assumes uppercase A-Z words with no letter repeated more than 15 times. fn u128_lettercount(words: &[String]) -> KeyGroups { let items = words.iter().enumerate().map(|(idx, word)| { let mut lettercount = 0u128; for letter in word.bytes() { lettercount += 1u128 << ((letter - b’A’) as u32 * 4); } (lettercount, idx as u32) }); KeyGroups::new(words.len(), items) } (Note that we’ve done something else here - we’re only returning the list of anagrams, not a full dictionary containing all of the words that don’t have anagrams.) Avoiding the string manipulation and sorting gives a big win: Result: 20ms -> 5.6ms (31ns / word)

将字母计数打包到 u128 中。好多了，但我们还可以做得更好。排序字符串并创建新字符串分配的时间是不容忽视的，而且我们正在进行 17.8 万次这样的操作。那将是另一大块纳秒。让我们尝试改用字母计数向量，并将其紧凑地打包到一个整数中。只有 26 个字符，如果我们假设没有单词包含超过 15 次相同的字符重复，我们可以为每个字符使用 4 位，即 26 x 4 = 104 位。这可以舒适地放入 u128 中，虽然它不算小，但至少是一个很好的固定大小的 16 字节对象，我们可以将其用作快速哈希表键。/// 按 u128 对单词进行分组，其中包含每个字母 A-Z 的 4 位计数。/// 假设单词为大写 A-Z，且没有字母重复超过 15 次。fn u128_lettercount(words: &[String]) -> KeyGroups { let items = words.iter().enumerate().map(|(idx, word)| { let mut lettercount = 0u128; for letter in word.bytes() { lettercount += 1u128 << ((letter - b’A’) as u32 * 4); } (lettercount, idx as u32) }); KeyGroups::new(words.len(), items) }（请注意，我们在这里做了另一件事——我们只返回变位词列表，而不是包含所有没有变位词的单词的完整字典。）避免字符串操作和排序带来了巨大的胜利：结果：20ms -> 5.6ms（每词 31ns）。

A faster hash table At this point, we might ask a question like “how much does the slow default Rust hash table cost us?” So we’ll switch to the rustc_hash FxHashMap, which is much faster if you don’t have to worry about adversarial inputs to your hash table. Result: 5.6ms -> 4.1ms (23ns / word) That seems much better. But are we done yet? 64-bit Gödel numbering with tuned primes Of course we’re not done! Storing the

更快的哈希表。此时，我们可能会问一个问题，比如“缓慢的默认 Rust 哈希表让我们付出了多少代价？”所以我们将切换到 rustc_hash FxHashMap，如果你不必担心哈希表的对抗性输入，它会快得多。结果：5.6ms -> 4.1ms（每词 23ns）。这看起来好多了。但我们完成了吗？使用调整后的素数进行 64 位哥德尔编码。当然我们还没完成！存储……