ripgrep 为什么快：正则引擎设计、并行搜索、内存模型（主题精读） 未开始

题记与说明

• 日期：2026-10-31
• 前缀：knowledge-4j1kbhrc-4
• 类型：主题研究（先检索多来源精读，再做本地实测复现）
• 来源（本主题的 5 个一手来源）：
  1. Andrew Gallant（BurntSushi）, *ripgrep is faster than {grep, ag, git grep, ucg, pt, sift}* — https://blog.burntsushi.net/ripgrep/ （作者本人 25 组基准 + 原理剖析，2016）
  2. ripgrep 官方 FAQ（尤其 "Why does using -P/PCRE2 get slower"、"--sort 与并行"、"mmap 行为"）— https://github.com/BurntSushi/ripgrep/blob/master/FAQ.md
  3. ripgrep README "Is it really faster than everything else?" — https://github.com/BurntSushi/ripgrep/blob/master/README.md
  4. Rust regex crate 文档（Performance / Crate features / O(m·n) 保证 / 字面量加速）— https://docs.rs/regex/latest/regex/
  5. grep-searcher crate 文档（Searcher/MmapChoice 内存策略）与 regex-automata::meta 模块文档 — https://docs.rs/grep-searcher/latest/grep_searcher/ 、https://docs.rs/regex-automata/latest/regex_automata/meta/index.html
• 本地实测环境：Windows 10.0.26200 x64，24 逻辑核，rg 15.1.0（features: +pcre2，WinGet 安装），GNU grep 3.0（C:\Program Files\Git\usr\bin\grep.exe；注意 PATH 中 /usr/bin/grep 实为 ugrep 7.8.4，对比时必须用完整路径）。语料为本会话生成：300MB 单文件（稀疏命中 359 处）+ 3000 个小文件目录树（48MB，1500 个在 .rgignore 排除的 build/ 下）。

一、七维提取

1. 核心问题

一个"代码搜索工具"（grep/ack 类）在真实仓库里要做到单大文件与海量小文件两个场景都不慢，难点在哪？ripgrep 作者要回答三个问题：

• 为什么一个带全量 Unicode 支持、默认尊重 .gitignore 的新工具能比 C 写的 grep 还快？
• 快到底来自哪几层：正则引擎设计？并行目录遍历？还是 IO/内存策略？
• 那些被广泛相信的"优化"（如 mmap 更快）在什么条件下反而是错的？

2. 主要主张

博客开头给出三条可检验声明（原文）：

- For both searching single files *and* huge directories of files, no other tool obviously stands above ripgrep in either performance or correctness.
- ripgrep is the only tool with proper Unicode support that doesn't make you pay dearly for it.
- Tools that search many files at once are generally _slower_ if they use memory maps, not faster.

README 把"为什么快"压缩成 5 点（原文）：

* It is built on top of Rust's regex engine. Rust's regex engine uses finite automata, SIMD and aggressive literal optimizations to make searching very fast.
* Rust's regex library maintains performance with full Unicode support by building UTF-8 decoding directly into its deterministic finite automaton engine.
* It supports searching with either memory maps or by searching incrementally with an intermediate buffer. The former is better for single files and the latter is better for large directories. ripgrep chooses the best searching strategy for you automatically.
* Applies your ignore patterns in .gitignore files using a RegexSet. That means a single file path can be matched against multiple glob patterns simultaneously.
* It uses a lock-free parallel recursive directory iterator, courtesy of crossbeam and ignore.

3. 方法

（a）正则引擎设计 —— 有限自动机 + 字面量预过滤，而非回溯

• 默认引擎基于有限自动机，保证最坏 O(m·n)（m≈正则编译后大小，n≈被搜文本字节数），从根上消灭回溯型引擎的灾难性回溯（re.search('(a*)*c', 'a'*30) 指数爆炸；ucg 实测直接 match limit exceeded 崩溃）。代价：不支持反向引用，lookaround 需 -P 切到 PCRE2。
• 字面量优先（prefilter）：引擎从 AST/HIR 提取前缀/后缀/内部字面量，用 SIMD 扫描候选位置，候选命中才进核心引擎验证；foo|bar 这类纯字面量交替完全绕过核心正则引擎。文档原文（regex crate）：

