每个词 11 纳秒：把变位词索引优化到极致
来源：wiredream.com — 2026-10-27
📋 概述
作者为一个「变位也算一步」的单词接龙游戏写了求解器，嫌一秒太慢，于是把变位词索引从 173 纳秒每词压到 10.9 纳秒每词，快 15.8 倍。路径很干净：用扁平数组加内联单例去掉 16 万次 Vec 分配、把 26 个字母的计数按 4 位塞进 u128、换成 FxHashMap、再用为语料调过的质数分配做 64 位哥德尔编号，最后用 5 位打包的 u128 单词表加上双累加器指令级并行和无分支循环，让编译器自动向量化。
🔑 核心要点
- 基线是 HashMap 加排序字符串做键：31 毫秒、每词 173 纳秒。
- 第一刀砍分配：扁平数组加内联单例，16 万次分配消失，降到每词 112 纳秒。
- 把字母计数按 4 位压进 u128，省掉排序与字符串构造，降到每词 31 纳秒。
- 换 FxHashMap 再降到 23 纳秒，然后上质数乘积：为 Scrabble 词典调过的 26 个质数保证 64 位不溢出。
- 最长的乘积是 PSYCHOPATHOLOGY，用到 63.945 位，占满 64 位空间的 96.2%。
- 最后用 5 位打包单词、双累加器并行、无分支定长循环，落到每词 10.9 纳秒。
💡 金句
在我的 M1 MacBook Pro 上，173 纳秒大约能执行 4400 条指令。谁有空等这个？
👍 0
👎 0
← 返回 Lobsters 首页