qingjian/docs/notes/performance.md

性能：做过什么、怎么找到的、为什么这么改

输入法的性能预算只有一条：每一键的候选必须在 10 ms 内算完（用户敲键间隔 100 ms 上下，超过 30 ms 就能感觉到黏）， 启动尽量 1 s 内。联想走后台线程不算在内。这篇按时间顺序记每一轮优化：起因、怎么定位、改了什么、数字前后对比， 以及走过的弯路。数字都是 release 构建、开发测试词库（89 万条）、300 万对 bigram 的 M 系列 Mac 上量的。

怎么量

• cargo run --release -p qingjian-cli -- <拼音> 打每个阶段的耗时：parse（切分 + 纠错）、lookup（词库查询）、 rank（排序 + 各类插入，整句转换算在这里）、translate（释义查表）。
• --typing 逐键模式（2026-09-05 加）：把 kaifa 当 k、ka、kai、kaif、kaifa 五次按键，每个前缀查一次并标注译文， 一行一键。这才是输入法的真实工作量，一次性查整段会漏掉「首键最贵」「简拼越敲越贵」这类问题。
• 启动日志带各数据文件的加载耗时（加载完成 dict_ms=… glossary_ms=…、语言模型已加载 load_ms=…、Engine 就绪 total_ms=…）。
• 定位热点靠临时打点：在怀疑的函数里 Instant::now() 累加、eprintln! 打出来，看完删掉。机器上没有装 profiler， 而且 IME 进程也不方便挂 profiler；打点够用，前提是先打点再改（见下面的弯路）。
• 测试性能改动不改行为：词库查询有一份线性扫描版只在测试里用，随机词库 + 随机模式与收窄版对拍，结果集必须相同； 排序 / 整句的改动靠现有单元测试和 CLI 上一组固定输入回归。

第一轮：内存（2026-09-03）

起因：词库从几十条样例换成 89 万条真实数据，进程 RSS 480 MB。每条词一个 String + 一个 Vec<String> 音节， 分配器开销和指针比数据本身还大。

改法：arena + 偏移。所有词文本首尾相接放一个 String（texts），所有拼音键放另一个（keys，同音词共用一个键）， 索引是两个 Vec 的定长结构：KeyIndex { key_start: u32, key_len: u16, first_slot: u32, slot_count: u32 }、 Slot { text_start: u32, text_len: u16, frequency: u32 }。查出来的 Match 借用 arena 里的 &str，不拷贝。

结果：RSS 480 MB → 148 MB。这个布局也是后来二进制化（.qj 容器）能直接 mmap 的前提：内存里就是几段连续数组。

第二轮：查词（2026-09-04）

起因：单字母 k 一键 30 ms，全简拼 zhgdoima 70 ms，长全拼 20 ms。当时 lookup_pattern 是对整个索引线性扫、 逐键 split 音节比对。

观察：键按字节序排好，「以某段前缀开头的键」一定是连续区间。所以查词可以逐音节位置二分收窄：

• 完整音节：区间里直接二分到 前缀 + 音节 + 空格（kai ），一步到位。
• 简拼位置（k 是前缀）：区间里出现的不同音节是一块一块的（ka …、kai …、kan …），每块只看第一条键就能算出这块的 子区间，跳着扫，代价与实际出现的音节组合数成正比，与首音节下有多少键无关。
• 区间收到 48 条以内改成线性比对：小区间再二分加递归反而贵，全简拼时小块极多。
• lookup_exact（只要音节数正好等于模式长度的词）与 lookup_pattern（≥）同一套收窄，只是最后一级不收更长的词。 整句转换的词图格子和「输入前缀也出候选」都只要精确等长的词，之前用 ≥ 版再过滤，白查一大片长词。

同一次查询里的重复：不同切分共享很多前缀（zh g d o… 的几种切法前几段一样），同一个前缀模式只查一遍（HashMap 记忆化， 键是模式串）。

排序：单字母简拼命中两万条，sort_by 的比较器里每次 chars().count() 让排序占几十毫秒。改成排序键先算好再排 （SortKey 元组，文本借自词库），远超上限时先按结构键 + 词频 select_nth_unstable 砍到 2 × 上限再算上下文得分、再排， 候选最多 500 条（同音字最多的音节也不到这个数，再往后没人翻）。去重只做到够数为止。

结果：长输入 20 ms → 0.2 ms，zhgdoima 70 ms → 1–3 ms，单字母 30 ms → 3–4 ms。

第三轮：逐键（2026-09-05）