This crate tends to be quite good at recognizing literals in a regex pattern and using them to accelerate a search. … in the regex \w+@\w+, the engine will look for occurrences of @ and then try a reverse match for \w+ to find the start position.
perf-literal — Enables the use of literal optimizations for speeding up matches. In some cases, literal optimizations can result in speedups of *several orders of magnitude*.

• 多字面量算法分层：少量字面量 → Teddy（作者从 Intel Hyperscan 移植的未发表 SIMD 算法，16 字节打包比较）；字面量多到 Teddy 候选误报爆炸 → 回退到"Advanced Aho-Corasick"（把失败转移编译成连续内存 DFA 表，每字节一次查表，不追指针）。单字面量 → memchr，且先挑"最稀有字节"再交给 memchr（Boyer-Moore 教科书式固定取末字节，在西里尔文本上恰好蒙对、在别处会蒙错——rg 用 256 字节频率先验主动选字节）。
• 元引擎调度（regex-automata 0.4 meta::Regex）：regex crate 是 meta 引擎的薄包装，内部按模式形态在 lazy DFA（大干草垛上"通常快一个数量级"）、one-pass DFA（提取捕获组最快）、有界回溯（介于 PikeVM 与 one-pass 之间）、PikeVM（兜底）之间选择。feature 文档原文：

perf-dfa — Enables the use of a lazy DFA for matching. The lazy DFA is used to compile portions of a regex to a very fast DFA on an as-needed basis. This can result in substantial speedups, *usually by an order of magnitude on large haystacks*.

• UTF-8 解码编译进自动机：Unicode 类（\w、\p{Greek}）不先解码再匹配，而是把 UTF-8 字节级转移直接编进 DFA，非法 UTF-8 自然不匹配。这是"Unicode 全开仍不减速"的根源（源自 Ken Thompson/Russ Cox 技巧）。
• rg 应用层独有的 inner-literal 优化：grep-regex 利用 regex-syntax 的完整解析器提取"行内必含字面量"，先按行粗筛、只对候选行跑完整正则（--debug 可直接看到 extracted fast line regex: "(?:(?:fox)|(?:lazy))"，本会话实测输出）。作者坦承该优化放在引擎里做有本质困难：找到字面量后不知道从哪开始匹配整条正则，通用化会引入二次方风险。

（b）并行搜索 —— 并行目录遍历 + 锁无关工作窃取

• 目录遍历与搜索解耦：ignore crate 的 WalkParallel 分发文件路径，Chase-Lev 无锁 work-stealing 队列（作者强调其他参评工具全用互斥锁队列变体）。默认线程数=逻辑核数。
• 打印端串行化以避免交叉输出，但先写内存缓冲再一次性 dump，否则"边搜边抢打印锁"会把并行完全串行化。代价是高命中时内存膨胀（单文件/stdin 场景直接写 stdout 绕过缓冲）。
• .gitignore 规则集编译成一个 RegexSet，一条路径一次匹配全部 glob（而非逐规则试）。
• 两个可直接观察的推论：--sort path 会关闭并行；-j1 退化为串行。

（c）内存模型 —— mmap 不是银弹

• rg 的搜索器按字节流增量搜索（大缓冲区 + 行边界簿记 + 上下文行跨缓冲区携带），mmap 只是其中一种可选策略。MmapChoice 文档原文：

Use memory maps when they are believed to be advantageous. The heuristics used to determine whether to use a memory map or not may depend on many things, including but not limited to, *file size and platform*. … By default, memory maps are disabled.

• 结论是经验性的、随场景反转的： thousands of small files → mmap 慢（每文件建映射的内核簿记开销）；single large file → mmap 快（只建一次映射，省掉 read 拷贝）。rg 的 auto 启发式按"文件数/大小/平台"自动选；本机实测见下节（Windows 上 mmap 反而慢）。
• FAQ 用 --trace 展示策略切换（原文输出节选）：

