面向 CPU 缓存命中率的 AC 自动机优化

面向 CPU 缓存命中率的 AC 自动机优化

💡 原文中文,约6000字,阅读约需15分钟。
📝

内容提要

文章介绍AC自动机v2优化:将节点和子节点标签存入连续数组,用二分查找替代std::map,并采用冻结快照布局提升CPU缓存命中率。测试显示,内存镜像加载耗时约为v1的1/48,常驻内存增量约1/13,构建索引由570.4ms降至304.7ms;含敏感词短文本匹配约快4倍,长文本约快1.24倍。

🔎

延伸解读

缓存优化并非万能:失败链接与边界检查仍有成本

文章明确指出,冻结快照让子节点标签连续存放,但失败链接仍会跳转,符号查找和边界检查也有开销。这意味着并非每条匹配路径都连续,缓存收益主要体现在节点和子节点标签的局部性上。读者应理解,v2 的优化是减少 std::map 和独立分配带来的缓存未命中,而非消除所有随机访问。

性能对比包含功能差异,命中次数增加不等于纯提速

测试中 v2 命中次数比 v1 多约 29%~47%,原因是 v1 不支持边界规则和别名等新功能。因此匹配耗时对比并非完全同功能比较,v2 的提速部分来自更早或更准确的命中。文章也提醒,无敏感词语料由 v2 自身筛选,v2 零命中是生成条件的一部分。读者在参考性能数据时需注意这些功能差异。

内存镜像加载的 48 倍提升有明确前提

v2 内存镜像加载 3.93 ms 仅统计镜像已在内存中的加载阶段,不包含读取文件,也不覆盖额外语义校验开销。compliance 实际使用文件流并开启 verify_semantics,默认文件流加载为 41.45 ms。若要改用字节缓冲路径,需在相同校验选项下比较“读取文件+加载”的总耗时和峰值内存,再决定是否值得。

碎片化堆下内存收益会收窄,但仍具参考价值

受控探针的 RSS 增量 v1 为 83.0 MB、v2 为 6.4 MB,约 13∶1;但在碎片化堆下,v1 的 RSS 增量降至 39.0 MB,因为 v1 可复用预先释放的空闲块,部分存储落在已计入基线的驻留页中。文章认为整体量级仍可参考。这说明内存收益受分配环境影响,读者应结合自身堆状态评估。

❓

Q&A

AC自动机v2优化主要解决了什么问题?

v2优化主要解决旧版AC自动机因节点独立分配和std::map管理子节点导致的CPU缓存命中率低的问题。通过将节点和子节点标签存入连续数组、用二分查找替代std::map,并采用冻结快照布局,提升缓存局部性,从而加快构建、加载和匹配速度。

v2的冻结快照布局具体是怎么组织的?

v2节点按广度优先顺序编号。每个节点用16字节保存子节点区间的起点、数量、失败链接和输出词条链表头;另有每节点4字节的标签数组,保存进入该节点的符号ID。同一父节点的子节点标签有序且连续,标签的数组下标就是目标节点ID。查询时,零个或一个子节点直接处理,多个子节点才做二分查找。

v2在加载和内存占用上比v1提升了多少?

根据测试,内存镜像加载耗时约为v1的1/48(v1 190.4 ms,v2 3.9 ms);常驻内存增量(RSS)约为v1的1/13(v1 83.0 MB,v2 6.4 MB)。构建离线索引总耗时由570.4 ms降至304.7 ms。

v2在文本匹配速度上比v1快多少?

含敏感词的短文本匹配v2耗时约为v1的0.25倍(约快4倍);含敏感词的长文本匹配约为0.81倍(约快1.24倍);无敏感词短文本和长文本的差距较小,v2耗时分别约为v1的0.90倍和0.96倍。

v2新增了哪些功能来减少误匹配?

v2增加了token别名规则,可将不同token归一化为同一符号(如“二”和“2”),合并等价匹配路径;还增加了可配置的左右边界规则,例如配置忽略大小写和边界后,能让“SM”命中,同时排除“SMS”和“smile”,从而减少短词误匹配。

测试中v2的命中次数为什么比v1多?

测试显示,在含敏感词的短文本和长文本语料上,v2的命中次数分别约为5003和5129,而v1分别为3878和3485,v2多约29%~47%。这主要是因为v1不支持v2的边界规则和别名等功能,导致部分匹配被遗漏;但命中次数增加不等于命中文本数同比例增加。

🏷️

标签

➡️

继续阅读