起因：简拼整句、拼写纠错、英文模式几个功能叠上去之后，想在给测试者打包前系统量一遍。先加了 --typing 逐键模式， 一跑就看到三个极端：zhzhzhzhzhzhzhzh 16 键 44 ms（parse 39 ms），sssssssssssssss 15 键 21 ms（rank 13 ms）， 单字母首键 9–10 ms。常规输入（woxiangquchifan、kaifa）都在 1–4 ms，问题全在简拼极端情况和首键。

parse 39 ms：纠错变体

拼写纠错对「不像话」的拼音枚举一处编辑的全部变体（换位、替换、插入、删除，16 字母约 1500 个），每个变体跑一次 完整切分 DP（parser::segment，带 Vec<Segmentation> 克隆和排序）。任何非末尾有简拼的输入都算「不像话」， 所以全简拼句子每键都在做这件事，而且长度越长变体越多、每个变体的 DP 也越贵，二次增长。

改法：加一个只回答是否、不分配的 parser::is_fully_segmentable（一维可达性 DP，每个位置查 trie 拿合法音节长度）， 变体先过它，剩下的几个才做真正的切分。结果 39 ms → 0.17 ms。

rank 13 ms：整句词图的格子查词（弯路在这里）

sss… 15 个音节，词图有 15 × 8 = 92 个格子（最长词 8 音节），每个格子对词库做一次 lookup_exact。

先后猜错了两次：

1. 猜是格子内的排序：比较器里每次查两张哈希表（用户选择次数、个人出现次数）。改成得分先算好再排——没变化（12.6 → 11.9 ms）。
2. 猜是路径打分里的 bigram 查找：300 万对 (u64 键, 计数) 扁平数组二分，一次 22 步随机访问。改成按前词分组的 CSR （offsets[v]..offsets[v+1] 是 v 的后继段，段内按后词编号二分），内存 48 MB → 24 MB——也没变化（11.6 ms）。

然后才打点：92 个格子查词共 25 000 条原始命中、10 ms；路径打分只有 0.7 ms。热点是词库收窄本身： s s s s 这种简拼格子要把词库里所有 s 开头音节的组合走一遍，每步一两次二分，这是第二轮那个算法的固有代价， 再怎么调常数也省不掉。

改法：不省这一次，省后面十四次。敲键是增量的——第 n+1 键只新增以它结尾的最多 8 个格子，其余格子上一键都算过。 加 sentence::SpanCache：键是格子模式（每个位置的写法与是否完整，含模糊音写法），值是排好、截好的候选（Arc<[SpanWord]>， 不再借用词库）。候选只与词库、用户词、选择次数、个人出现次数有关，Engine 在 commit / learner_mut / 换 Learner 时整个清掉； 超过 8192 个格子也清。结果 12 ms → 1 ms，15 键平均 2.5 ms。

前两次改动保留了：得分预算是对的写法，CSR 是更好的布局（也是二进制化时的布局），只是它们不是这个瓶颈。 教训写在最后。

首键 9 ms：单字母命中 78 000 条

s 一键：lookup_pattern([s…]) 把所有首音节 s 开头的词全收进来（78 573 条），然后每条算一次用户权重（哈希查表）、 一次模糊音比对、构造 Scored，再进预选。打点分摊：查词 1.9 ms、构造 3.0 ms、预选 + 排序 3.8 ms、插入 1.4 ms （这 1.4 ms 是 jiff 首次加载时区，进程生命周期里只有一次）。

改了四处，每处都是常数级：

• 词频、语言模型词表、个人 n-gram 的 HashMap 换 foldhash（SipHash 一次几十纳秒，这里一键要查几万次）。
• 预选键从 9 元组打包成一个 u128（精确、覆盖字母数、简拼数、末音节完整、选择次数、词频、模糊、字数依次占位）， select_nth 比整数而不是逐项比元组；预选边界上的平手不再拿文本决胜，谁留下无所谓，最终排序仍用完整键。
• 没开模糊音时不逐条做模糊命中比对（is_fuzzy_hit 要 split 音节）。
• scored.reserve(hits.len())，省掉几次翻倍搬家。

结果 首键 9–10 ms → 4.5–5.6 ms，模糊音全开 8 ms。

这一轮之后的数字

场景	改前最慢一键	改后
全拼长句 woxiangquchifan	3.8 ms	3.1 ms
全简拼 15 字母	10.8 ms	3.4 ms
zhzhzh… 16 字母	44 ms	8 ms
sss… 15 字母	21 ms	4.5 ms
单字母首键	9 ms	5 ms（模糊音全开 8 ms）
英文模式（2.1 万词表补全 + 一处编辑纠正）	0.24 ms	不变
启动	1.03 s	0.93 s