TRACE|grep_searcher::searcher … searching via memory map / slice reader: searching via slice-by-line strategy / searcher core: will use fast line searcher

• "Thou Shalt Not Search Line By Line"：逐行起停正则的开销在"命中稀少"的常态下是纯浪费；正确做法是大缓冲整体搜、命中后再切行。

4. 数据与证据

（a）作者基准（EC2 c3.2xlarge + 作者本地 i7-6900K，Linux kernel built tree / OpenSubtitles 2016，全部可由仓库内 benchsuite 复现）：

• linux_literal_casei（大小写不敏感字面量）：rg 0.345s vs pt(Go regexp) 17.204s —— rg 靠"大小写折叠展开成字面量交替 + Teddy"，pt 坠入 Go 无 DFA 的引擎。
• linux_unicode_word（\wAh，Unicode 词类）：rg 0.355s vs git grep 13.045s —— git grep 为 Unicode 付出 37 倍代价，rg 几乎为零（UTF-8 编进 DFA）。
• subtitles_alternate（5 字面量交替，1GB 英文字幕）：rg 0.294s vs grep 2.955s —— 纯 Teddy，核心正则引擎一次未跑，快约一个数量级。
• subtitles_no_literal（无字面量 \w{5}\s+\w{5}…）：rg 2.777s vs grep(Unicode) >90s；rg Unicode 版只比 ASCII 版慢约 0.3x（Unicode NFA 状态 77,000 vs ASCII 250，懒 DFA 按需构建）。
• mmap 对照（同一 rg 同一查询）：rg (ignore) 0.334s vs rg (ignore)(mmap) 1.611s —— 控制变量后矛头直指 mmap。
• 大小写折叠字面量展开（--debug 可见）：PM_RESUME → PM_RE/PM_Re/…/pm_re 共 16 个前缀字面量喂给 Teddy；含 ſ（U+017F）这类 Unicode 简单大小写折叠变体。

（b）本会话本地实测（命令与原始输出，3 次取观察，bash time，单位秒）：

单文件 300MB、Sherlock Holmes 稀疏 359 命中：

目录树 48MB/3000 文件（.rgignore 排除一半后默认只搜 23,742,000 字节，--stats 证实；-uuu 搜 47,484,015 字节）：

300MB 单文件正则（注意：命中数高达 180 万，属 README 自述的高命中病态区）：

• rg -c '\w+\s+fox\s+\w+'：0.539/0.525/0.750 vs GNU grep -cE 0.126/0.105/0.122
• rg -c '(\w+\s+){4}\w+'（无字面量）：0.822/0.572/0.670 vs grep 0.102/0.120/0.127

--stats 原始片段（tree 默认模式）：12000 matches / 3000 files searched / 47484000 bytes searched / 0.151000 seconds spent searching / 0.415357 seconds total（搜索纯耗时只占总时长约 1/3——遍历与打印是另一大块）。

对本地实测的诚实解读：目录树场景与作者结论一致——并行+忽略规则使 rg 默认模式比 grep -r 快约 6 倍（0.23s vs 1.5s），并行化（-j1→默认）在本机约 2 倍；--sort path 确实禁用并行变慢。但单大文件场景 GNU grep 3.0 在这台 Windows 机器上全面更快（连无字面量正则都快 5 倍以上），rg 的 mmap 默认策略在 Windows 单文件上也是负优化（--no-mmap 反超）。这与博客"平台依赖、VM 会惩罚 mmap"的警告方向吻合，也提示：Linux 上 rg 的单文件优势（作者数据 rg 全胜）不能想当然平移到 Windows。

5. 结论

1. ripgrep 的快是分层的工程结论，不是单点魔法：①有限自动机引擎的 O(m·n) 底线（消灭 ReDoS）②字面量预过滤（多数真实查询根本不进核心引擎）③UTF-8 编进 DFA（Unicode 免费送）④无锁并行目录遍历（多核白拿）⑤ mmap/增量读按场景启发式选择（"mmap 更快"是有条件的神话）。
2. 工具层与引擎层的分工明确：inner-literal 这类"知道自己在搜行"的优化放在 rg，不放在通用引擎里；引擎层只负责保证任意消费者都拿到 lazy DFA/Teddy/Aho-Corasick/memchr 的自动加速（README 原文：大多数优化在 regex 库里，"every consumer of that library gets all these performance optimizations automatically"）。
3. PCRE2 慢的原因可完全归因到两条：失去"静态禁止跨行匹配"导致逐行慢搜 + Unicode 强制 UTF-8 转码；-U --no-pcre2-unicode 可让 PCRE2 JIT 反超（FAQ 实测 2.458s → 1.121s）。这条是把"引擎能力"和"数据供给方式"分开分析的绝佳案例。
4. 忽略规则（.gitignore/.rgignore）首先是相关性优化，性能上"是严格的加分项但不是必然"——规则编译与逐路径匹配有开销，Linux kernel 树 178 个 ignore 文件的代价被 RegexSet 均摊。

6. 局限

作者自认的：

• 博客基准是"curated"且作者在其中一方，"there are so many variables to control for that testing every possible permutation isn't feasible"；承认选择了对己有利的表述空间但公布全部原始数据。
• PCRE2 慢的分析作者自注 "This author is not a PCRE2 expert, so there may be APIs that can improve performance that the author missed."
• inner-literal 通用化无优雅解：找到字面量后"don't know where to start searching the full regex"，双向搜索暴露二次方风险，未解决。
• find_iter 的最坏复杂度是 O(m·n²)（文档明确说明），earliest(true) 可恢复 O(m·n) 但改变贪婪语义。
• 2016 年的博客距今十年：Teddy/元引擎描述对应当时实现（rg 0.x，SIMD 需 nightly feature）；现在 simd-accel feature 已被移除（README 468-471 行明确说明），SIMD 检测改为运行时自动进行；元引擎（regex-automata 0.4，2023 重写）让引擎选择比博客描述更精细。数值结论应视为"该年代的快照"，机制描述仍有效。
• 我方实测的局限：语料是合成重复文本（真实代码压缩比/字节分布不同）；Windows MSYS 的 GNU grep 3.0 老（2017）且非典型发行版；rg 15.1.0 与博客的 rg 0.1.2 差了十年；单文件正则测试命中 180 万属病态；未测 git grep（无仓库）；未跑 Linux 对照组。因此"Windows 上 grep 单文件更快"是本机观察，不宜外推为普遍规律。

7. 对我的启发

• 性能归因要像作者那样拆变量：rg vs ag 的差距被 rg (ignore) vs rg (ignore)(mmap) 一组对照钉死在 mmap 上——任何"X 比 Y 快"的结论都应配一个只改一个变量的对照组。这比看总分可信得多。
• "快"的最大红利常在引擎之外：字面量预过滤让常见查询根本不进引擎；同理，我的工具链/Agent 性能优化应先问"能不能让热路径压根不走重逻辑"，再谈微优化。
• 无锁 work-stealing + 先缓冲后串行打印是多线程 CLI 工具的正确模板：并行计算与串行输出解耦，正确性不牺牲。
• O(m·n) 是产品承诺：regex crate 把"永不 panic + 线性时间"写进 API 文档当作设计约束，这值得在自研解析/匹配组件时效仿——先保证最坏情形，再优化均值。
• 对后续"终端工具链实践建议"的直接输入见下节。

二、配套终端工具链实践建议（从上述机制直接推导）

配置固化（RIPGREP_CONFIG_PATH 指向一个 rc 文件，每行一个 flag）：

# ~/.config/ripgrep/rc
--smart-case          # 小写不敏感、含大写才敏感：不牺牲 Teddy 字面量路径
--stats               # 结束时打印 searched bytes/spent searching，顺便当性能仪表
--colors=line:style:bold