启动里词库解析 0.24 s、语言模型表 0.62 s，这是 TSV 逐行 parse + 建哈希表的成本，靠算法省不掉，要改文件格式（下一节）。

第四轮：启动（2026-09-05，.qj 容器）

起因：启动 0.93 s，词库 TSV 解析 0.24 s、语言模型两张 TSV 解析 + 建哈希表 0.62 s。这是 89 万行 + 350 万行的逐行 parse、 排序、HashMap 插入，算法上没得省，要改文件格式。

改法：crates/qingjian-format 的 .qj 容器（设计见 design/architecture.md）。要点是内存布局就是文件布局： 第一轮的 arena + 偏移、第三轮的 CSR 本来就是几段连续数组，直接落盘；打开时 mmap，只校验头、分节边界、每条偏移是否越界。 语言模型的 HashMap<String, (id, count)> 换成文件里的开放寻址哈希索引（槽里放编号、键留在 arena、FNV-1a + fmix64 稳定哈希）， TSV 解析路径也改成产出同样的结构，查询代码只有一份。

弯路：第一版 Text::deref 用带校验的 from_utf8，每次取 &str 都扫一遍 30 MB arena，CLI 直接卡死超时。 打开时校验一次、之后 unchecked 才是对的；unsafe 的前提（文件只整体替换、从不就地修改）写在注释里。

结果：

	改前	改后
词库加载	240 ms	12 ms（其中大半是逐条校验偏移）
语言模型加载	620 ms	9 ms
Engine 就绪	930 ms	50 ms
文件体积	dict.tsv 26 MB + lm TSV 48 MB	dict.qj 46 MB + lm.qj 46 MB

体积反而大了：TSV 里词频是十进制文本，容器里是定长 u32，加上哈希表一半是空槽。以后要减体积就上变长编码， 但那会破坏零拷贝，除非只对冷字段（词频）做。首键从冷页开始时多 2–3 ms（缺页），madvise(WILLNEED) 已开， 再要就启动时后台线程摸一遍页。

第五轮：释义表进容器（2026-09-05）

起因：释义表全量生成后从 6 万词涨到 24 万词，TSV 解析从 20 ms 涨到 90 ms，启动 170 ms。

改法：Glossary 改成双存法：TSV 解析出来还是哈希表；.qj 是字符串 arena + 词条表（词的偏移、释义段）+ 释义表 （译文 / 读音 / 词性缩写各一段偏移）+ 文件里的哈希索引，与词库、语言模型同一套 qingjian-format。查表时按需拼出 Translation， 每键几百次、每次几十纳秒的哈希加几次切片。结果 释义表加载 90 ms → 8 ms，启动 170 ms → 47 ms（冷启动 116 ms，缺页）。

第六轮：词图敲错边（2026-09-06）

起因：整句词图每个完整音节多了十几种敲错写法（correction::typo），格子查词的分支随之变多。

数字（release，带用户数据，--typing）：28 键句子最慢 3.5 ms → 4.2 ms、平均 0.46 → 0.64 ms；40 键句子最慢 2.9 → 4.7 ms、平均 0.66 → 0.95 ms。 仍在每键 10 ms 的目标内。已做的收敛：换键只算相邻键（变体数少一半以上）；词级候选不加敲错边；整段一处编辑的变体上不再叠敲错边 （nihoama 的 parse 从 12 ms 回到 1 ms）；非末尾带简拼的切分、双拼、不到 4 个字母的不加。格子缓存的键含全部写法，敲错边不影响增量复用。 没做的：格子里敲错变体的命中先算全部再按 e^(−代价) 打折截断，理论上可以按代价分层、原样够多就不查变体，等数字需要再说。

第七轮：句末英文词（2026-09-08）

改动：Engine::split_english_tail 每次查询多做一遍「尾段是不是英文词」的扫描：从最长到最短试每个后缀查英文词表（哈希表）， 命中且整段能读成拼音时再多跑两次整句转换比分（头段一次、整段末尾单字母也读一次），都走 SpanCache。 数字：--typing woxiangxuehaorust 每键最慢 5.0 ms（改前 4.65 ms），平均 0.8 ms；回放 4867 条与改前完全一致。 比分只在尾段真是词表里的词时才发生，平时的键只多几十次哈希查表。

神经重打分的延迟另见 docs/notes/neural-rescoring.md： M1 上 Metal 空前文单条 6 ms、64 字前文 × 8 条 133 ms，离每键预算差一个量级，要做前文 KV 缓存与异步防抖。