注意 FAQ 原文：结果顺序不定是并行的固有副作用，"The only way to make the order of results consistent is to ask ripgrep to sort the output. Currently, this will disable all parallelism."——脚本里要确定性顺序就 --sort path，交互场景别加。

性能调优速查（每条都有上文机制依据）：

1. 正则能带字面量就带：\w+@\w+ 靠 @ 加速；纯交替 foo|bar 走 Teddy 完全绕过核心引擎；--debug 可看提取结果（本会话实测：extracted fast line regex: "(?:(?:fox)|(?:lazy))"）。
2. Windows/VM 上单大文件搜索变慢时先试 --no-mmap（本机实测 0.35s→0.24s）；--trace 能证实当前走的是 memory map 还是 slice-by-line。
3. 结果"变少"先怀疑忽略规则：默认尊重 .gitignore 但仅限 git 仓库内（本会话踩坑：非 git 目录 .gitignore 不生效，用 .rgignore 或 --no-require-git）；-u/-uu/-uuu 逐级放开（等价 grep -r / grep -a -r）。
4. -f patterns.txt 大模式文件变慢是 DFA 缓存太小：--dfa-size-limit 1G（FAQ 原文："an internal cache is too small, and will cause ripgrep to spill over to a slower but more robust regular expression engine"）。
5. 需要 lookaround/反向引用才 -P（PCRE2）；要榨干 PCRE2 速度用 -U --no-pcre2-unicode（FAQ 实测 2.962s→1.121s），代价是接受非 Unicode 语义。
6. 高命中模式天然慢（README："high match counts also tend to both tank performance"——本机 180 万命中实测 rg 明显掉速），能用 -l/--files-with-matches 短路就短路。
7. 并行度用 -j 显式控制；共享一个 Regex 跨线程高频短干草垛有同步争用，文档建议 clone 后按线程分发。
8. 编译一次、处处复用：std::sync::LazyLock 缓存 Regex，循环内重复编译是反模式（regex 文档明确列为 anti-pattern）。
9. 管道组合：rg foo --files-with-matches -0 | xargs -0 sed -i 's/foo/bar/g'（FAQ 推荐做法；含空格路径用 NUL 分隔）。
10. --json 输出给下游程序消费；--stats/--trace/--debug 三件套分别对应"性能仪表/内存策略/引擎策略"三个观测层。

与 grep 的分工：可移植脚本、POSIX 语义、任意环境 → grep；交互式代码搜索、大目录、Unicode → rg。FAQ 原文的表述值得记住：ripgrep "never was, isn't and never will be POSIX compatible"。

三、重要原文引述索引（防丢失）

四、本会话执行记录（可复现）

# 语料生成（python -I，synthetic）
# single/big.log: 300.0MB, 每~5001行1个"Sherlock Holmes" → 359 hits
# tree: src00..src59/{build,code}/f000..f049.log，每文件120行，每37行1个 ERR_SYS
# tree/.rgignore: "build/"（.gitignore 在非 git 目录不生效，实测已踩坑）

export TIMEFORMAT='%R'
bench() { local label="$1"; shift; local t; for i in 1 2 3; do
  t=$( { time "$@" >/dev/null 2>/dev/null; } 2>&1 ); echo "$label run$i: ${t}s"; done; }
rg --version          # ripgrep 15.1.0 (rev af60c2de9d) features:+pcre2
"/c/Program Files/Git/usr/bin/grep.exe" --version   # grep (GNU grep) 3.0
rg ERR_SYS tree --stats              # 47484000→23742000 bytes searched（rgignore 生效后）
rg 'Sherlock Holmes' single/big.log --trace 2>&1 | grep -i 'memory map'
rg --debug '[a-z]+fox[a-z]*|lazy\s+cat' tiny.txt 2>&1 | grep extracted

（实测数据表见"数据与证据"节；本笔记所有数字均出自上表与来源原文，无转引猜测。）