第八轮：本地整句模型（2026-09-08）

起因：字级 Transformer 重打分在整句评测集上过了门槛（+4.3 个点，见 neural-rescoring.md），但同步打分一次查询 60 到 70 ms、20 字长句 800 ms， 远超每键 10 ms 预算，不能放进按键回调。

定位：cargo test --release -p qingjian-neural --features metal -- --ignored --nocapture 的延迟探针（M1，small 23M，8 条约 8 字的候选）：

后端	空前文 1 条	空前文 8 条	64 字前文 1 条	64 字前文 8 条
Metal，无缓存（改前）	6 ms	—	—	133 ms
Metal，前文 KV 缓存	6 ms	20 ms	8 ms	28 ms
CPU（candle gemm），前文 KV 缓存	17 ms	61 ms	19 ms	73 ms

前文重算与缓存命中只差 1 到 2 ms：前文那 64 个 token 一次前向很便宜，贵的是每条候选一遍、每层十几个小算子的调度； 所以候选越多越慢，与候选长度关系不大，也是 CPU 反而更慢的原因（同样多次小算子）。Accelerate 后端在本机编不过，没量。

改法：

1. qingjian-neural::PrefixCache：前文（去掉最后一个 token）每层的 K / V 算一次存下来，候选只算「前文最后一个 token + 候选」；结果与 Python 打分对拍不变。
2. Core engine/rescoring：一次查询里整句转换跑好几遍（纠错变体、中英混输比分），所有路径文本进一张「前文 + 文本 → 神经分」缓存， 同步打分器只补缺的分：评测每句 69 → 27 ms（--eval-text 300 句，λ 0.25 前文 64）。
3. 异步：打分在后台线程，按键回调只跑词级模型；壳停键 80 ms 后把缺分的文本一批送去，20 ms 轮询，到了重查一次只重画当前页。 --neural-async 走同一条路，300 句上与同步逐句一致，每句 35 ms（含等待与两次查询）。

结果：按键路径回到改前（查询 0.7 ms），模型的意见在停键后约 100 到 130 ms 到（80 ms 防抖 + 一批 20 到 30 ms + 轮询间隔）。 模型后台加载 + 预热：进程冷启动 353 ms（fp16 56 MB mmap）；机器第一次编译 Metal 内核那次 12 秒，系统缓存后不再有。 内存：权重按 f32 上 GPU 时输入法进程 273 MB（其中 GPU 侧 172 MB）；改成 Metal 上缺省 f16 后 CLI 评测进程 240 → 131 MB（GPU 侧 185 → 60 MB）， 300 句评测结果与 f32 逐句一致、与 Python 对拍仍在容差内，延迟略快（64 字前文 × 8 条 27 → 25 ms）。空闲时 CPU 0 到 1%，敲键那一刻 10 到 18%。 评测集全量（8322 句，--eval-text，同步模式，λ 0.5 前文 64）：改前平均 61 ms、最慢 781 ms；改后平均 24 ms、最慢 101 ms，命中率不变（41.6% / 79.1%）。

经验

1. 先量再改，先打点再改。 第三轮猜错两次的原因是凭「常识」判断热点（哈希查表、大数组二分都是教科书里的慢点）， 而真正的热点是自己两天前写的、以为已经快了的收窄算法。两个改动花的时间比打点多得多。
2. 量真实的工作负载。 输入法的真实负载是逐键增量查询，不是「查一次整段」。--typing 一加，之前一直测不出的问题 立刻出来。同理，测极端输入（全简拼、重复字母、模糊音全开）而不只测顺手的例子。
3. 增量场景优先想缓存，而不是优化单次。 格子查词的单次代价是算法固有的，但相邻两键 90% 的工作是重复的。 缓存的难点是失效条件，要把「结果依赖什么」列清楚（这里是词库、用户词、选择次数、个人计数），在改这些东西的每个入口清缓存。
4. 常数优化要成批做并分别量。 哈希器、键打包、跳过比对、预留容量，单看每项 0.5–1.5 ms，合起来首键砍掉一半。 但它们排在算法和缓存之后，先做算法。
5. 数据布局服务两件事：查询速度和文件格式。 arena + 偏移、CSR 这些选择让内存结构可以直接落盘，二进制化（第四轮）只花了半天， 而且解析路径和映射路径共用同一套查询代码。
6. 性能改动要有对拍或回归。 收窄算法与线性扫描随机对拍；排序 / 缓存改动跑全部单元测试加固定输入组。 没有这层保护，select_nth 换排序方向这种改动很容易悄悄改掉候选顺序。